Search

In this chapter, we discuss a modification of the standard path-following scheme that tends to speed up the global convergence. This modification, the central region method, generates iterates that do not really trace the central path, or at least not closely. In this way, it has a relatively large freedom of movement, and consequently the ability to take long steps. This makes it interesting to consider more sophisticated search directions. We propose a search direction that is built up in three phases, viz. 1. Initial centering, 2. Predictor, 3. Second order centrality corrector.

In this chapter, we take a careful look at the behavior of the central path, when it approaches the optimal solution set of a semidefinite program. We will demonstrate that the primal-dual central path converges to the analytic center of the optimal solution set. Moreover, the distance to this analytic center from any point on the central path is shown to converge at the same R-rate as the duality gap. This result can be interpreted as an error-bound for solutions on the central path, with respect to the optimal solution set. Underlying the analysis is an assumption that a strictly complementary solution pair for the semidefinite program exists.

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.