A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees

Abstract

In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an (,)-SOSP of this problem. Our method is not only implementable, but also achieves an iteration complexity of O(^-3/2), which matches the best known iteration complexity of second-order methods for finding an (,)-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of O(^-3/2) Cholesky factorizations and O(^-3/2 ,^-1/4\) other fundamental operations, is also established for our method.

Tasks

Reproductions