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