Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming

DOI10.1007/s10107-017-1136-5zbMath1402.90115arXiv1507.00290OpenAlexW2963029052MaRDI QIDQ1702782

Gábor Pataki, Ming-Hui Liu

Publication date: 28 February 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingfacial reductionconic linear programmingclosedness of the linear image of a closed convex coneexact certificates of infeasibility and weak infeasibilityexact duals

Mathematics Subject Classification ID

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

Related Items (20)

A bound on the Carathéodory number ⋮ Facial Reduction and Partial Polyhedrality ⋮ A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms ⋮ Error bounds, facial residual functions and applications to the exponential cone ⋮ A simplified treatment of Ramana's exact dual for semidefinite programming ⋮ Unnamed Item ⋮ Amenable cones: error bounds without constraint qualifications ⋮ Numerical algebraic geometry and semidefinite programming ⋮ Weak infeasibility in second order cone programming ⋮ Conic programming: infeasibility certificates and projective geometry ⋮ Perturbation analysis of singular semidefinite programs and its applications to control problems ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ Limitations on the Expressive Power of Convex Cones without Long Chains of Faces ⋮ A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs ⋮ Facially Dual Complete (Nice) Cones and Lexicographic Tangents ⋮ An interior point-proximal method of multipliers for linear positive semi-definite programming ⋮ Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs ⋮ Solving SDP completely with an interior point oracle ⋮ Amenable Cones Are Particularly Nice ⋮ Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach

Uses Software

• frlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions
• Facial reduction algorithms for conic optimization problems
• Characterizing the universal rigidity of generic frameworks
• Set intersection theorems and existence of optimal solutions
• New stopping criteria for detecting infeasibility in conic optimization
• Regularizing the abstract convex program
• An exact duality theory for semidefinite programming and its complexity implications
• Convex analysis and nonlinear optimization. Theory and examples
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Cones of diagonally dominant matrices
• A paradigm for listing \((s,t)\)-cuts in graphs
• How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
• On the connection of facially exposed and nice cones
• Invariance and efficiency of convex representations
• Cones, matrices and mathematical programming
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Bad Semidefinite Programs: They All Look the Same
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Strong Duality for Semidefinite Programming
• Facial Reduction and Partial Polyhedrality
• Closedness criteria for the image of a closed set by a inear operator
• Facially Exposed Cones Are Not Always Nice
• An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
• Coordinate Shadows of Semidefinite and Euclidean Distance Matrices
• On the Closedness of the Linear Image of a Closed Convex Cone
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• Foundations of Optimization
• A STRUCTURAL GEOMETRICAL ANALYSIS OF WEAKLY INFEASIBLE SDPS
• Convex Analysis
• Proving strong duality for geometric optimization using a conic formulation

This page was built for publication: Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming