Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach

Abstract

We establish connections between the facial reduction algorithm of Borwein and Wolkowicz and the self-dual homogeneous model of Goldman and Tucker when applied to conic optimization problems. Specifically, we show that the self-dual homogeneous model returns facial reduction certificates when it fails to return a primal-dual optimal solution or a certificate of infeasibility. Using this observation, we give an algorithm based on facial reduction for solving the primal problem that, in principle, always succeeds. (An analogous algorithm is easily stated for the dual problem.) This algorithm has the appealing property that it only performs facial reduction when it is required, not when it is possible; e.g., if a primal-dual optimal solution exists, it will be found in lieu of a facial reduction certificate even if Slater's condition fails. For the case of linear, second-order, and semidefinite optimization, we show that the algorithm can be implemented by assuming oracle access to the central-path limit point of an extended embedding, a strictly feasible conic problem with a strictly feasible dual. We then give numerical experiments illustrating barriers to practical implementation.

Locations

• Technical University of Denmark, DTU Orbit (Technical University of Denmark, DTU) - View - PDF
• SIAM Journal on Optimization - View