极大单调算子的加速近端点法
本文回顾了近端点法在大规模优化中的作用,并重点介绍了三个最新的例子:用于弱凸随机逼近的近端指导次梯度法,用于最小化凸函数和平滑映射组合的近端线性算法以及用于正则化经验风险最小化的 Catalyst 通用加速。
Dec, 2017
本文研究了一个迭代算法在具有约束的非单调集值算子中寻找零点的收敛性,这个算法被称为 proximal-projection 算法,收敛结果基于 Opial 引理的新概括。我们展示了 proximal-projection 算法可以被应用于求解仅具有近似数据的 ILL-POSED 变分不等式和凸优化问题。此外,我们证明了 proximal point 算法(具有 Bregman 距离)的收敛性在算子具有顺序弱闭图形时仍然存在。
Nov, 2007
本文介绍了通过应用已知算法到原问题的复合平滑近似,获得无约束或线性约束的复合非凸凹、极小极大(因而是非光滑的)问题的近似稳定点的平滑方案。具体而言,在无约束(resp. 有约束)的情况下,通过应用作者先前提出的加速不精确近端点算法(resp. 二次罚项)到其复合平滑近似,获得原问题的近似稳态点。同时,还建立了两个平滑方案的迭代复杂度界。最后,给出了数值结果,以展示无约束平滑方案的效率。
May, 2019
研究了泛化的 “Proximal Point Algorithm(PPA)” 在寻找 “Maximal Monotone Operator” 的零点上的线性收敛率问题,并证明 Rockafellar 提出的条件足以确保这种泛化的 PPA 的线性收敛率;同时,这种泛化的 PPA 包括 PPA 源自的一些分裂方法的松弛版本。在特定的凸优化情境中,提出了比现有条件更弱的改进条件。
May, 2016
提出了两个针对非凸情况的数值算法,用于快速解决优化问题。该算法基于可变度量介绍了近端项,这使得我们能够针对非凸结构优化问题构建新的近端分裂算法。在变量度量序列条件温和并且假设相关增广拉格朗日函数具有 Kurdyka-Lojasiewicz 性质的情况下,证明了该算法迭代可以收敛到 KKT 点,并获得了增广拉格朗日函数和迭代的收敛速度。
Jan, 2018
我们扩展了 Approximate-Proximal Point 方法,在随机凸优化问题中应用包括随机次梯度、近端点和束方法,同时提出了更快的模型算法和加速方案,保持了 Approximate-Proximal Point 算法的鲁棒性,同时提供了更快的收敛速度和更低的界限。我们通过实证测试证实了理论结果的可行性。
Jan, 2021
本文提出了一种新的 proximal ADMM 算法,使用平滑后的原始迭代的序列并在每次迭代时向增广拉格朗日函数中引入一个二次近似项。该算法的迭代收敛到这个问题的一个站点,特别是当目标函数是二次函数时,证明算法的线性收敛性。
Dec, 2018
本篇论文提出了一种新的随机坐标下降方法,能够并行、加速和提高期望可分超逼近,此方法能够同时最小化依赖于少数坐标的多个凸函数的和,通过使用新的安全且大的步长,使得该方法不需要执行完整的矢量运算。
Dec, 2013
本文提出了基于模型的方法,解决随机凸优化问题,并介绍了近似近端点(aProx)家族,包括随机次梯度、近端点和束方法。通过适当准确的建模方法,这些方法享有比传统方法更强的收敛性和鲁棒性保证,即使与随机次梯度方法相比,基于模型的方法通常增加很少甚至没有计算开销。
Oct, 2018
本文提出了一种新的方法 —— 加速镜像近端(AMP)方法,用于计算一类确定性和随机单调变分不等式的弱解,该方法将多步加速方案融入到镜像近端方法中。对于确定性和随机 VI,AMP 方法计算出最佳收敛速度的弱解。特别地,如果 VI 中的单调算子由平滑函数的梯度组成,则 AMP 方法的收敛速度估计中的 Lipschitz 常数可以加速。对于有界可行集的 VI,AMP 方法的收敛速度估计取决于可行集的直径。对于无界 VI,我们采用 Monteiro 和 Svaiter 引入的修改间隙函数,证明了 AMP 方法的收敛速度取决于初始点到强解集合的距离。
Mar, 2014