Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs

DOI10.1137/17M1140844zbMath1430.90459arXiv1709.02423OpenAlexW2988743386WikidataQ113779121 ScholiaQ113779121MaRDI QIDQ5243181

Gábor Pataki

Publication date: 15 November 2019

Published in: SIAM Review (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingdualityduality gappathological semidefinite programsclosedness of the linear image of the semidefinite cone

Mathematics Subject Classification ID

Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Convex functions and convex programs in convex geometry (52A41) Inequalities and extremum problems involving convexity in convex geometry (52A40) Duality theory (optimization) (49N15)

Related Items (6)

Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ A simplified treatment of Ramana's exact dual for semidefinite programming ⋮ How Do Exponential Size Solutions Arise in Semidefinite Programming? ⋮ Unnamed Item ⋮ Bad projections of the PSD cone ⋮ Solving SDP completely with an interior point oracle

Uses Software

• Sieve-SDP
• frlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facial reduction algorithms for conic optimization problems
• The algebraic degree of semidefinite programming
• Set intersection theorems and existence of optimal solutions
• Regularizing the abstract convex program
• 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
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Cones of diagonally dominant matrices
• Strong duality and minimal representations for cone optimization
• Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Lectures on Modern Convex Optimization
• WHAT IS...a Spectrahedron?
• Deciding Polyhedrality of Spectrahedra
• Bad Semidefinite Programs: They All Look the Same
• Convex Computation of the Region of Attraction of Polynomial Control Systems
• Semidefinite optimization
• Semidefinite Programming
• Semidefinite Optimization and Convex Algebraic Geometry
• An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
• On the Closedness of the Linear Image of a Closed Convex Cone
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• A STRUCTURAL GEOMETRICAL ANALYSIS OF WEAKLY INFEASIBLE SDPS
• Convex Analysis
• Asymptotes and Projections of Convex Sets.
• Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals

This page was built for publication: Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs