A new self-dual embedding method for convex programming

作     者：Zhang, SZ 

作者机构：Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China 

出 版 物：《JOURNAL OF GLOBAL OPTIMIZATION》 (全局最优化杂志)

年 卷 期：2004年第29卷第4期

页      面：479-496页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：RGC  (CUHK4233/01E) 

主　　题：convex cones convex programming self-concordant barrier functions self-dual embedding 

摘      要：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.