An exact duality theory for semidefinite programming based on sums of squares
From MaRDI portal
Publication:5169680
Abstract: Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality is infeasible if and only if -1 lies in the quadratic module associated to it. We also present a new exact duality theory for semidefinite programming, motivated by the real radical and sums of squares certificates from real algebraic geometry.
Recommendations
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- A generalized Farkas lemma with a numerical certificate and linear semi-infinite programs with SDP duals
- An exact duality theory for semidefinite programming and its complexity implications
- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- scientific article; zbMATH DE number 5036103
Cited in
(31)- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- Conic programming: infeasibility certificates and projective geometry
- Bad projections of the PSD cone
- Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
- New examples of extremal positive linear maps
- Irreducible infeasible subsystems of semidefinite systems
- Noncommutative polynomials nonnegative on a variety intersect a convex set
- The tracial Hahn-Banach theorem, polar duals, matrix convex sets, and projections of free spectrahedra
- A simplified treatment of Ramana's exact dual for semidefinite programming
- Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
- Exact algorithms for linear matrix inequalities
- Bad semidefinite programs: they all look the same
- A note on a matrix version of the Farkas lemma
- Operator Positivstellensätze for noncommutative polynomials positive on matrix convex sets
- A real nullstellensatz for free modules
- Some recent developments in spectrahedral computation
- Constraint satisfaction problems over numeric domains
- Solving SDP completely with an interior point oracle
- Simultaneous diagonalization via congruence of Hermitian matrices: some equivalent conditions and a numerical solution
- Weak infeasibility in second order cone programming
- A matrix Positivstellensatz with lifting polynomials
- Characterizing bad semidefinite programs: normal forms and short proofs
- A semidefinite hierarchy for containment of spectrahedra
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- Certificates of primal or dual infeasibility in linear programming
- A practical approach to SOS relaxations for detecting quantum entanglement
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Convex representation of metabolic networks with Michaelis-Menten kinetics
- A distributional Farkas' lemma and moment optimization problems with no-gap dual semi-definite programs
- The truncated moment problem on curves y = q ( x ) and yx ℓ = 1
- Certifying solutions of degenerate semidefinite programs
This page was built for publication: An exact duality theory for semidefinite programming based on sums of squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169680)
