SNAP algorithm finds approximate SOSPs for non-convex linearly constrained problems in O(1/ε^{2.5}) iterations with polynomial per-iteration complexity by leveraging strict complementarity on generic instances.
A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Non-Convex Optimization
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Motivated by TRACE algorithm [Curtis et al. 2017], we propose a trust region algorithm for finding second order stationary points of a linearly constrained non-convex optimization problem. We show the convergence of the proposed algorithm to (\epsilon_g, \epsilon_H)-second order stationary points in \widetilde{\mathcal{O}}(\max{\epsilon_g^{-3/2}, \epsilon_H^{-3}}) iterations. This iteration complexity is achieved for general linearly constrained optimization without cubic regularization of the objective function.
fields
math.OC 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems
SNAP algorithm finds approximate SOSPs for non-convex linearly constrained problems in O(1/ε^{2.5}) iterations with polynomial per-iteration complexity by leveraging strict complementarity on generic instances.