Bad semidefinite programs: they all look the same
From MaRDI portal
Abstract: Conic linear programs, among them semidefinite programs, often behave pathologically: the optimal values of the primal and dual programs may differ, and may not be attained. We present a novel analysis of these pathological behaviors. We call a conic linear system {em badly behaved} if the value of is finite but the dual program has no solution with the same value for {em some} We describe simple and intuitive geometric characterizations of badly behaved conic linear systems. Our main motivation is the striking similarity of badly behaved semidefinite systems in the literature; we characterize such systems by certain {em excluded matrices}, which are easy to spot in all published examples. We show how to transform semidefinite systems into a canonical form, which allows us to easily verify whether they are badly behaved. We prove several other structural results about badly behaved semidefinite systems; for example, we show that they are in in the real number model of computing. As a byproduct, we prove that all linear maps that act on symmetric matrices can be brought into a canonical form; this canonical form allows us to easily check whether the image of the semidefinite cone under the given linear map is closed.
Recommendations
Cites work
- A complementarity partition theorem for multifold conic systems
- 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
- Closedness criteria for the image of a closed set by a inear operator
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Convex Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- Convex analysis and nonlinear optimization. Theory and examples
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- Facial reduction algorithms for conic optimization problems
- Facially exposed cones are not always nice
- Generating and measuring instances of hard semidefinite programs
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 3121286 (Why is no real title available?)
- scientific article; zbMATH DE number 5773482 (Why is no real title available?)
- scientific article; zbMATH DE number 3818523 (Why is no real title available?)
- scientific article; zbMATH DE number 3728055 (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 1860211 (Why is no real title available?)
- Invariance and efficiency of convex representations
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- New stopping criteria for detecting infeasibility in conic optimization
- Notes on Duality in Second Order and p -Order Cone Optimization
- On Nesterov's approach to semi-infinite programming
- On point classification in convex sets.
- On the Closedness of the Linear Image of a Closed Convex Cone
- On the connection of facially exposed and nice cones
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Regularizing the abstract convex program
- Relating Homogeneous Cones and Positive Definite Cones via T-Algebras
- Semidefinite optimization
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Set intersection theorems and existence of optimal solutions
- Stability of closedness of convex cones under linear mappings
- Stability of closedness of convex cones under linear mappings. II
- Strong duality and minimal representations for cone optimization
- Strong Duality for Semidefinite Programming
- Strong duality in conic linear programming: facial reduction and extended duals
- Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
- Universal duality in conic convex optimization
Cited in
(22)- 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
- Conic programming: infeasibility certificates and projective geometry
- Bad projections of the PSD cone
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- A complementarity partition theorem for multifold conic systems
- A simplified treatment of Ramana's exact dual for semidefinite programming
- A note on strict complementarity for the doubly non-negative cone
- Solving SDP completely with an interior point oracle
- scientific article; zbMATH DE number 7476198 (Why is no real title available?)
- In SDP Relaxations, Inaccurate Solvers Do Robust Optimization
- Characterizing bad semidefinite programs: normal forms and short proofs
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- Preprocessing and regularization for degenerate semidefinite programs
- A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone
- Generating linear, semidefinite, and second-order cone optimization problems for numerical experiments
- Understanding badly and well-behaved linear matrix inequalities via semi-infinite optimization
- On the uniform duality in copositive optimization
- Certifying solutions of degenerate semidefinite programs
This page was built for publication: Bad semidefinite programs: they all look the same
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2967605)
