# A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 78 references that are in the map.
- First posted on arXiv 10 Jan 2023.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (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)
- [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)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [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)
- [NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization](https://mlsanity.com/paper/1712.01033/) (2017)
- [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)
- [Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian](https://mlsanity.com/paper/2204.01448/) (2022)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization](https://mlsanity.com/paper/1705.07285/) (2017)
- [Hessian barrier algorithms for non-convex conic optimization](https://mlsanity.com/paper/2111.00100/) (2021)
- [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)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)

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

- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)

## Abstract (arXiv)

In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under some mild assumptions, we show that our method enjoys a total inner iteration complexity of widetildecal O(ε-11/2) and an operation complexity of widetildecal O(ε-11/2minn,ε-5/4) for finding an (ε,√ε)-SOSP of general nonconvex conic optimization with high probability. Moreover, under a constraint qualification, these complexity bounds are improved to widetildecal O(ε-7/2) and widetildecal O(ε-7/2minn,ε-3/4), respectively. To the best of our knowledge, this is the first study on the complexity of finding an approximate SOSP of general nonconvex conic optimization. Preliminary numerical results are presented to demonstrate superiority of the proposed method over first-order methods in terms of solution quality.