On Sensitivity of Central Solutions in Semidefinite Programming - J.F. Sturm; S. Zhang (Tinbergen Institute, 1998)
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: 330; analytic central path; semidefinite programming; sensitivity; condition number; Mathematische Optimierung; Theorie