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: [email protected]
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[PS]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)