Skip to yearly menu bar Skip to main content


Poster

Barrier Algorithms for Constrained Non-Convex Optimization

Pavel Dvurechenskii · Mathias Staudigl

Hall C 4-9 #1314

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(ε2) (first-order) and O(ε3/2) (second-order), respectively.

Chat is not available.