Exact algorithms for semidefinite programs with degenerate feasible set
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Exact algorithms for semidefinite programs with degenerate feasible set
Original language description
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.
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
10102 - Applied mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
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
Journal of Symbolic Computation
ISSN
0747-7171
e-ISSN
1095-855X
Volume of the periodical
104
Issue of the periodical within the volume
May
Country of publishing house
GB - UNITED KINGDOM
Number of pages
18
Pages from-to
942-959
UT code for WoS article
000598670000041
EID of the result in the Scopus database
2-s2.0-85097046553