Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00373586" target="_blank" >RIV/68407700:21230/24:00373586 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1137/22M1529762" target="_blank" >https://doi.org/10.1137/22M1529762</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/22M1529762" target="_blank" >10.1137/22M1529762</a>
Alternative languages
Result language
angličtina
Original language name
Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM Journal on Optimization
ISSN
1052-6234
e-ISSN
1095-7189
Volume of the periodical
34
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
26
Pages from-to
1-26
UT code for WoS article
001174991600009
EID of the result in the Scopus database
2-s2.0-85182510299