On Sensitivity of Central Solutions in Semidefinite Programming

J.F. Sturm and Stephen Zhang
Additional contact information
J.F. Sturm: McMaster University, Hamilton, Canada

No 98-040/4, Tinbergen Institute Discussion Papers from Tinbergen Institute

Abstract: In this paper we study the properties of the analytic central path of asemidefinite programming problem under perturbation of a set of inputparameters. Specifically, we analyze the behavior of solutions on the centralpath with respect to changes on the right hand side of the constraints,including the limiting behavior when the central optimal solution isapproached. Our results are of interest for the sake of numerical analysis,sensitivity analysis and parametric programming.Under the primal-dual Slater condition and the strict complementarity conditionwe show that the derivatives of central solutions with respect to theright hand side parameters converge as the path tends to the centraloptimal solution. Moreover, the derivatives are bounded, i.e. aLipschitz constant exists.This Lipschitz constant can be thought of as a condition number for thesemidefinite programming problem. It is a generalization of the familiarcondition number for linear equation systems and linear programming problems.However, the generalized condition number depends on the right hand sideparameters as well, whereas it is well-known that in the linear programming casethe condition number depends only on the constraint matrix.We demonstrate that the existence of strictly complementary solutionsis important for the Lipschitz constant to exist.Moreover, we give an example in which the set of right hand side parameters forwhich the strict complementarity condition holds is neither open nor closed.This is remarkable since a similar set for which the primal-dual Slatercondition holds is always open.

Keywords: analytic central path; semidefinite programming; sensitivity; condition number (search for similar items in EconPapers)
Date: 1998-04-17
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://papers.tinbergen.nl/98040.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tin:wpaper:19980040

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().