Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming

Z-Q. Luo, J.F. Sturm and Shuzhong Zhang

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

Abstract: This paper establishes the superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming under the assumptions that the semidefinite program has a strictly complementary primal-dual optimal solution and that the size of the central path neighborhood tends to zero. The interior point algorithm considered here closely resembles the Mizuno-Todd-Ye predictor-corrector method for linear programming which is known to be quadratically convergent. It is shown that when the iterates are well centered, the duality gap is reduced superlinearly after each predictor step. Indeed, if each predictor step is succeeded by [TeX: $r$] consecutive corrector steps then the predictor reduces the duality gap superlinearly with order [TeX: $\\frac{2}{1+2^{-2r}}$]. The proof relies on a careful analysis of the central path for semidefinite programming. It is shown that under the strict complementarity assumption, the primal-dual central path converges to the analytic center of the primal-dual optimal solution set, and the distance from any point on the central path to this analytic center is bounded by the duality gap.

Keywords: central path; path following; semidefinite programming; superlinear convergence (search for similar items in EconPapers)
Date: 1996-01-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://repub.eur.nl/pub/1373/1373_c.pdf (application/pdf)

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

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