Conic convex programming and self-dual embedding
- 1 January 2000
- journal article
- research article
- Published by Informa UK Limited in Optimization Methods and Software
- Vol. 14 (3), 169-218
- https://doi.org/10.1080/10556780008805800
Abstract
How ro 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 [30]. For linear programming this technique makes it possible to identify an optimal solution or conclude the problem to be infeasible/unbounded by solving tts embedded self-dual problem The embedded self-dual problem has a trivial initial solution and has the same stmctare 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 programmng. Since a nonlinear conic convex programming problem may lack the so-called strict complementarity property, it canses diffcairier 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.Keywords
This publication has 18 references indexed in Scilit:
- Primal-Dual Interior-Point Methods for Self-Scaled ConesSIAM Journal on Optimization, 1998
- Infeasible-start semidefinite programming algorithms via self-dual embeddingsPublished by American Mathematical Society (AMS) ,1998
- On homogeneous interrior-point algorithms for semidefinite programmingOptimization Methods and Software, 1998
- Initialization in semidefinite programming via a self-dual skew-symmetric embeddingOperations Research Letters, 1997
- Self-Scaled Barriers and Interior-Point Methods for Convex ProgrammingMathematics of Operations Research, 1997
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric MatricesSIAM Journal on Optimization, 1997
- Infeasible-Interior-Point AlgorithmsPublished by Springer Science and Business Media LLC ,1996
- Convergence behavior of interior-point algorithmsMathematical Programming, 1993
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- Computational experience with a primal-dual interior point method for linear programmingLinear Algebra and its Applications, 1991