# A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

arXiv: https://arxiv.org/abs/2301.03139 · HTML: https://mlsanity.com/paper/2301.03139/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 72 references that are in the map.
- First posted on arXiv 9 Jan 2023.

## Builds on (most cited first, 22 of 22)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints](https://mlsanity.com/paper/1908.00131/) (2019)
- [Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization](https://mlsanity.com/paper/1706.03131/) (2017)
- [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization](https://mlsanity.com/paper/1906.05622/) (2019)
- [Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization](https://mlsanity.com/paper/1912.04365/) (2019)
- [Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary](https://mlsanity.com/paper/1702.04300/) (2017)
- [A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees](https://mlsanity.com/paper/1904.03563/) (2019)
- [Complexity and performance of an Augmented Lagrangian algorithm](https://mlsanity.com/paper/1907.02401/) (2019)
- [Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization](https://mlsanity.com/paper/1705.07285/) (2017)
- [Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization](https://mlsanity.com/paper/1707.00337/) (2017)
- [Evaluation complexity bounds for smooth constrained nonlinear optimisation using scaled KKT conditions, high-order models and the criticality measure chi](https://mlsanity.com/paper/1705.04895/) (2017)
- [Sparse Recovery via Partial Regularization: Models, Theory and Algorithms](https://mlsanity.com/paper/1511.07293/) (2015)

## Built on by (most cited first, 6 of 6)

- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)
- [Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessian](https://mlsanity.com/paper/2311.13094/) (2023)
- [A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization](https://mlsanity.com/paper/2412.14488/) (2024)

## Abstract (arXiv)

In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of widetildecal O(ε-7/2) and an operation complexity of widetildecal O(ε-7/2minn,ε-3/4) for finding an (ε,√ε)-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method [60]. Besides, we show that it has a total inner iteration complexity of widetildecal O(ε-11/2) and an operation complexity of widetildecal O(ε-11/2minn,ε-5/4) when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the ones in [56,60].