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


Files produced by the author(s)



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⟩



Record views


Files downloads