Aug, 2012

关于交替方向乘子法线性收敛的研究

PDF
TL;DR本文研究交替方向乘子法 (ADMM) 用于多个非光滑凸可分函数的线性约束约束下极小化问题的收敛速率，通过引入一种新的与其它满足该问题的近似算法有所不同的证明手段，我们在不限制强凸性的情况下，建立了全局线性收敛性的证明方案，表明 ADMM 的线性收敛性可以在三个以上的可分函数的情况下适用，包括 LASSO，Group LASSO 和 Sparse Group LASSO 等当代应用。
发现论文，激发创造
  • ADMM 收敛性的一般分析

    本论文提出了一种新的证明交替方向乘子方法（ADMM）在一个目标项强凸时线性收敛的方法，并在一个数值示例上演示了通过选择算法参数来最小化收敛速率的做法，同时构造了一个接近匹配的收敛率下界。

    Feb, 2015

  • 一类非凸问题交替方向乘子法的收敛分析

    该研究分析了 ADMM 算法在解决一些非凸共识和共享问题时的收敛性，发现当增广拉格朗日乘数的惩罚参数足够大时，经典 ADMM 算法会收敛到静止解的集合。对于共享问题，我们发现 ADMM 无论变量块的数量如何，都是收敛的。该分析不对算法生成的迭代强加任何假设，并且广泛适用于涉及近端更新规则和各种灵活的块选择规则的 ADMM 变体。

    Oct, 2014

  • 非凸非光滑优化中的 ADMM 全局收敛性

    本文分析了交替方向乘子法（ADMM）在非凸优化中的收敛性，并提供了针对特定情形的收敛保证。同时，通过例子和分析，本文表明 ADMM 有望比增广拉格朗日方法（ALM）更适用于某些非凸非光滑问题。

    Nov, 2015

  • 带收敛分析的非凸非光滑优化的线性化 ADMM

    本篇论文提出两种针对非凸非光滑目标函数的扩展线性交替方向乘子法 (ADMM)，均在较少的前提下保证收敛，并且可以使用多个块来并行计算协同变量以更有效地求解问题。

    May, 2017

  • 凸复合二次和半定规划的交替方向乘子法的线性收敛率

    本文提供了一种更加通用的半迭代交替方向乘子法，以解决线性约束下的凸组合优化问题，并证明该方法具有线性收敛性。同时，文章还说明了该方法在解决多个块的凸优化问题时非常有效，其中凸组合二次规划和二次半定规划是重要的应用之一。

    Aug, 2015

  • 使用双块交替方向乘子法解决多块可分凸最小化问题

    本文探讨使用交替方向乘子法（ADMM）来解决多块可分凸优化问题。提出了一种将多块问题转化为等价的二块问题来解决的策略，并分别从理论和实验结果两方面证明了其收敛性和数值效率优势。

    Aug, 2013

  • 一类非凸、非光滑问题的交替方向乘子法及其在背景 / 前景提取中的应用

    本文针对图像科学中广泛使用的一类优化问题，基于 ADMM 算法，通过使用通用的双重步长方法、构建特殊的潜函数以及采用简单的初始化策略实现了非凸优化问题全局收敛和解决，并在实际应用中进行了比较实验，表明最优化效果良好。

    Jun, 2015

  • 应用于多面体约束函数的交替方向乘子法收敛证明

    我们证明了 Alternating Direction Method of Multipliers (ADMM) 收敛到最优的原始对偶解，假设成本函数 f (x)+g (y) 被限制在对点集 X 和 Y 上。

    Dec, 2011

  • 非凸组合问题的 Bregman 交替方向乘数法收敛性研究

    本文研究了一种名为 Bregman modification 的 ADMM 算法，在某些限定条件下证明了 BADMM 迭代序列能够收敛到相关增广拉格朗日函数的静止点，这为 ADMM 在非凸设置中的应用提供了可行性。

    Oct, 2014

  • 一种基于 Majorization Minimization 的统一交替方向乘子法

    提出了 Gauss-Seidel ADMMs 和 Jacobian ADMMs 框架及其收敛分析。我们展示了这些框架可以通过最小化可分离 majorant 替代加强本来只可以解决可分离问题的 ADMMs。我们还介绍了几种提高 ADMM 效率的技术，特别地，我们提出了 M-ADMM，它通过吸收 Gauss-Seidel ADMMs 的特点来缓解 Jacobian ADMMs 的缓慢收敛问题。在理论保证和数值实验方面，我们的新 ADMMs 表现优越。此外，我们还发布了一个工具箱，其中包含了很多压缩感知问题的高效 ADMMs 的实现。

    Jul, 2016