A Fixed-Penalty Linearized Augmented Lagrangian Method with Classical Multiplier Updates

Abstract

Augmented Lagrangian methods are effective for nonlinear equality-constrained optimization, but solving their nonlinear primal subproblems can be expensive. For smooth nonconvex problems with deterministic or stochastic objectives, we propose a nonlinear-residual linearized augmented Lagrangian method (NR-LALM) that replaces this subproblem by a regularized Gauss-Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual. The resulting step is computed from one symmetric positive-definite linear system, but the mismatch between the linearized primal model and the nonlinear-residual update produces a quadratic constraint-linearization error in the multiplier identity. We show that this error can be controlled under local regularity; multiplier boundedness and trajectory localization are derived rather than assumed. With fixed, accuracy-independent parameters, deterministic NR-LALM finds an $\varepsilon$-approximate Karush-Kuhn-Tucker (KKT) pair in $O(\varepsilon^{-2})$ iterations and first-order oracle evaluations. For stochastic objectives, a projected stochastic path-integrated differential estimator with safeguarded restarts requires, in expectation, $O(\varepsilon^{-3})$ stochastic-gradient evaluations and $O(\varepsilon^{-2})$ constraint and Jacobian evaluations. Compactness and a Kurdyka-Lojasiewicz condition further yield finite-length convergence of the deterministic primal-dual sequence. An optional minimum-norm second-order correction reduces the constraint-linearization error from second to fourth order without changing the complexity orders. All theoretical results are formalized in Lean 4. Numerical experiments confirm the predicted error orders and show favorable performance on high-dimensional deterministic and stochastic problems.

Disclosure

“edicted orders and favorable performance. The Lean formalization and public code support independent checking of the theory and experiments. Inequalities, inexact solves, adaptive parameters, and globalization remain open. Acknowledgments Generative AI assisted manuscript preparation and parts of the mathematical and computational work. The authors verified all results and assume responsibility for all content. References [1] A. Alacaoglu and S. J. Wright. Complexity of single loop al”

PDF page 24

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:13:15.710019Z

Structural counts