Symmetric primal-dual path following algorithms for semidefinite programming

J.F. Sturm and Shuzhong Zhang

No EI 9554-/A, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

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.

Keywords: primal-dual interior point method; primal-dual transformation; semidefinite programming (search for similar items in EconPapers)
Date: 1995-01-01
References: Add references at CitEc
Citations: View citations in EconPapers (4)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:1364

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).