半定规划

半定规划（semidefinite programming，SDP）在实对称半正定矩阵约束及仿射约束下优化线性目标。它把逐个标量的不等式推广为对所有方向都成立的二次型不等式；“每个元素都非负”与“半正定”是不同条件。

一个二阶矩阵的最小迹

考虑 $$\underset{x,y}{min}x+y,M(x,y)=\left(\begin{array}{cc}x& 1\\ 1& y\end{array}\right)⪰0.$$ 半正定要求对每个 $v\in {ℝ}^2$ 有 $v^{𝖳}Mv\ge 0$。取标准基得到x、y非负；x若为零，取 $v=(u,1)$ 便有 $2u+y$，选很负的u会违反，故本例x必须正。再配方： $$x{u}^2+2uv+y{v}^2=x(u+v/x{)}^2+(y-1/x)v^2.$$ 所以约束等价于 $x>0,y\ge 1/x$，即正象限内xy至少一。

可行区域在正象限双曲线上方，目标下界线在 (1,1) 接触边界。

最优性可以不求导就证明：对方向 $v=(1,-1)$，有 $v^{𝖳}Mv=x+y-2\ge 0$。因此目标至少二；取x=y=1时矩阵为 $(\genfrac{}{}{0ex}{}{1}{1})(1,1)$，对任意方向的二次型是 $(u+v{)}^2\ge 0$，确为可行并达到二。这里一个特定方向提供目标下界，完整半正定验证提供可行上界，两者闭合才证明最优。

线性矩阵不等式的含义

记 ${𝕊}^k$ 为k阶实对称矩阵空间，${𝕊}_{+}^k$ 为其中半正定者。一般形式为 $$min{c}^{𝖳}x,F_0+\sum _{i=1}^n{x}_i{F}_i⪰0,Ax=b,$$ 其中 $F_i\in {𝕊}^k$、$x\in {ℝ}^n$。矩阵随变量仿射变化，所以称线性矩阵不等式，虽然由它限定的标量可行域未必是多面体。主例消元后出现xy，正说明了这一点。

矩阵锥凸性直接来自定义：若P、Q半正定且 $0\le \theta \le 1$，任意方向v都满足 $v^{𝖳}[\theta P+(1-\theta )Q]v=\theta v^{𝖳}Pv+(1-\theta )v^{𝖳}Qv\ge 0$。故其仿射原像凸，线性目标上的SDP是凸优化。另一标准形式使用对称矩阵变量X、目标 $\mathrm{tr}(CX)$、约束 $\mathrm{tr}(A_{i}X)=b_i$ 及 $X⪰0$。

较小特征值在 s=1 变为零；半正定范围为 s≥1。

对称性在定义中不可省略。非对称矩阵的二次型只看见其对称部分，不能由二次型非负就把它归入这里的对称锥。即使矩阵对称，只有对角非负也不够：$\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ 的元素全为正，却在方向 $(1,-1)$ 上给出负二，其特征值为三和负一。半正定也允许零特征值，主例最优矩阵就有特征值二和零，不是正定。

变式与低维证书计算

把固定非对角元改为实数c，约束为 $\left(\begin{array}{cc}x& c\\ c& y\end{array}\right)⪰0$。取方向 $(1,-\mathrm{sign}c)$（c为零时任取正负号），得到 $x+y\ge 2|c|$。取 $x=y=|c|$ 时二次型为 $|c|(u+\mathrm{sign}(c)v{)}^2$，达到此界。因此变式c=−2的最优点为x=y=2，目标四，负的非对角元完全可以出现在半正定矩阵中。

下例只用标准库，输入固定非对角元c，返回解析最优矩阵、特征值及方向下界，不改写输入。二阶对称矩阵的特征值为 $(x+y\pm \sqrt{(x-y{)}^2+4c^2})/2$，代码用它复核。固定二阶成本为常数；一般稠密k阶对称特征值分解约为 $O(k^3)$，数值容差下接近零的特征值还需结合残差解释。

Python 3

import math

def sdp_minimum_trace(off_diagonal=1.0):
    c = float(off_diagonal)
    x = y = abs(c)
    discriminant = math.hypot(x-y,2*c)
    eigenvalues = ((x+y-discriminant)/2,(x+y+discriminant)/2)
    sign = 1 if c >= 0 else -1
    direction_value = x+y-2*sign*c
    return ((x,c),(c,y)),eigenvalues,2*abs(c),direction_value

for c in (1,-2,0):
    print(c,sdp_minimum_trace(c))
assert sdp_minimum_trace(-2)[1] == (0.0,4.0)