We develop inexact augmented Lagrangian (AL) methods for linearly constrained convex composite optimization problems whose objective is the sum of a smooth convex function and a possibly nonsmooth closed proper convex function with compact domain. Unlike primal accuracy guarantees based on objective-value error, our methods target verifiable approximate KKT solutions. In the convex setting, we propose three inexact AL schemes with optimal primal-dual complexity \(\mathcal O(\epsilon^{-1})\), improving prior AL bounds such as \(\mathcal O(\epsilon^{-4/3})\), \(\mathcal O(\epsilon^{-7/4})\), and \(\mathcal O(\epsilon^{-2})\), and improving the \(\mathcal O(\epsilon^{-1}\log(\epsilon^{-1}))\) guarantees of proximal augmented Lagrangian (PAL) methods. Two of the three convex variants are parameter-free. We also establish non-ergodic convergence guarantees, including a stronger last-iterate guarantee for one variant. In the strongly convex setting, our methods achieve near-optimal complexity \(\mathcal O(\epsilon^{-1/2}\log(\epsilon^{-1}))\), with two parameter-free variants. Numerical experiments on six important problem classes, including elastic-net least-squares regression, group-sparse Huberized support vector machines, and a quantum semidefinite program (SDP), demonstrate substantial computational advantages of our inexact AL methods over a representative PAL method, with speedups frequently ranging from \(5\) to \(50\) times.
Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods
\(\)