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

Zhi Quan Luo, Jos F. Sturm, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

66 Scopus citations

Abstract

This paper establishes the superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming (SDP) 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 r consecutive corrector steps then the predictor reduces the duality gap superlinearly with order 2/(1 + 2-r). The proof relies on a careful analysis of the central path for SDP. 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.

Original languageEnglish (US)
Pages (from-to)59-81
Number of pages23
JournalSIAM Journal on Optimization
Volume8
Issue number1
DOIs
StatePublished - Feb 1998

Keywords

  • Central path
  • Path following
  • Semidefinite programming
  • Superlinear convergence

Fingerprint Dive into the research topics of 'Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming'. Together they form a unique fingerprint.

Cite this