SDP の安全な下界

主問題 $\min\langle C,X\rangle$ s.t. $\langle A_i,X\rangle=b_i$ ($i=1,\ldots,m$), $X\succeq0$ の任意の実行可能解が $\operatorname{tr}X\le\bar t$ を満たすとする。$\boldsymbol{y}\in\mathbb{R}^m$ について $S=C-\sum_iy_iA_i$ とし、$\lambda_{\min}(S)\ge\underline\lambda$ が分かっているとする。このとき最適値 $p^\ast$ について $p^\ast\ge\boldsymbol{b}^{\mathsf{T}}\boldsymbol{y}+\min(\underline\lambda,0)\,\bar t$ である。