On the long step path--following method for semidefinite programming

J.F. Sturm and Stephen Zhang

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

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.

Keywords: long step path following; semidefinite programming; symmetric primal-dual transformation (search for similar items in EconPapers)
Date: 1996-01-01
References: Add references at CitEc
Citations:

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:1389

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 ).