锥规划的对偶与证书

对偶锥收集所有在 $K$ 上非负的线性测量。把目标分解成 $c=A^{\ast }y+s$ 后，第一部分在可行集上恒等于 $b^{\mathrm{\top }}y$，第二部分始终非负。因此对偶点给出可核验的下界，而零内积说明剩余成本已经耗尽。不可行性证书使用同一结构：某个测量在整个锥上非负，却把所要求的右端测成负数。

对 $K={\mathbb{R}}_{+}^n$，有 $K^{\ast }=K$，条件变为 $A^{\mathrm{\top }}y\le c$，恢复等式标准形的线性规划对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。。半正定规划把向量非负改成矩阵半正定，弱对偶的恒等式仍然成立；发生变化的是锥在线性映射下的闭性，以及证书能否取到。

半正定锥为何自对偶 ​

在实对称矩阵空间 ${\mathbb{S}}^n$ 上使用迹公理库迹Trace of a matrix · Matrix trace方阵主对角元素之和，也是线性算子在换基下不变的标量。内积 $⟨S,X⟩=\mathrm{tr}(SX)$。由有限维谱定理公理库有限维谱定理Finite-dimensional spectral theorem有限维实对称或复自伴算子存在正交规范特征向量基。，若 $X⪰0$，可写成 $X=\sum _i{\lambda }_i{q}_i{q}_i^{\mathrm{\top }}$，其中 ${\lambda }_i\ge 0$、$q_i$ 为正交单位向量。对任意 $S⪰0$，

反之，若对称矩阵 $S$ 不是半正定矩阵公理库正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。，就存在 $q$ 使 $q^{\mathrm{\top }}Sq<0$。取 $X=q{q}^{\mathrm{\top }}⪰0$，便有 $\mathrm{tr}(SX)=q^{\mathrm{\top }}Sq<0$。因此 $({\mathbb{S}}_{+}^n{)}^{\ast }={\mathbb{S}}_{+}^n$。

在二阶情形，迹内积特别容易漏掉非对角项的系数：

所以测量 $A(X)=X_{12}$ 的伴随不是把 $y$ 原样填入两个非对角位置，而是 $A^{\ast }y=\left(\begin{array}{cc}0& y/2\\ y/2& 0\end{array}\right)$。

以下四个例子只需二阶判据：$\left(\begin{array}{cc}u& z\\ z& v\end{array}\right)⪰0$ 当且仅当 $u,v\ge 0$ 且 $uv\ge z^2$。由此可见，半正定矩阵的某个对角元为零时，对应行与列都必须为零：一般维数中对每个二阶主子矩阵应用 $X_{ii}{X}_{jj}\ge X_{ij}^2$ 即可。

一对最优解：把上下界都算到 2 ​

考虑

这里 $C=I$，对偶为 $maxy$，约束是 $S=\left(\begin{array}{cc}1& -y/2\\ -y/2& 1\end{array}\right)⪰0$。取

两个矩阵的特征值均为 $0,2$，所以原、对偶均可行。原目标 $\mathrm{tr}{X}^{\ast }=2$，对偶目标 $y^{\ast }=2$；进一步 $S^{\ast }{X}^{\ast }=0$，故迹内积也为零。弱对偶已经完成最优性证明。此例还满足两侧严格可行性：$\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)\succ 0$ 是原始严格可行点，$y=0$ 给出对偶松弛 $I\succ 0$。Slater 定理能预告证书存在，具体矩阵则把证书交到手中。

一个不可行性证书：负的对角元 ​

系统 $X_{11}=-1,X⪰0$ 不可行。写成 $A(X)=X_{11}$、$b=-1$，取 $w=1$，就有 $A^{\ast }w=E_{11}⪰0$ 而 $bw=-1<0$。证书只需检查一个半正定矩阵和一个严格负标量，不必尝试搜索所有 $X$。

零间隙，但对偶最优值取不到 ​

考虑

