TY - JOUR

T1 - On sensitivity of central solutions in semidefinite programming

AU - Sturm, J. F.

AU - Zhang, S.

PY - 2001/4

Y1 - 2001/4

N2 - 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 center 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 derivatives 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.

AB - 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 center 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 derivatives 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.

KW - Analytic central path

KW - Condition number

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=0005334185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0005334185&partnerID=8YFLogxK

U2 - 10.1007/PL00011422

DO - 10.1007/PL00011422

M3 - Article

AN - SCOPUS:0005334185

SN - 0025-5610

VL - 90

SP - 205

EP - 227

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 2

ER -