Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results

Abstract

Primal-dual interior-point path-following methods for semidefinite programming (SDP) are considered. Several variants are discussed based on Newtons method applied to three equations: primal feasibility, dual feasibility, and some form of centering condition. The focus is on three such algorithms, called respectively the XZ, XZ+ZX and Q methods. For the XZ+ZX and Q methods algorithms, the Newton system is well-defined and its Jabobian is nonsingular at the solutions, under nondegeneracy assumptions. The associated Schur complement matrix has an unbounded condition number on the central path, under nondegeneracy assumptions and an additional rank assumption. Practical aspects are discussed, including Mehrotra predictor-corrector variants and issues of numerical stability. Compared to the other methods considered, the XZ+ZX method is more robust with respect to its ability to step close to the boundary, converges more rapidly, and achieves higher accuracy.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 31, 1996
Accession Number
AD1020236

Entities

People

  • Farid Alizadeh
  • Jean-pierre A. Haeberly
  • Michael L. Overton

Organizations

  • New York University

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Boundaries
  • Computer Programming
  • Convergence
  • Equations
  • Evolutionary Algorithms
  • Heuristic Methods
  • Mathematics
  • Semidefinite Programming

Fields of Study

  • Mathematics

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Operations Research