零对角元迫使 $X_{12}=0$，所以唯一可行矩阵是 $\mathrm{diag}(0,1)$，且 $p^{\ast }=0$。目标矩阵是 $C=\left(\begin{array}{cc}0& 1/2\\ 1/2& 0\end{array}\right)$，故对偶为

非零的非对角元迫使两个对角元都严格为正，特别是 $y_2<0$。另一方面，对任意 $t>0$，取 $y_1=-t$、$y_2=-1/(4t)$，得到对角元为正、行列式为零的半正定松弛，且目标 $-1/(4t)\to 0$。因此 $d^{\ast }=p^{\ast }=0$，却没有对偶最优解。原可行集没有正定矩阵，原始 Slater 条件缺失；此处失去的是可达性，而非最优值相等。对偶本身严格可行，例如 $y_1=y_2=-1$，与原最优值确实可达相符。

弱不可行：残差消失，矩阵却逃向无穷 ​

现在要求 $X_{11}=0,X_{12}=1,X⪰0$。零对角元与非零非对角元矛盾；等价地，任意满足等式的矩阵 $\left(\begin{array}{cc}0& 1\\ 1& v\end{array}\right)$ 都有行列式 $-1$，所以系统不可行。但对每个 $\epsilon >0$，

其半正定性由非负对角元和零行列式直接给出。将左上角改为零便落入等式仿射空间，Frobenius 距离恰为 $\epsilon$；反向距离下界也由左上角差值给出。因此半正定锥与等式空间虽不相交，距离却为零。这称为弱不可行。$X_{22}=1/\epsilon \to \mathrm{\infty }$，序列没有有限矩阵极限，不能用锥的闭性推出可行解。

图中 $u=X_{11}$、$v=X_{22}$；绘图区只截取有限窗口，向上箭头表示序列继续离开窗口。直线 $u=0$ 是不可行的等式条件，绝不是半正定区域里的一条边界射线。

这个系统甚至没有前述严格不可行性证书。因为 $A(X)=(X_{11},X_{12})$、$b=(0,1)$，任何候选 $w$ 都须满足

右下角为零迫使 $w_2=0$，于是 $b^{\mathrm{\top }}w=w_2=0$，不可能严格为负。这里是这种线性证书不存在，并不意味着不能通过其他推理或扩展证书证明不可行。

证书完备性取决于线性像的闭性 ​

严格不可行性证书存在，当且仅当 $b\notin \overline{A(K)}$。一个方向直接来自连续性：若 $A^{\ast }w\in K^{\ast }$，则 $w^{\mathrm{\top }}z\ge 0$ 对 $z\in A(K)$ 及其闭包均成立，故 $w^{\mathrm{\top }}b<0$ 把 $b$ 排除在闭包之外。反方向调用有限维闭凸集的严格分离定理，将 $b$ 与闭凸锥 $\overline{A(K)}$ 分离。锥包含零且可任意正向缩放，分离泛函必可写成在该锥上非负、在 $b$ 处严格负的 $w$，恰好得到所需证书。

因此，当 $A(K)$ 闭时，不可行就必有这样的证书；多面锥的线性像仍是多面锥，LP 属于这一情形。闭锥的线性像一般未必闭。上面的弱不可行例子恰有

若 $a>0$，选择 $X_{22}=z^2/a$ 即可实现任意 $z$；若 $a=0$，半正定性迫使 $z=0$。于是 $b=(0,1)$ 不在这个像中，却在它的闭包中，证书的缺失有了精确的几何原因。

从求得一个点到证明一个结论 ​

对精确可行的原、对偶点，弱对偶给出

这把两侧目标差变成最优性误差上界。在半正定规划松弛公理库半正定规划松弛semidefinite relaxation · SDP relaxation把 ±1 二次变量提升为单位向量或 Gram 矩阵，获得可凸优化的上界并连接随机舍入。中，它能认证连续松弛的求解精度；从松弛回到离散问题的保证，仍需该问题的舍入分析。实际核验应先确认等式约束与半正定性，再使用目标差。弱不可行例子尤其说明：即使等式残差可以任意小，也不能仅凭残差宣告存在精确可行点。