Optimization Online


Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach

Frank Permenter (fperment***at***mit.edu)
Henrik A. Friberg (metronware***at***gmail.com)
Erling D. Andersen (e.d.andersen***at***mosek.com)

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 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 algorithms, based on facial reduction, for solving the primal or dual problem that, in principle, always succeed. These algorithms have the appealing property that they only perform 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. We interpret this phenomena geometrically by studying the cone of solutions to the homogeneous model -- an interesting object in its own right. For the case of semidefinite programming, we show our method can be implemented using existing central-path-following techniques.

Keywords: conic optimization, facial reduction, self-dual embedding, homogeneous model

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 09/14/2015
Entry Accepted: 09/14/2015
Entry Last Modified: 11/11/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society