Skip to Main content Skip to Navigation
Journal articles

Exact algorithms for semidefinite programs with degenerate feasible set

Abstract : Given symmetric matricesA0, A1, . . . , Anof sizemwith rational entries, theset of real vectorsx= (x1, . . . , xn) such that the matrixA0+x1A1+···+xnAnhas non-negative eigenvalues is called a spectrahedron. Minimizationof linear functions over spectrahedra is called semidefinite programming.Such problems appear frequently in control theory and real algebra, espe-cially in the context of nonnegativity certificates for multivariate polynomi-als based on sums of squares.Numerical software for semidefinite programming are mostlybased oninterior point methods, assuming non-degeneracy properties such as the ex-istence of an interior point in the spectrahedron. In this paper, we designan exact algorithm based on symbolic homotopy for solving semidefiniteprograms without assumptions on the feasible set, and we analyze its com-plexity. Because of the exactness of the output, it cannot compete withnumerical routines in practice. However, we prove that solving such prob-lems can be done in polynomial time if eithernormis fixed.
Complete list of metadata

https://hal.laas.fr/hal-03121215
Contributor : Laas Hal-Laas <>
Submitted on : Tuesday, January 26, 2021 - 11:25:17 AM
Last modification on : Tuesday, March 23, 2021 - 9:28:03 AM

File

Exact-algorithm-V3-JSC.pdf
Files produced by the author(s)

Identifiers

Citation

Didier Henrion, Simone Naldi, Mohab Safey El Din. Exact algorithms for semidefinite programs with degenerate feasible set. Journal of Symbolic Computation, Elsevier, 2021, 104, pp.942 - 959. ⟨10.1016/j.jsc.2020.11.001⟩. ⟨hal-03121215⟩

Share

Metrics

Record views

142

Files downloads

55