Characterizing bad semidefinite programs: normal forms and short proofs
From MaRDI portal
Publication:5243181
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5773482 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- scientific article; zbMATH DE number 1534289 (Why is no real title available?)
- scientific article; zbMATH DE number 6872015 (Why is no real title available?)
- scientific article; zbMATH DE number 1821400 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A mathematical view of interior-point methods in convex optimization
- A structural geometrical analysis of weakly infeasible SDPS
- An exact duality theory for semidefinite programming and its complexity implications
- An exact duality theory for semidefinite programming based on sums of squares
- Asymptotes and Projections of Convex Sets.
- Bad semidefinite programs: they all look the same
- Cones of diagonally dominant matrices
- Convex Analysis
- Convex Computation of the Region of Attraction of Polynomial Control Systems
- Deciding polyhedrality of spectrahedra
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- Facial reduction algorithms for conic optimization problems
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- On the Closedness of the Linear Image of a Closed Convex Cone
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Regularizing the abstract convex program
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Semidefinite optimization
- Set intersection theorems and existence of optimal solutions
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Stability of closedness of convex cones under linear mappings
- Stability of closedness of convex cones under linear mappings. II
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Strong duality and minimal representations for cone optimization
- Strong duality in conic linear programming: facial reduction and extended duals
- The algebraic degree of semidefinite programming
- What is \dots a spectrahedron?
Cited in
(10)- Bad projections of the PSD cone
- Bad semidefinite programs: they all look the same
- An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone
- Solving SDP completely with an interior point oracle
- A simplified treatment of Ramana's exact dual for semidefinite programming
- On the uniform duality in copositive optimization
- Understanding badly and well-behaved linear matrix inequalities via semi-infinite optimization
- scientific article; zbMATH DE number 7476198 (Why is no real title available?)
- How Do Exponential Size Solutions Arise in Semidefinite Programming?
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
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)
