Convex majorization methods for nonconvex constrained problems achieve O(ε^{-(κ+1)/κ}) iteration complexity under Hölderian gradients, with a second-order variant reaching approximate second-order stationarity in O(1/ε1+1/ε2) subproblem solves.
Barrier Algorithms for Constrained Non-Convex Optimization
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper we theoretically show that interior-point methods based on self-concordant barriers possess favorable global complexity beyond their standard application area of convex optimization. To do that we propose first- and second-order methods for non-convex optimization problems with general convex set constraints and linear constraints. Our methods attain a suitably defined class of approximate first- or second-order KKT points with the worst-case iteration complexity similar to unconstrained problems, namely $O(\varepsilon^{-2})$ (first-order) and $O(\varepsilon^{-3/2})$ (second-order), respectively.
citation-role summary
background 1
citation-polarity summary
fields
math.OC 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Complexity Analysis of Convex Majorization Schemes for Nonconvex Constrained Optimization
Convex majorization methods for nonconvex constrained problems achieve O(ε^{-(κ+1)/κ}) iteration complexity under Hölderian gradients, with a second-order variant reaching approximate second-order stationarity in O(1/ε1+1/ε2) subproblem solves.