Optimization Online


A New Self-Dual Embedding Method for Convex Programming

Shuzhong Zhang (zhang***at***se.cuhk.edu.hk)

Abstract: In this paper we introduce a conic optimization formulation for inequality-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.

Keywords: Convex Programming, Convex Cones, Self-Dual Embedding, Self-Concordant Barrier Functions.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Technical Report SEEM2001-09, Department of Systems Engineering & Engineering Management The Chinese University of Hong Kong, 2001.

Download: [Postscript]

Entry Submitted: 01/03/2002
Entry Accepted: 01/04/2002
Entry Last Modified: 01/03/2002

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 Programming Society