Exact algorithms for semidefinite programs with degenerate feasible set

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00348008" target="_blank" >RIV/68407700:21230/21:00348008 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.jsc.2020.11.001" target="_blank" >https://doi.org/10.1016/j.jsc.2020.11.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jsc.2020.11.001" target="_blank" >10.1016/j.jsc.2020.11.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Exact algorithms for semidefinite programs with degenerate feasible set

Popis výsledku v původním jazyce

Given symmetric matrices A0,A1,...,An of size m with rational entries, the set of real vectors x=(x1,...,xn) such that the matrix A0+x1A1++xnAn has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed.

Název v anglickém jazyce

Exact algorithms for semidefinite programs with degenerate feasible set

Popis výsledku anglicky

Given symmetric matrices A0,A1,...,An of size m with rational entries, the set of real vectors x=(x1,...,xn) such that the matrix A0+x1A1++xnAn has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

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

Journal of Symbolic Computation

ISSN

0747-7171

e-ISSN

1095-855X

Svazek periodika

104

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

18

Strana od-do

942-959

Kód UT WoS článku

000598670000041

EID výsledku v databázi Scopus

2-s2.0-85097046553