Exact algorithms for semidefinite programs with degenerate feasible set

DOI10.1145/3208976.3209022zbMATH Open1460.90128arXiv1802.02834OpenAlexW3108376486WikidataQ131130148 ScholiaQ131130148MaRDI QIDQ2229751FDOQ2229751

Mohab Safey El Din, Simone Naldi, Didier Henrion

Publication date: 18 February 2021

Published in: Journal of Symbolic Computation, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: Given symmetric matrices $A_0,A_1,ldots,A_n$ of size $m$ with rational entries, the set of real vectors $x=(x_1,ldots,x_n)$ such that the matrix $A_0+x_1{A}_1+cdots+x_n{A}_n$ 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.

Full work available at URL: https://arxiv.org/abs/1802.02834

Recommendations

• Exact algorithms for semidefinite programs with degenerate feasible set
• Exact algorithms for linear matrix inequalities
• Solving rank-constrained semidefinite programs in exact arithmetic
• Solving rank-constrained semidefinite programs in exact arithmetic
• On the complexity of semidefinite programs

zbMATH Keywords

polynomial optimizationsemidefinite programminghomotopyexact computation

Mathematics Subject Classification ID

Linear programming (90C05) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Interior-point methods (90C51) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Semialgebraic sets and related spaces (14P10) Solving polynomial systems; resultants (13P15)

Cites Work

• FGb: A Library for Computing Gröbner Bases
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear Matrix Inequalities in System and Control Theory
• Title not available (Why is that?)
• An exact duality theory for semidefinite programming and its complexity implications
• Moments, positive polynomials and their applications
• Algorithms in real algebraic geometry
• Computing parametric geometric resolutions
• A Gröbner free alternative for polynomial system solving
• Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
• The algebraic degree of semidefinite programming
• Regularizing the abstract convex program
• Introduction to Semidefinite, Conic and Polynomial Optimization
• Finding at least one point in each connected component of a real algebraic set defined by a single equation
• Sums of squares of polynomials with rational coefficients
• Title not available (Why is that?)
• Testing sign conditions on a multivariate polynomial and applications
• Title not available (Why is that?)
• Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
• On the complexity of semidefinite programs
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Real root finding for determinants of linear matrices
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Exact algorithms for linear matrix inequalities
• Intrinsic complexity estimates in polynomial optimization
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Computing rational solutions of linear matrix inequalities
• Improving root separation bounds
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Exact algorithms for semidefinite programs with degenerate feasible set
• Solving rank-constrained semidefinite programs in exact arithmetic
• Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic

Cited In (6)

• Encoding inductive invariants as barrier certificates: synthesis via difference-of-convex programming
• Exact algorithms for semidefinite programs with degenerate feasible set
• On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate
• Estimation under group actions: recovering orbits from invariants
• An effective decision method for semidefinite polynomials
• Exact Semidefinite Programming Bounds for Packing Problems

Uses Software

• FGb
• Kronecker
• SeDuMi
• SDPT3
• Mosek
• SPECTRA

This page was built for publication: Exact algorithms for semidefinite programs with degenerate feasible set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229751)