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 -