Apr, 2015

非强凸优化的一阶方法线性收敛

PDF
TL;DR本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率，提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的，最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。
convex optimizationconstrained optimizationlinear convergencestrong convexitygradient
发现论文，激发创造
  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

  • 广义平滑下的凸优化和非凸优化

    本文介绍了一种新的非均匀光滑条件下的优化方法，并开发出一种简单但有效的分析技术来限制沿轨迹的梯度，从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了（随机）梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率，而不需要梯度剪裁，并允许在随机场景中的有界方差的重尾噪声。

    Jun, 2023

  • Newton 方法在无强凸性或 Lipschitz 梯度情况下的全局线性收敛

    证明了牛顿法对于具有稳定 Hessians 的目标函数具有全局收敛的线性速度，在这一类问题中包括了许多不是强凸的函数，如逻辑回归，相比于仅在类似条件下实现次线性 $O（1/t^2）$ 收敛率的一阶方法，我们的线性收敛结果是（i）仿射不变的，即使使用（ii）近似海森和（iii）仅近似解决子问题。

    Jun, 2018

  • 基于线性化增广 Lagrangian 函数的约束凸规划的一阶方法

    本文提出了两种针对带约束凸问题的一阶方法，分别使用增广拉格朗日方法和单一近端梯度步进行变量更新，并证明了它们的全局和局部收敛性。数值实验验证了理论结果与实际表现的一致性。

    Nov, 2017

  • 一阶方法实现的相对平滑凸优化及其应用

    本文提出相对平滑性和相对强凸性的概念，并相应地将标准算法扩展到新的设置中，应用于发展新的一阶方法来解决 D - 优化设计问题并进行计算复杂度分析。

    Oct, 2016

  • 一种线性收敛的条件梯度算法及其在在线和随机优化中的应用

    本研究介绍了一种基于条件梯度算法的优化模型，可用于求解线性优化问题和非线性凸优化问题，并给出了一种基于此算法的在线凸优化算法，具有线性收敛速度和最优的遗憾保证。

    Jan, 2013

  • Hamiltonian Descent 方法

    研究了一种基于动力学系统模拟的优化方法，该方法使用常量步长和一阶梯度信息，在更大的凸函数类中实现线性收敛性，包括那些在其极小值点处可能具有奇异或未有界的二阶导数，该方法的动力学梯度映射可以设计成以凸共轭的形式整合信息，允许在非平滑或非强凸的凸函数上实现线性收敛。

    Sep, 2018

  • 一类非凸非光滑优化问题的收敛保证

    对于非凸、非光滑函数的关键点寻找问题，本文研究了三种基于梯度的方法 (梯度下降、近端更新、弗兰克 - 沃尔夫更新) 的行为，并证明了这些算法的收敛速率，同时也为连续亚解析函数证明了更快的收敛速率，优化后的算法具有更低的迭代成本，并通过应用于最佳子集选择、鲁棒估计、混合密度估计和形状阴影重建等问题，展示了方法和理论的实际效果。

    Apr, 2018

  • 解凸二层优化问题的一阶方法

    本文研究凸双层优化问题，其中内层最小化平滑函数和非凸函数的和，外层旨在在内层问题的最优解集合上最小化平滑且强凸的函数。我们分析了一个基于现有不动点算法的一阶方法，通过内部目标函数值建立了方法的全局次线性收敛率。

    Feb, 2017

  • 一阶方法的平滑强凸插值及其最坏情况下的精确性能

    通过解决凸性问题，可以得到针对光滑（可能强烈凸）函数的固定步长的一阶方法的最坏情况下的性能。将一种黑盒一阶方法的最坏情况性能的确定视为在一组光滑（强）凸函数和初始条件上的优化问题。此工作证明了性能的最坏情况估计问题可以看作是一个相当的有限维度独立半定优化问题，其精确解可以恢复到数值精度。

    Feb, 2015