Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Optimization

ISSN

1052-6234

e-ISSN

1095-7189

Svazek periodika

34

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

26

Strana od-do

1-26

Kód UT WoS článku

001174991600009

EID výsledku v databázi Scopus

2-s2.0-85182510299