Solving SDP completely with an interior point oracle
From MaRDI portal
Abstract: We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying Slater's condition simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show how to use such an oracle to "completely solve" an arbitrary SDP. Completely solving an SDP, includes, for example, distinguishing between weak/strong feasibility/infeasibility and detecting when the optimal value is attained or not. We will employ several tools, including a variant of facial reduction where all auxiliary problems are ensured to satisfy Slater's condition at all sides. Our main technical innovation, however, is an analysis of double facial reduction, which is the process of applying facial reduction twice: first to the original problem and then once more to the dual of the regularized problem obtained during the first run. Although our discussion is focused on semidefinite programming, the majority of the results are proved for general convex cones
Recommendations
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- scientific article; zbMATH DE number 1031414
- An exact duality theory for semidefinite programming and its complexity implications
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
Cites work
- A bound on the Carathéodory number
- A relaxed-certificate facial reduction algorithm based on subspace intersection
- A structural geometrical analysis of weakly infeasible SDPS
- A unified class of directly solvable semidefinite programming problems
- Amenable cones: error bounds without constraint qualifications
- An exact duality theory for semidefinite programming based on sums of squares
- Bad semidefinite programs: they all look the same
- Characterizing bad semidefinite programs: normal forms and short proofs
- Cones of diagonally dominant matrices
- Conic convex programming and self-dual embedding
- Error Bounds for Linear Matrix Inequalities
- Exact algorithms for linear matrix inequalities
- Exact Duality in Semidefinite Programming Based on Elementary Reformulations
- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
- Explicit solutions for interval semidefinite linear programs
- Facial reduction algorithms for conic optimization problems
- Facial reduction and partial polyhedrality
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
- scientific article; zbMATH DE number 3728055 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1534289 (Why is no real title available?)
- scientific article; zbMATH DE number 1534291 (Why is no real title available?)
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- New stopping criteria for detecting infeasibility in conic optimization
- On homogeneous interrior-point algorithms for semidefinite programming
- On the complexity of semidefinite programs
- On the duality operator of a convex cone
- On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Preprocessing and regularization for degenerate semidefinite programs
- Primal-dual interior-point methods for domain-driven formulations
- Projections of Convex Programs with Unattained Infima
- Regularizing the abstract convex program
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Strong duality and minimal representations for cone optimization
- Strong Duality for Semidefinite Programming
- Strong duality in conic linear programming: facial reduction and extended duals
- The Simplest Semidefinite Programs are Trivial
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Weak infeasibility in second order cone programming
Cited in
(10)- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Weak infeasibility in second order cone programming
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
- A new extension of Chubanov's method to symmetric cones
- Closing duality gaps of SDPs completely through perturbation when singularity degree is one
- Certifying solutions of degenerate semidefinite programs
This page was built for publication: Solving SDP completely with an interior point oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999336)
