Barrier Algorithms for Constrained Non-Convex Optimization
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.
Cite
Text
Dvurechensky and Staudigl. "Barrier Algorithms for Constrained Non-Convex Optimization." International Conference on Machine Learning, 2024.Markdown
[Dvurechensky and Staudigl. "Barrier Algorithms for Constrained Non-Convex Optimization." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/dvurechensky2024icml-barrier/)BibTeX
@inproceedings{dvurechensky2024icml-barrier,
title = {{Barrier Algorithms for Constrained Non-Convex Optimization}},
author = {Dvurechensky, Pavel and Staudigl, Mathias},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {12190-12214},
volume = {235},
url = {https://mlanthology.org/icml/2024/dvurechensky2024icml-barrier/}
}