Characterizing bad semidefinite programs: normal forms and short proofs

DOI10.1137/17M1140844zbMATH Open1430.90459arXiv1709.02423OpenAlexW2988743386WikidataQ113779121 ScholiaQ113779121MaRDI QIDQ5243181FDOQ5243181

Authors: Gábor Pataki 

Publication date: 15 November 2019

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

Abstract: Semidefinite programs (SDPs) -- some of the most useful and versatile optimization problems of the last few decades -- are often pathological: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are both theoretically interesting and often impossible to solve; yet, the pathological SDPs in the literature look strikingly similar. Based on our recent work cite{Pataki:17} we characterize pathological semidefinite systems by certain {em excluded matrices}, which are easy to spot in all published examples. Our main tool is a normal (canonical) form of semidefinite systems, which makes their pathological behavior easy to verify. The normal form is constructed in a surprisingly simple fashion, using mostly elementary row operations inherited from Gaussian elimination. The proofs are elementary and can be followed by a reader at the advanced undergraduate level. As a byproduct, we show how to transform any linear map acting on symmetric matrices into a normal form, which allows us to quickly check whether the image of the semidefinite cone under the map is closed. We can thus introduce readers to a fundamental issue in convex analysis: the linear image of a closed convex set may not be closed, and often simple conditions are available to verify the closedness, or lack of it.

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

Recommendations

• Bad semidefinite programs: they all look the same
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• Semidefinite Programming
• An exact duality theory for semidefinite programming and its complexity implications
• Semidefinite optimization

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• Title not available (Why is that?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Semidefinite Programming
• Convex Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• An exact duality theory for semidefinite programming and its complexity implications
• Strong duality and minimal representations for cone optimization
• A mathematical view of interior-point methods in convex optimization
• Convex Computation of the Region of Attraction of Polynomial Control Systems
• Semidefinite optimization
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Stability of closedness of convex cones under linear mappings
• The algebraic degree of semidefinite programming
• What is \dots a spectrahedron?
• Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
• Facial reduction algorithms for conic optimization problems
• Regularizing the abstract convex program
• Title not available (Why is that?)
• Set intersection theorems and existence of optimal solutions
• An exact duality theory for semidefinite programming based on sums of squares
• On the Closedness of the Linear Image of a Closed Convex Cone
• Title not available (Why is that?)
• Cones of diagonally dominant matrices
• Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
• Title not available (Why is that?)
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• A STRUCTURAL GEOMETRICAL ANALYSIS OF WEAKLY INFEASIBLE SDPS
• Strong duality in conic linear programming: facial reduction and extended duals
• Asymptotes and Projections of Convex Sets.
• Bad Semidefinite Programs: They All Look the Same
• Title not available (Why is that?)
• Deciding polyhedrality of spectrahedra

Cited In (8)

• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Bad projections of the PSD cone
• How Do Exponential Size Solutions Arise in Semidefinite Programming?
• Title not available (Why is that?)
• On the uniform duality in copositive optimization
• Understanding badly and well-behaved linear matrix inequalities via semi-infinite optimization
• A simplified treatment of Ramana's exact dual for semidefinite programming
• Solving SDP completely with an interior point oracle

Uses Software

• Sieve-SDP
• frlib

This page was built for publication: Characterizing bad semidefinite programs: normal forms and short proofs

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