A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
This addresses a foundational problem in optimization theory for researchers and practitioners, providing the first complexity analysis for approximate second-order stationary points in this setting, though it is incremental as it builds on existing barrier and Lagrangian methods.
The paper tackles the problem of finding approximate second-order stationary points for general nonconvex conic optimization with nonlinear equality and convex conic constraints, proposing a Newton-CG based barrier-augmented Lagrangian method that achieves total inner iteration complexities of $\widetilde{\cal O}(ε^{-11/2})$ and $\widetilde{\cal O}(ε^{-7/2})$ under different conditions, with preliminary numerical results showing superiority over first-order methods in solution quality.
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 $\widetilde{\cal O}(ε^{-11/2})$ and an operation complexity of $\widetilde{\cal O}(ε^{-11/2}\min\{n,ε^{-5/4}\})$ for finding an $(ε,\sqrtε)$-SOSP of general nonconvex conic optimization with high probability. Moreover, under a constraint qualification, these complexity bounds are improved to $\widetilde{\cal O}(ε^{-7/2})$ and $\widetilde{\cal O}(ε^{-7/2}\min\{n,ε^{-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.