On sensitivity of central solutions in semidefinite programming

On sensitivity of central solutions in semidefinite programming

0.00 Avg rating0 Votes
Article ID: iaor2002922
Country: Germany
Volume: 90
Issue: 2
Start Page Number: 205
End Page Number: 227
Publication Date: Jan 2001
Journal: Mathematical Programming
Authors: ,
Abstract:

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic conter of the optimal set, is approached. Our analysis assumes the primal–dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the drivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example 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.

Reviews

Required fields are marked *. Your email address will not be published.