22. A conditional gradient homotopy method with applications to Semidefinite Programming
Invited abstract in session TB-6: Advances in Semi-Definite Programming, stream Challenges in nonlinear programming.
Thursday, 10:05 - 11:20Room: M:H
Authors (first author is the speaker)
| 1. | Mathias Staudigl
|
| Department of Mathematics, Universität Mannheim | |
| 2. | Pavel Dvurechensky
|
| Weierstrass Institute for Applied Analysis and Stochastics, Berlin | |
| 3. | Shimrit Shtern
|
| Industrial Engineering and Management, Technion-Israel Institute of Technology |
Abstract
We propose a new homotopy-based conditional gradient method for solving convex opti- mization problems with a large number of simple conic constraints. Instances of this template naturally appear in semidefinite programming problems arising as convex relaxations of com- binatorial optimization problems. Our method is a double-loop algorithm in which the conic constraint is treated via a self-concordant barrier, and the inner loop employs a conditional gradient algorithm to approximate the analytic central path, while the outer loop updates the accuracy imposed on the temporal solution and the homotopy parameter. Our theoretical it- eration complexity is competitive when confronted to state-of-the-art SDP solvers, with the decisive advantage of cheap projection-free subroutines. Preliminary numerical experiments are provided for illustrating the practical performance of the method.
Keywords
- Conic and semidefinite optimization
- Complexity and efficiency of optimization algorithms
- SS - Semidefinite Optimization
Status: accepted
Back to the list of papers