A new self-dual embedding method for convex programming

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.

Original languageEnglish (US)
Pages (from-to)479-496
Number of pages18
JournalJournal of Global Optimization
Volume29
Issue number4
DOIs
StatePublished - Aug 2004

Keywords

  • Convex cones
  • Convex programming
  • Self-concordant barrier functions
  • Self-dual embedding

Fingerprint Dive into the research topics of 'A new self-dual embedding method for convex programming'. Together they form a unique fingerprint.

Cite this