Conditioning of semidefinite programs

Madhu V. Nayakkankuppam; Michael L. Overton

doi:10.1007/s101070050070

Conditioning of semidefinite programs

Madhu V. Nayakkankuppam, Michael L. Overton

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	525-540
Number of pages	16
Journal	Mathematical Programming, Series B
Volume	85
Issue number	3
DOIs	https://doi.org/10.1007/s101070050070
State	Published - 1999

Keywords

Condition number
Kantorovič theory
Perturbation theory
Semidefinite programming

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/s101070050070

Cite this

@article{506b4dcb34c84ec782f448098b34268f,

title = "Conditioning of semidefinite programs",

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{\v c} 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.",

keywords = "Condition number, Kantorovi{\v c} theory, Perturbation theory, Semidefinite programming",

author = "Nayakkankuppam, {Madhu V.} and Overton, {Michael L.}",

year = "1999",

doi = "10.1007/s101070050070",

language = "English (US)",

volume = "85",

pages = "525--540",

journal = "Mathematical Programming, Series B",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "3",

}

TY - JOUR

T1 - Conditioning of semidefinite programs

AU - Nayakkankuppam, Madhu V.

AU - Overton, Michael L.

PY - 1999

Y1 - 1999

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

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

KW - Condition number

KW - Kantorovič theory

KW - Perturbation theory

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=0007469583&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0007469583&partnerID=8YFLogxK

U2 - 10.1007/s101070050070

DO - 10.1007/s101070050070

M3 - Article

AN - SCOPUS:0007469583

SN - 0025-5610

VL - 85

SP - 525

EP - 540

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 3

ER -

Conditioning of semidefinite programs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this