Fast Augmented Lagrangian Method in the convex regime with convergence guarantees for the iterates

Area of Science:

• Optimization Theory
• Applied Mathematics
• Numerical Analysis

Background:

• Minimizing convex functions with linear constraints is a fundamental problem in optimization.
• Existing fast gradient methods often require strong convexity assumptions for guaranteed convergence of iterates.

Purpose of the Study:

• To develop and analyze a novel inertial algorithm for convex optimization under linear equality constraints.
• To establish convergence rates and prove the convergence of primal-dual iterates without strong convexity.

Main Methods:

• Discretization of a second-order primal-dual dynamical system with vanishing damping.
• Formulation using the Augmented Lagrangian.
• Analysis of inertial parameters including Nesterov, Chambolle-Dossal, and Attouch-Cabot rules.

Main Results:

• Achieved convergence rates of O(1/k^2) for primal-dual gap, feasibility, and objective function value.
• Proved convergence of primal-dual iterates for Chambolle-Dossal and Attouch-Cabot rules.
• Demonstrated convergence without requiring strong convexity, a novel result for fast algorithms in this setting.

Conclusions:

• The proposed inertial algorithm is effective for linearly constrained convex optimization.
• The algorithm achieves optimal convergence rates and guarantees iterate convergence under general conditions.
• This work advances the theory of fast gradient methods for constrained optimization problems.