论文标题
不平等问题的统一原始偶算法框架
A Unified Primal-Dual Algorithm Framework for Inequality Constrained Problems
论文作者
论文摘要
在本文中，我们提出了一个基于增强的拉格朗日功能的统一原始偶算法框架，以解决圆锥不平等约束的复合凸问题。新的框架用途广泛。首先，它不仅涵盖了许多现有的算法，例如PDHG，Chambolle-Pock（CP），GDA，OGDA和线性化ALM，而且还指导我们设计一种称为Simi-oggda（SOGDA）的新有效算法。其次，它使我们能够研究增强惩罚项在收敛分析中的作用。有趣的是，正确选择的惩罚不仅可以提高上述方法的数值性能，而且从理论上讲可以使PDHG和SOGDA等算法的收敛性。在正确设计的步进尺寸和罚款项下，我们的统一框架保留了$ \ Mathcal {o}（1/n）$ ergodic收敛性，同时不需要有关最佳Lagrangian乘数幅度的任何先验知识。在适当的条件下，还可以获得仿射平等约束问题的线性收敛率。最后，关于线性编程，$ \ ell_1 $最小化问题和多块基础追踪问题的数值实验证明了我们方法的效率。
In this paper, we propose a unified primal-dual algorithm framework based on the augmented Lagrangian function for composite convex problems with conic inequality constraints. The new framework is highly versatile. First, it not only covers many existing algorithms such as PDHG, Chambolle-Pock (CP), GDA, OGDA and linearized ALM, but also guides us to design a new efficient algorithm called Simi-OGDA (SOGDA). Second, it enables us to study the role of the augmented penalty term in the convergence analysis. Interestingly, a properly selected penalty not only improves the numerical performance of the above methods, but also theoretically enables the convergence of algorithms like PDHG and SOGDA. Under properly designed step sizes and penalty term, our unified framework preserves the $\mathcal{O}(1/N)$ ergodic convergence while not requiring any prior knowledge about the magnitude of the optimal Lagrangian multiplier. Linear convergence rate for affine equality constrained problem is also obtained given appropriate conditions. Finally, numerical experiments on linear programming, $\ell_1$ minimization problem, and multi-block basis pursuit problem demonstrate the efficiency of our methods.
