26. Barrier Algorithms for Constrained Non-Convex Optimization
Invited abstract in session WE-6: Higher-order Methods in Mathematical Programming I, stream Challenges in nonlinear programming.
Wednesday, 14:10 - 15:50Room: M:H
Authors (first author is the speaker)
| 1. | Pavel Dvurechensky
|
| Weierstrass Institute for Applied Analysis and Stochastics | |
| 2. | Mathias Staudigl
|
| Department of Mathematics, Universität Mannheim |
Abstract
A key problem in mathematical imaging, signal processing and computational statistics is the minimization of non-convex objective functions that may be non-differentiable at the relative boundary of the feasible set. This paper proposes a new family of first- and second-order interior-point methods for non-convex optimization problems with linear and set constraints, combining self-concordant barriers with quadratic and cubic regularization respectively. Our approach is based on a potential-reduction mechanism and, under the Lipschitz continuity of the corresponding derivative with respect to the local barrier-induced norm, attains a suitably defined class of approximate first- or second-order KKT points with worst-case iteration complexity typical for unconstrained optimization. Based on these findings, we develop also new path-following schemes attaining the same complexity, modulo adjusting constants.
Keywords
- Complexity and efficiency of optimization algorithms
- SS - Advances in Nonlinear Optimization and Applications
- SS - Conic Optimization and Applications
Status: accepted
Back to the list of papers