Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

Zhaosong Lu, Renato D.C. Monteiro

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form X S+SX=2 W, where W is a fixed positive definite matrix and 0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. We present a different and simpler proof than the one given by Prei and Stoer [Prei, M. and Stoer, J., 2004, Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems. Mathematical Programming 99, 499-520.] that a weighted central path as a function of can be extended analytically beyond 0. In addition, the characterization of the limit points of the path and its normalized first-order derivatives is also provided. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, we make some observation for the superlinear convergence of some primal-dual interior point SDP algorithms using AHO neighborhood.

Original languageEnglish (US)
Pages (from-to)849-870
Number of pages22
JournalOptimization Methods and Software
Volume22
Issue number5
DOIs
StatePublished - Oct 2007
Externally publishedYes

Bibliographical note

Funding Information:
The authors are in debt to three anonymous referees for invaluable advice and comments that have greatly improved this paper. This work was partially supported by NSF Grants CCR-9902010, CCR-0203113, INT-9910084 and CCF-0430644 and ONR grants N00014-03-1-0401 and N00014-05-1-0183.

Keywords

  • Error bound
  • Limiting behavior
  • Semidefinite programming
  • Superlinear convergence
  • Weighted central path

Fingerprint

Dive into the research topics of 'Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming'. Together they form a unique fingerprint.

Cite this