Conditioning of semidefinite programs

Madhu V. Nayakkankuppam, Michael L. Overton

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies the conditioning of semidefinite programs by analyzing the effect of small perturbations in problem data on the solution. Under the assumptions of strict complementarity and non-degeneracy, an explicit bound on the change in the solution is derived in a primal-dual framework, using tools from the Kantorovič theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case.

Original languageEnglish (US)
Pages (from-to)525-540
Number of pages16
JournalMathematical Programming, Series B
Volume85
Issue number3
DOIs
StatePublished - 1999

Keywords

  • Condition number
  • Kantorovič theory
  • Perturbation theory
  • Semidefinite programming

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Conditioning of semidefinite programs'. Together they form a unique fingerprint.

Cite this