一种具有大步长的原始 - 对偶算法的新收敛分析
在这篇文章中,我们提出了一种新的原始 - 对偶算法,用于最小化具有 Lipschitz 连续梯度的可微下凸函数 $f$,下半连续的凸函数 $g$ 和线性算子 $A$ 的 $h (Ax)$ 的总和,证明了此算法的收敛性,并比较了其与其他多种算法在参数可接受范围和迭代代价方面的优点。
Nov, 2016
透过所谓的斜弱 Minty 条件,提供用于具有不同程度的(非)单调性问题的收敛结果。我们的研究结果表明,步长和松弛参数范围不仅取决于线性映射的范数,还取决于其其他奇异值。此外,在非单调设置中,除了 CPA 的经典步长条件外,还需要额外的步长和松弛参数界限。然而,在强单调设置下,允许松弛参数超过 2 的经典上界。此外,当个别算子属于最近引入的半单调算子类时,我们得到了足够的收敛条件。由于此类算子包括许多传统算子类,如(假设)- 和共(假设)单调算子,因此此分析恢复并扩展了 CPA 的现有结果。我们提供了几个示例,以演示和建立所提步长范围的紧致性。
Dec, 2023
本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
本文介绍了多步优化算法的收敛加速方案,并使用 Chebyshev 问题模拟了迭代过程中的行为,同时讨论了该方案在原始 - 对偶算法中的应用,并在逻辑回归问题中进行了数值实验。
Oct, 2018
本文研究了一类非光滑的分散式多智能体最优化问题,该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架,统一了许多现有的最先进的算法。我们在非光滑项存在的情况下,证明了所提出的方法向确切解的线性收敛。此外,对于更一般的具有代理特定非光滑术语的问题类,我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例,展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。
Sep, 2019
本文分析了新提出的 SPDHG 算法并给出了新的理论结果,证明了算法的收敛性和线性收敛性,同时提供数值实验证明了该算法在实际应用中的表现竞争力很强,特别是在支持向量机等问题上的实现效果不错。
Nov, 2019
基于最近的无线搜索自适应近端梯度方法,本文提出了 AdaPG^rπ 框架,通过提供更大的步长策略和改进的下界,统一和扩展了现有的结果。讨论了参数 π 和 r 的不同选择,并通过数值模拟证明了所得方法的有效性。为了更好地理解基本理论,还建立了一个允许时变参数的更一般的收敛性设置。最后,通过探索对偶设置,提出了一种自适应交替最小化算法。这种算法不仅包含了额外的适应性,而且扩展了其适用性,超出了标准强凸设置。
Nov, 2023
提出了两个针对非凸情况的数值算法,用于快速解决优化问题。该算法基于可变度量介绍了近端项,这使得我们能够针对非凸结构优化问题构建新的近端分裂算法。在变量度量序列条件温和并且假设相关增广拉格朗日函数具有 Kurdyka-Lojasiewicz 性质的情况下,证明了该算法迭代可以收敛到 KKT 点,并获得了增广拉格朗日函数和迭代的收敛速度。
Jan, 2018
该论文介绍了一种 V~u-Condat 算法的坐标下降版本,该算法可以解决具有可微函数、约束以及非可分、非可导的正则化器的优化问题,并且在更广泛的参数范围内比之前的方法产生了更好的收敛性能。
Aug, 2015
本文提出了一种用于解决多块凸优化问题的随机 Primal-Dual 近端块坐标更新框架,并使用其达到 $O (1/t)$ 的收敛速度,且包含现有算法的特例,以及推广至解决随机编程的问题。
May, 2016