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

Frank Permenter, Henrik A. Friberg, Erling D. Andersen

Research output: Contribution to journalJournal articleResearchpeer-review

222 Downloads (Pure)

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.

Original languageEnglish
JournalSIAM Journal on Optimization
Volume27
Issue number3
Pages (from-to)1257-1282
Number of pages26
ISSN1052-6234
DOIs
Publication statusPublished - 2017

Keywords

  • Conic optimization
  • Facial reduction
  • Homogeneous model
  • Self-dual embedding

Fingerprint Dive into the research topics of 'Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach'. Together they form a unique fingerprint.

Cite this