May, 2019

解决非凸凹极小极大问题的加速非精确近端点方法

PDF
TL;DR本文介绍了通过应用已知算法到原问题的复合平滑近似，获得无约束或线性约束的复合非凸凹、极小极大（因而是非光滑的）问题的近似稳定点的平滑方案。具体而言，在无约束（resp. 有约束）的情况下，通过应用作者先前提出的加速不精确近端点算法（resp. 二次罚项）到其复合平滑近似，获得原问题的近似稳态点。同时，还建立了两个平滑方案的迭代复杂度界。最后，给出了数值结果，以展示无约束平滑方案的效率。
smoothing schemescomposite nonconvex-concave problemsaccelerated inexact proximal point methodquadratic penalty methoditeration complexity bounds
发现论文，激发创造
  • 求解线性约束非凸组合问题的二次惩罚加速不精确近端点方法的复杂度

    本文研究了一种二次罚函数加速的不精确近端点法迭代复杂度，用于求解线性约束下的非凸组合规划问题。作者证明了该方法能够在加速梯度下降法的基础上，有效地生成近似极小点。数值结果表明该方法的有效性。

    Feb, 2018

  • 统一的连续伪凸逼近框架

    该研究提出了一种连续伪凸逼近算法以有效计算一类可能非凸优化问题的稳态点，并针对未加区分的优化问题提出了一种新的一维搜索方法。

    Jun, 2015

  • 基于不光滑优化的变量度量不精确线性搜索方法

    我们提出了一种新的近端 - 梯度方法，用于最小化可微、可能非凸的函数加上凸、可能非可微的函数，并探讨了度量可能在每次迭代中改变，近似计算近端点并给出充分条件的可能性。我们还展示了这个方法在图像恢复问题中的竞争力。

    Jun, 2015

  • 非光滑非凸优化的快速随机方法

    本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

    May, 2016

  • 约束下凸规划的不精确近端路径跟踪算法

    通过使用可计算的接近算子和自共轭障碍的凸约束集，提出了一种新的关于近端和自共轭障碍概念的混合处理方法，并提出了一种非精确路径跟踪算法框架，可以有效地解决非光滑凸最小化问题，同时可以以无调谐自由的方式获得自共轭目标正则化问题的 Pareto 前沿点。

    Nov, 2013

  • 非凸 - 凹平滑极小极大问题的一阶纳什均衡高效搜索

    本文提出了一种有效的算法，通过在原函数上执行近似的近端点迭代，并利用 Nesterov 算法在正则化函数上运行不精确的神谕来找到关于站点准则的（εx，εy）第一阶纳什均衡，其中目标函数在两个变量中都是平滑的，对 y 是凸的；集合 X 和 Y 都是凸集和 “投影友好型” 的，Y 是紧凑的。

    Feb, 2020

  • 最大结构非凸优化的原始 - 对偶平滑框架

    本文提出了一种基于原始 - 对偶平滑框架的方法，用于寻找一类非光滑非凸优化问题的近似稳态点，并通过两种方法，即先对偶后原始和先原始后对偶平滑方法分析了框架的原始和对偶梯度复杂度。通过一个新开发的非 Hilbertian 不精确加速近端梯度算法来解决一类（强）凸 - 凹鞍点问题，进一步改进了已有方法的最佳 oracle 复杂度，并讨论了其变体和扩展。

    Mar, 2020

  • 一类非凸非凹极小极大问题的固定时间收敛

    本文提出了一种基于固定时间的收敛鞍点动力系统，用于在标准凸凹性假设的放松下解决极小极大问题。

    Jul, 2022

  • 非凸强凹极小 - 极大优化的复杂性

    本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

    Mar, 2021

  • 复合凸极小化的近端梯度法的最恶情况收敛速率

    本文研究了求解由平滑强凸函数和可得到其 Proximal 算子的非光滑凸函数组成的函数和的最优收敛速度，并利用半定规划等工具，建立了 Proximal 梯度算法的准确最坏情况收敛速度，同时提出可将强凸性等条件放宽以保证相应的收敛速度，得到了三种性能度量的同一步长最优的证明。

    May, 2017