On primal-dual path following algorithms for semidefinite programming.

E. de Klerk, C. Roos, T. Terlaky

Interior point methods for semidefinite programming have recently been studied intensively, due to their polynomial complexity and practical efficiency. Most of these methods are extensions of linear programming algorithms. The long step primal-dual path-following (log barrier) method was rece ntly extended to semidefinite programming by Jiang, using the Nesterov-Todd direction and a new centrality measure. In this report we refine and extend this analysis: A weaker condition for a full Newton step in terms of the new measure is derived, and quadratic convergence to target points on the central path is shown. Moreover, strategies for large barrier parameter updates which still allow full Newton steps are proposed.

Report 96-102, Reports of the Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands.

Contact: e.deklerk@twi.tudelft.nl