Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach
本文建立了面缩减算法与自对偶齐次模型在锥优化问题中的联系，提出一种仅在必要时进行面缩减的求解算法，并在线性、二阶锥和半定优化中展示了其实现原理与数值实验。
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.