On sensitivity of central solutions in semidefinite programming
On sensitivity of central solutions in semidefinite programming
复制标题
半定规划中心解的敏感性
DOI：
10.1007/pl00011422
复制
发表时间：
2001
影响因子：
2.7
通讯作者：
Shuzhong Zhang
中科院分区：
文献类型：
--
作者：
J. Sturm;Shuzhong Zhang
在本文中，我们研究了在约束右侧扰动下半定规划问题的解析中心路径的性质，包括接近中心最优解（即最优集的解析中心）时的极限行为。 我们的分析假设原对偶斯莱特条件和严格互补条件。我们的研究结果如下。首先，从负面来看，如果我们将中心最优解视为约束右侧的函数，那么该函数通常不是连续的，而在线性规划情况下，该函数已知是 Lipschitz 连续的。从积极的一面来看，与之前的结论相比，我们得到了一个（看似）矛盾的结果：在中心路径上，相对于约束右侧的任何方向导数都是有界的，甚至随着接近中心最优解而收敛。 由于右侧参数的导数缺乏统一的界限，因此可能出现这种现象。 所有这些结果都是基于严格的互补性假设。关于最后一个属性，我们举一个例子。在该示例中，严格互补条件成立的右侧参数集既不是开也不是闭。这是值得注意的，因为原始-对偶斯莱特条件成立的相似集合始终是开放的。
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.