TY - JOUR

T1 - Conic convex programming and self-dual embedding

AU - Luo, Z. Q.

AU - Sturm, J. F.

AU - Zhang, S.

PY - 2000

Y1 - 2000

N2 - How to initialize an algorithm to solve an optimization problem is of great theoretical and practical importance. In the simplex method for linear programming this issue is resolved by either the two-phase approach or using the so-called big M technique. In the interior point method, there is a more elegant way to deal with the initialization problem, viz. the self-dual embedding technique proposed by Ye, Todd and Mizuno. For linear programming this technique makes it possible to identify an optimal solution or conclude the problem to be infeasible/unbounded by solving its embedded self-dual problem. The embedded self-dual problem has a trivial initial solution and has the same structure as the original problem. Hence, it eliminates the need to consider the initialization problem at all. In this paper, we extend this approach to solve general conic convex programming, including semidefinite programming. Since a nonlinear conic convex programming problem may lack the so-called strict complementarity property, it causes difficulties in identifying solutions for the original problem, based on solutions for the embedded self-dual system. We provide numerous examples from semidefinite programming to illustrate various possibilities which have no analogue in the linear programming case.

AB - How to initialize an algorithm to solve an optimization problem is of great theoretical and practical importance. In the simplex method for linear programming this issue is resolved by either the two-phase approach or using the so-called big M technique. In the interior point method, there is a more elegant way to deal with the initialization problem, viz. the self-dual embedding technique proposed by Ye, Todd and Mizuno. For linear programming this technique makes it possible to identify an optimal solution or conclude the problem to be infeasible/unbounded by solving its embedded self-dual problem. The embedded self-dual problem has a trivial initial solution and has the same structure as the original problem. Hence, it eliminates the need to consider the initialization problem at all. In this paper, we extend this approach to solve general conic convex programming, including semidefinite programming. Since a nonlinear conic convex programming problem may lack the so-called strict complementarity property, it causes difficulties in identifying solutions for the original problem, based on solutions for the embedded self-dual system. We provide numerous examples from semidefinite programming to illustrate various possibilities which have no analogue in the linear programming case.

UR - http://www.scopus.com/inward/record.url?scp=0034459312&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034459312&partnerID=8YFLogxK

U2 - 10.1080/10556780008805800

DO - 10.1080/10556780008805800

M3 - Article

AN - SCOPUS:0034459312

SN - 1055-6788

VL - 14

SP - 169

EP - 218

JO - Optimization Methods and Software

JF - Optimization Methods and Software

IS - 3

ER -