mlsanityData to 14 Oct 2026

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

arXiv 2301.04204 ↗First posted 10 Jan 2023math.OC cs.LG cs.NAcited by 2

Not on the map. Why?

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.

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

25 of 78 references.

References · 25

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  2. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  3. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  4. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  5. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  6. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  7. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  8. 2018A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimizationcited by 23
  9. 2014SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraintscited by 22
  10. 2016Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Stepcited by 18
  11. 2019Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraintscited by 17
  12. 2017Complexity analysis of second-order line-search algorithms for smooth nonconvex optimizationcited by 16
13 more
  1. 2019Polynomial time guarantees for the Burer-Monteiro methodcited by 12
  2. 2019On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimizationcited by 10
  3. 2019Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimizationcited by 10
  4. 2017NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimizationcited by 9
  5. 2017Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundarycited by 8
  6. 2019A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guaranteescited by 7
  7. 2022Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangiancited by 6
  8. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  9. 2017Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimizationcited by 5
  10. 2021Hessian barrier algorithms for non-convex conic optimizationcited by 5
  11. 2017Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimizationcited by 3
  12. 2017Evaluation complexity bounds for smooth constrained nonlinear optimisation using scaled KKT conditions, high-order models and the criticality measure chicited by 2
  13. 2022A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guaranteescited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1.

2 papers.

  1. 2023Federated Learning with Convex Global and Local Constraintscited by 4
  2. 2024Stochastic interior-point methods for smooth conic optimization with applicationscited by 1