Certifying solutions of degenerate semidefinite programs

DOI10.1137/24M1664691MaRDI QIDQ6952578zbMATH OpenFDO

Authors Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata

Publication date 27 July 2025

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1664691

zbMATH Keywords

facial reductionlinear matrix inequalitiesspectrahedrasymbolic-numeric algorithmsweak feasibility

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22)

Cites work

• Algorithms in real algebraic geometry
• An exact duality theory for semidefinite programming based on sums of squares
• Bad semidefinite programs: they all look the same
• Computing sum of squares decompositions with rational coefficients
• Conic programming: infeasibility certificates and projective geometry
• Exact algorithms for linear matrix inequalities
• Exact algorithms for semidefinite programs with degenerate feasible set
• Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
• Exact Semidefinite Programming Bounds for Packing Problems
• Facial reduction algorithms for conic optimization problems
• Generalized polar varieties: geometry and algorithms
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 3728055 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Linear Sections of Determinantal Varieties
• msolve. A library for solving polynomial systems
• Numerical algebraic geometry and semidefinite programming
• Numerically solving polynomial systems with Bertini
• On symmetric and skew-symmetric determinantal varieties
• On the existence and computation of rank-revealing LU factorizations
• On the Generation of Positivstellensatz Witnesses in Degenerate Cases
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Performance of first-order methods for smooth convex minimization: a novel approach
• Rank revealing Gaussian elimination by the maximum volume concept
• Real root finding for determinants of linear matrices
• Real root finding for low rank linear matrices
• Real World Verification
• Regularizing the abstract convex program
• Semidefinite programming
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
• Solving rank-constrained semidefinite programs in exact arithmetic
• Solving SDP completely with an interior point oracle
• Strong duality in conic linear programming: facial reduction and extended duals
• The algebraic degree of semidefinite programming
• Validating numerical semidefinite programming solvers for polynomial invariants
• Verifying Nonlinear Real Formulas Via Sums of Squares

This page was built for publication: Certifying solutions of degenerate semidefinite programs

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