New Complexity Analysis of the Primal-Dual Method for Semidefinite Optimization based on the NT-direction

J. Peng, C. Roos and T. Terlaky

Interior point methods for semidefinite optimization have recently been studied intensively, due to their polynomial complexity and practical efficiency. Many search directions have been proposed to symmetrize the corresponding Newton system. In this paper, we first introduce a variational principle for defining the search direction and show that the Nesterov-Todd (NT) direction is optimal under this principle. Secondly, we provide a unified analysis for both large-update and small-update interior point methods using the NT direction and derive polynomial iteration bounds for such methods.

Techinal Report, January 1999, Faculty of ITS/TWI, Delft University of Technology, Delft, The Netherlands