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

摘要

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.