Convergence of Augmented Lagrangian Methods for Composite Optimization Problems

Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latter condition and a certain second-order sufficient condition, we are able to establish Q-linear convergence of the primal-dual sequence for an inexact version of the ALM for composite programs.

Funding: Research of the first author is partially supported by Singapore National Academy of Science via SASEAF Programme under the grant RIE2025 NRF International Partnership Funding Initiative. Research of the second author is partially supported by the National Science Foundation under the grant DMS 2108546.