Strong duality in conic linear programming: facial reduction and extended duals

DOI10.1007/978-1-4614-7621-4_28MaRDI QIDQ5746458zbMATH OpenOpenAlexFDO

Authors Gábor Pataki

Publication date 18 February 2014

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

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

zbMATH Keywords

conic linear programmingextended dualsfacial reductionnice conessemidefinite programmingstrong duality

Mathematics Subject Classification ID

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

Abstract: The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program ${\displaystyle }$ (P) sup {<c, x> | Ax leq_K b} ${\displaystyle }$ 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.

Recommendations

• The minimal cone for conic linear programming
• Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
• scientific article; zbMATH DE number 5036103
• A simplified treatment of Ramana's exact dual for semidefinite programming
• Facial reduction and partial polyhedrality

Cited in

(45)

• A relaxed-certificate facial reduction algorithm based on subspace intersection
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Conic programming: infeasibility certificates and projective geometry
• Perturbation analysis of singular semidefinite programs and its applications to control problems
• Bad projections of the PSD cone
• Dimension reduction for semidefinite programs via Jordan algebras
• Characterization of the dual problem of linear matrix inequality for H-infinity output feedback control problem via facial reduction
• Amenable cones: error bounds without constraint qualifications
• Iterative universal rigidity
• A bound on the Carathéodory number
• The orthogonal complement of faces for cones associated with the cone of positive semidefinite matrices
• Bad semidefinite programs: they all look the same
• Facial reduction algorithms for conic optimization problems
• Facial reduction and partial polyhedrality
• Prestress stability of triangulated convex polytopes and universal second-order rigidity
• Solving SDP completely with an interior point oracle
• scientific article; zbMATH DE number 7476198 (Why is no real title available?)
• 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
• 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
• Coordinate shadows of semidefinite and Euclidean distance matrices
• Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• Application of facial reduction to H_ state feedback control problem
• Error bounds and singularity degree in semidefinite programming
• Amenable cones are particularly nice
• Validating numerical semidefinite programming solvers for polynomial invariants
• 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
• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Weak notions of nondegeneracy in nonlinear semidefinite programming
• On the longest chain of faces of the completely positive and copositive cones
• 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
• Convergence rate of alternating projection method for the intersection of an affine subspace and the second-order cone
• A minimal face constant rank constraint qualification for reducible conic programming
• Certifying solutions of degenerate semidefinite programs
• Tight error bounds for log-determinant cones without constraint qualifications
• Linear copositive programming: strong dual formulations and their properties
• Relaxations of KKT conditions do not strengthen finite RLT and SDP-RLT bounds for nonconvex quadratic programs
• The minimal cone for conic linear programming

This page was built for publication: Strong duality in conic linear programming: facial reduction and extended duals

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