Search

In Chapter 3, we have analyzed the iteration complexity of finding an ϵ-optimal solution, if an interior, sufficiently centered pair of primal and dual solutions is known beforehand. We will see in this chapter how we can adapt the algorithms of Chapter 3 to solve semidefinite programming problems without any pre-knowledge. To this end, we use the self-dual embedding technique. This technique will also be used to tackle semidefinite programming problems that may be unbounded, unsolvable, or infeasible.

Modern solvers for linear and quadratic programming often incorporate some variant of the primal-dual path-following method, which is a class of interior point methods. This method turns out to be suited for solving semidefinite programming problems as well. In this chapter, we propose a framework for analyzing primal-dual path-following algorithms for semidefinite programming. Our framework is a direct extension of the v-space approach, which was developed by Kojima et al. [63] in the context of complementarity problems.

List of Figures. List of Tables. Preface. Contributing Authors. Part I: Theory and Algorithms of Semidefinite Programming J.F. Sturm. 1. Introduction. 2. Duality. 3. Polynomiality of Path-following Methods. 4. Self-Dual Embedding Technique. 5. Properties of the Central Path. 6. Superlinear Convergence. 7. Central Region Methods. Part II: Linear, Quadratic, Semidefinite Programming and Beyond. 8. An Implementation of the Homogeneous Algorithm E.D. Andersen, K.D. Andersen. 9. A Simplified Correctness Proof for Interior Point Algorithm S.A. Vavasis, Y. Ye. 10. New Analysis of Newton Methods for LCP J. Peng, et al. 11. Numerical Evaluation of SDPA K. Fujisawa, et al. 12. Robust Modeling of Multi-Stage Portfolio Problems A. Ben-Tal, et al. 13. An Interior Point SQP Parallel B&B Method. 14. Solving Linear Ordering Problems J.E. Mitchell, B. Borchers. 15. Finite Element Methods for Solving Parabolic Inverse Problems Y.L. Keung, J. Zou. 16. Error Bounds For Quadratic Systems Z.-Q. Luo, J.F. Sturm. 17. Squared Functional Systems and Optimization Problems Y. Nesterov. 18. Interior Point Methods: Current Status and Future Directions R.M. Freund, S. Mizuno. Index.