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: Symmetric primal-dual path following algorithms for semidefinite programming
Abstract: In this paper a symmetric primal-dual transformation for positive semidefinite programming is proposed. For standard SDP problems, after this symmetric transformation the primal variables and the dual slacks become identical. In the context of linear programming, existence of such a primal-dual transformation is a well known fact. Based on this symmetric primal-dual transformation we derive Newton search directions for primal-dual path-following algorithms for semidefinite programming. In particular, we generalize: (1) the short step path following algorithm, (2) the predictor-corrector algorithm and (3) the largest step algorithm to semidefinite programming. It is shown that these algorithms require at most [TeX: ${\\cal O}(\\sqrt{n}\\mid \\log \\epsilon \\mid ) $] main iterations for computing an  [TeX: $\\epsilon $]-optimal solution.
Creation-Date: 1995-01-01
Series: RePEc:ems:eureir
Number: EI 9554-/A
Keywords: primal-dual interior point method, primal-dual transformation, semidefinite programming
Handle: RePEc:ems:eureir:1364