On the long Step Path-Following Method for Semidefinite Programming

Jos F. Sturm and Shuzhong Zhang

It has been shown in various recent research reports that the analysis of short step primal-dual path following algorithms for linear programming can be nicely generalized to semidefinite programming. However, the analysis of long step path-following algorithms for semidefinite programming appeared to be less straightforward. For such an algorithm, Monteiro obtained an O(n^1.5 log(1/ epsilon)) iteration bound for obtaining an epsilon-optimal solution, where n is the order of the semidefinite decision variable. In this paper, we propose to use a different search direction, viz. the so-called V-space direction. It is shown that this modification reduces the iteration complexity to O(n log(1/ epsilon)) . Independently, Monteiro and Y.Zhang obtained a similar result using Nesterov-Todd directions.

Report 9638/A, Econometric Institute, Erasmus University Rotterdam, the Netherlands (1996) 9 pages.

Contact: sturm@opres.few.eur.nl