Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/85734
Authors: 
Sturm, J.F.
Zhang, S.
Year of Publication: 
1998
Series/Report no.: 
Tinbergen Institute Discussion Paper 98-040/4
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.
Subjects: 
analytic central path
semidefinite programming
sensitivity
condition number
Document Type: 
Working Paper

Files in This Item:
File
Size
225.71 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.