非凸非光滑优化中的 ADMM 全局收敛性
该研究分析了 ADMM 算法在解决一些非凸共识和共享问题时的收敛性,发现当增广拉格朗日乘数的惩罚参数足够大时,经典 ADMM 算法会收敛到静止解的集合。对于共享问题,我们发现 ADMM 无论变量块的数量如何,都是收敛的。该分析不对算法生成的迭代强加任何假设,并且广泛适用于涉及近端更新规则和各种灵活的块选择规则的 ADMM 变体。
Oct, 2014
本文研究交替方向乘子法 (ADMM) 用于多个非光滑凸可分函数的线性约束约束下极小化问题的收敛速率,通过引入一种新的与其它满足该问题的近似算法有所不同的证明手段,我们在不限制强凸性的情况下,建立了全局线性收敛性的证明方案,表明 ADMM 的线性收敛性可以在三个以上的可分函数的情况下适用,包括 LASSO,Group LASSO 和 Sparse Group LASSO 等当代应用。
Aug, 2012
本篇论文提出两种针对非凸非光滑目标函数的扩展线性交替方向乘子法 (ADMM),均在较少的前提下保证收敛,并且可以使用多个块来并行计算协同变量以更有效地求解问题。
May, 2017
本文研究了一种名为 Bregman modification 的 ADMM 算法,在某些限定条件下证明了 BADMM 迭代序列能够收敛到相关增广拉格朗日函数的静止点,这为 ADMM 在非凸设置中的应用提供了可行性。
Oct, 2014
本文为非凸优化问题提供一种广泛适用的解决方法,即交替方向乘子法(ADMM),并研究了其在不同领域的实用性,包括线性回归、图像降噪、相位恢复及特征向量计算, 最近从提出的自适应 ADMM 方法可以通过自动调整惩罚参数来提高算法效率和解决质量 compared to ADMM with a non-tuned penalty。
Dec, 2016
本文针对图像科学中广泛使用的一类优化问题,基于 ADMM 算法,通过使用通用的双重步长方法、构建特殊的潜函数以及采用简单的初始化策略实现了非凸优化问题全局收敛和解决,并在实际应用中进行了比较实验,表明最优化效果良好。
Jun, 2015
本研究介绍了一种 Bregman 改进的 3 块 ADMM,并证明了其在大多数非凸函数下的收敛性,进一步扩展到多块(N≥3)的情况,证明了其在非凸设置下的可行性。
May, 2015
本文提出了一种扩展了 Alternating Direction Method of Multipliers 框架的方法 neADMM,可以用来解决非线性等式约束问题,并针对其中难点之一的非凸子问题提出了全局最优解决方案,实验结果表明这种方法在合成数据和现实世界数据上具有极高的性能和可扩展性。
May, 2017
本论文提出了一种新的证明交替方向乘子方法(ADMM)在一个目标项强凸时线性收敛的方法,并在一个数值示例上演示了通过选择算法参数来最小化收敛速率的做法,同时构造了一个接近匹配的收敛率下界。
Feb, 2015
本文提出了一种基于 ADMM 算法的方法,可以用于解决包含多元仿射约束条件及非凸、非光滑目标函数的优化问题,并证明在满足特定条件下,该方法可以收敛于受约束的稳定点解集合,且在 Kurdyka-Lojasiewicz 性质成立的情况下,可进一步收敛于单个受约束的稳定点。作者应用该方法解决了矩阵分解、风险均衡投资组合优化、凸优化问题的非凸化以及神经网络训练等问题,并证明算法子问题可以有封闭式解。
Feb, 2018