Jan, 2018

非凸情况下的近端交替方向乘子法：收敛性分析与速率

PDF
TL;DR提出了两个针对非凸情况的数值算法，用于快速解决优化问题。该算法基于可变度量介绍了近端项，这使得我们能够针对非凸结构优化问题构建新的近端分裂算法。在变量度量序列条件温和并且假设相关增广拉格朗日函数具有 Kurdyka-Lojasiewicz 性质的情况下，证明了该算法迭代可以收敛到 KKT 点，并获得了增广拉格朗日函数和迭代的收敛速度。
nonconvex optimizationproximal splitting algorithmskurdyka-lojasiewicz propertyaugmented lagrangianconvergence rates
发现论文，激发创造
  • 线性约束非凸优化的乘子近端交替方向法

    本文提出了一种新的 proximal ADMM 算法，使用平滑后的原始迭代的序列并在每次迭代时向增广拉格朗日函数中引入一个二次近似项。该算法的迭代收敛到这个问题的一个站点，特别是当目标函数是二次函数时，证明算法的线性收敛性。

    Dec, 2018

  • 一种基于 Kurdyka-Lojasiewicz 不等式的非凸问题的近端交替最小化和投影方法

    研究交替近端最小化算法在非凸结构函数中的应用，证明其收敛性质，并提供压缩感知和秩降问题的具体应用。

    Jan, 2008

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

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

    Jun, 2015

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

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

    Aug, 2012

  • 一种带有不定后验项的线性约束凸组合优化的主导式 ADMM 算法

    本文提出了一种使用不确定的近似项的 ADMM 算法，以解决包含非光滑和光滑凸函数和线性约束的二块凸优化问题，并通过理论和数值实验证明了其全局收敛性和收敛速度。

    Dec, 2014

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

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

    Oct, 2014

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

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

    Aug, 2015

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

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

    Jun, 2015

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

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

    Oct, 2014

  • 具有线性收敛率的分散近端梯度算法

    本文研究了一类非光滑的分散式多智能体最优化问题，该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架，统一了许多现有的最先进的算法。我们在非光滑项存在的情况下，证明了所提出的方法向确切解的线性收敛。此外，对于更一般的具有代理特定非光滑术语的问题类，我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例，展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。

    Sep, 2019