Sensitivity analysis of semidefinite programs without strong duality
Sensitivity analysis of semidefinite programs without strong duality
复制标题
无强对偶性的半定规划的敏感性分析
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Henry Wolkowicz
中科院分区：
文献类型：
--
作者：
Yuen;Henry Wolkowicz
假设我们被给出了一个可行的二次规划，该规划有一个有限的最优值，并且具有强对偶失效。众所周知，问题数据存在较小的扰动，导致最优值发生较大变化。在半定规划(SDP)的情况下，我们量化了大变化的概念。我们首先证明了，对于任何具有有限最优值的SDP，其中强对偶失效，且存在非零对偶间隙，则对于沿任何可行扰动方向的足够小的步长，最优值至少改变一个固定常数。接下来，如果存在零对偶间隙，无论有或没有双重实现，则任何足够小的>；0可行扰动对于某些要指定的常数γ∈(0，1)至多改变最优值O()。我们的主要工具涉及SDP的面部缩小。
Suppose that we are given a feasible conic program with a finite optimal value and with strong duality failing. It is known that there are small perturbations of the problem data that lead to relatively big changes in the optimal value. We quantify the notion of big change in the case of a semidefinite program (SDP). We first show that for any SDP with a finite optimal value where strong duality fails, and where there is a nonzero duality gap, then for a sufficiently small step along any feasible perturbation direction, the optimal value changes by at least a fixed constant. And next, if there is a zero duality gap, with or without dual attainment, then any sufficiently small > 0 feasible perturbation changes the optimal value by at most O( ) for some, to be specified, constant γ ∈ (0, 1). Our main tool involves the facial reduction of SDP.