2022/07/12 by Chuanjiang He, Zhaosong Lu, He, Chuan +1 · 1 citation
Computer Science · Engineering · Mathematics · #49M05 #49M15 #65F10 #90C06 #90C60 #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2207.05697
openalex publication_date 2022/07/12 · openalex created_date 2022/07/15 · openalex updated_date 2026/07/28
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 \cal 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 \cal O(ε-3/2) Cholesky factorizations and \widetilde\cal O(ε-3/2min\n,ε-1/4\) other fundamental operations, is also established for our method.