Fast Augmented Lagrangian Method in the convex regime with convergence guarantees for the iterates
针对线性等式约束下梯度Lipschitz连续的凸函数最小化问题，提出一种惯性算法，该算法源自二阶原始对偶动力系统的离散化，并证明在一般惯性参数设置下原始对偶间隙、可行性度量和目标函数值均达到O(1/k^2)收敛率，且迭代序列收敛到原始对偶解。
Abstract This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Boţ and Nguyen (J. Differential Equations 303:369–406, 2021), and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we consider for the inertial parameters covers the three classical rules by Nesterov, Chambolle–Dossal and Attouch–Cabot used in the literature to formulate fast gradient methods. For these rules, we obtain in the convex regime convergence rates of order $${\mathcal {O}}\left( 1/k^{2} \right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mfenced> </mml:mrow> </mml:math> for the primal-dual gap, the feasibility measure, and the objective function value. In addition, we prove that the generated sequence of primal-dual iterates converges to a primal-dual solution in a general setting that covers the two latter rules. This is the first result which provides the convergence of the sequence of iterates generated by a fast algorithm for linearly constrained convex optimization problems without additional assumptions such as strong convexity. We also emphasize that all convergence results of this paper are compatible with the ones obtained in Boţ and Nguyen (J. Differential Equations 303:369–406, 2021) in the continuous setting.