On Sensitivity of Central Solutions in Semidefinite Programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of a set of input parameters. Specifically, we analyze the behavior of solutions on the central path with respect to changes on the right hand side of the constraints, including the limiting behavior when the central optimal solution is approached. 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 condition we show that the derivatives of central solutions with respect to the right hand side parameters converge as the path tends to the central optimal solution. Moreover, the derivatives are bounded, i.e. a Lipschitz constant exists.<BR> This Lipschitz constant can be thought of as a condition number for the semidefinite programming problem. It is a generalization of the familiar condition number for linear equation systems and linear programming problems. However, the generalized condition number depends on the right hand side parameters as well, whereas it is well-known that in the linear programming case the condition number depends only on the constraint matrix. We demonstrate that the existence of strictly complementary solutions is important for the Lipschitz constant to exist.<BR> Moreover, we give an example in which the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open.<BR><BR>