Exact algorithms for semidefinite programs with degenerate feasible set

DOI10.1016/j.jsc.2020.11.001zbMath1460.90128arXiv1802.02834OpenAlexW3108376486MaRDI QIDQ2229751

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)

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

zbMATH Keywords

semidefinite programminghomotopypolynomial optimizationexact computation

Mathematics Subject Classification ID

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

Related Items (5)

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

Uses Software

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

Cites Work

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

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