Solving SDP completely with an interior point oracle
Open Access
- 28 January 2021
- journal article
- research article
- Published by Informa UK Limited in Optimization Methods and Software
- Vol. 36 (2-3), 425-471
- https://doi.org/10.1080/10556788.2020.1850720
Abstract
We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying strong feasibility (i.e. 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 entails, 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 strong feasibility 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.Keywords
Other Versions
Funding Information
- JSPS ((B)26280005, (C)17K00031, (B)20H04145, (B)15H02968, (B)24310112, (C)26330025, (B)18H03206)
This publication has 41 references indexed in Scilit:
- Strong duality and minimal representations for cone optimizationComputational Optimization and Applications, 2012
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimizationComputational Optimization and Applications, 2011
- A Unified Class of Directly Solvable Semidefinite Programming ProblemsAnnals of Operations Research, 2005
- Conic convex programming and self-dual embeddingOptimization Methods and Software, 2000
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric conesOptimization Methods and Software, 1999
- On homogeneous interrior-point algorithms for semidefinite programmingOptimization Methods and Software, 1998
- Explicit solutions for interval semidefinite linear programsLinear Algebra and its Applications, 1996
- On the duality operator of a convex coneLinear Algebra and its Applications, 1985
- Facial reduction for a cone-convex programming problemJournal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 1980
- Cones of diagonally dominant matricesPacific Journal of Mathematics, 1975