Template-Type: ReDIF-Paper 1.0
Author-Name: Sturm, J.F.
Author-Name-Last: Sturm
Author-Name: Zhang, S.
Author-Name-Last: Zhang
Author-Name-First: Shuzhong
Title: On the long step path--following method for semidefinite programming
Abstract: 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 [TeX: 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 [TeX: O(n log(1/ epsilon))]. Independently, Monteiro and Y. Zhang obtained a similar result using Nesterov-Todd directions.
Creation-Date: 1996-01-01
Series: RePEc:ems:eureir
Number: EI 9638-/A
Keywords: long step path following, semidefinite programming, symmetric  primal-dual transformation
Handle: RePEc:ems:eureir:1389