Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
From MaRDI portal
Publication:5746458
DOI10.1007/978-1-4614-7621-4_28zbMath1282.90231arXiv1301.7717OpenAlexW2166161233MaRDI QIDQ5746458
Publication date: 18 February 2014
Published in: Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)
Abstract: The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program $$ (P) sup {<c, x> | Ax leq_K b} $$ in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana's dual is applicable when (P) is a semidefinite program (SDP) and is an explicit SDP itself. Ramana, Tuncel, and Wolkowicz showed that these approaches are closely related; in particular, they proved the correctness of Ramana's dual using certificates from a facial reduction algorithm. Here we give a clear and self-contained exposition of facial reduction, of extended duals, and generalize Ramana's dual: -- we state a simple facial reduction algorithm and prove its correctness; and -- building on this algorithm we construct a family of extended duals when $K$ is a {em nice} cone. This class of cones includes the semidefinite cone and other important cones.
Full work available at URL: https://arxiv.org/abs/1301.7717
semidefinite programmingstrong dualityfacial reductionconic linear programmingnice conesextended duals
Semidefinite programming (90C22) Convex programming (90C25) 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 (36)
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 ⋮ Dimension reduction for semidefinite programs via Jordan algebras ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Weak notions of nondegeneracy in nonlinear semidefinite programming ⋮ Prestress Stability of Triangulated Convex Polytopes and Universal Second-Order Rigidity ⋮ Bad Semidefinite Programs: They All Look the Same ⋮ A relaxed-certificate facial reduction algorithm based on subspace intersection ⋮ Characterization of the dual problem of linear matrix inequality for H-infinity output feedback control problem via facial reduction ⋮ Unnamed Item ⋮ Amenable cones: error bounds without constraint qualifications ⋮ Refining the partition for multifold conic optimization problems ⋮ A note on alternating projections for ill-posed semidefinite feasibility problems ⋮ Weak infeasibility in second order cone programming ⋮ Conic programming: infeasibility certificates and projective geometry ⋮ Application of facial reduction to H ∞ state feedback control problem ⋮ Validating numerical semidefinite programming solvers for polynomial invariants ⋮ Perturbation analysis of singular semidefinite programs and its applications to control problems ⋮ Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone ⋮ On the longest chain of faces of the completely positive and copositive cones ⋮ Bad projections of the PSD cone ⋮ Closing duality gaps of SDPs completely through perturbation when singularity degree is one ⋮ Analytic formulas for alternating projection sequences for the positive semidefinite cone and an application to convergence analysis ⋮ Facial approach for constructing stationary points for mathematical programs with cone complementarity constraints ⋮ Limitations on the Expressive Power of Convex Cones without Long Chains of Faces ⋮ Facially Dual Complete (Nice) Cones and Lexicographic Tangents ⋮ Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs ⋮ Solving SDP completely with an interior point oracle ⋮ Exact Duality in Semidefinite Programming Based on Elementary Reformulations ⋮ Error Bounds and Singularity Degree in Semidefinite Programming ⋮ Coordinate Shadows of Semidefinite and Euclidean Distance Matrices ⋮ Amenable Cones Are Particularly Nice ⋮ Iterative universal rigidity ⋮ Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach
This page was built for publication: Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
