Lidé
MSc. Antonio Bellon, Ph.D.
Všechny publikace
Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Autoři: MSc. Antonio Bellon, Ph.D., Dressler, M., Dr. Vyacheslav Kungurtsev, Ph.D., Mgr. Jakub Mareček, Ph.D., Uschmajew, A.
- Publikace: SIAM Journal on Optimization. 2024, 34(1), 1-26. ISSN 1052-6234.
- Rok: 2024
- DOI: 10.1137/22M1529762
- Odkaz: https://doi.org/10.1137/22M1529762
- Pracoviště: Katedra počítačů, Centrum umělé inteligence, Intelligent Data Analysis
-
Anotace:
We present an online algorithm for time-varying semidefinite programs (TV-SDPs), based on the tracking of the solution trajectory of a low-rank matrix factorization, also known as the Burer–Monteiro factorization, in a path-following procedure. There, a predictor-corrector algorithm solves a sequence of linearized systems. This requires the introduction of a horizontal space constraint to ensure the local injectivity of the low-rank factorization. The method produces a sequence of approximate solutions for the original TV-SDP problem, for which we show that they stay close to the optimal solution path if properly initialized. Numerical experiments for a time-varying max-cut SDP relaxation demonstrate the computational advantages of the proposed method for tracking TV-SDPs in terms of runtime compared to off-the-shelf interior-point methods.