Target Directions for Primal-Dual Interior-Point Methods for Self-Scaled Conic Programming

Raphael Hauser

The theory of self-scaled conic programming provides a unified framework for the theories of linear programming, semidefinite programming and convex quadratic programming with convex quadratic constraints. In the linear programming literature there exists a unifying framework for the analysis of various important classes of interior-point algorithms, known under the name of target-following algorithms. This article is a step towards combining these two unifying theories in that we develop an infinite new family of Newton directions for self-scaled conic programming which inherit the properties of the search-direction that made target-following algorithms possible in the LP case. These so-called target directions are close relatives of the Nesterov-Todd direction and lend themselves to the construction of predictor-corrector methods. Moreover, target directions are closely connected to the notion of weighted analytic centers.

Numerical Analysis Report DAMTP 1999/NA15, Department of Applied Mathematics and Theoretical Physics, Silver Street, Cambridge, England CB3 9EW.