第5章：二次规划、锥规划与建模

标准问题族

线性规划有线性目标和仿射约束；凸二次规划的目标 Hessian 半正定；二阶锥规划包含范数不等式；半正定规划包含仿射矩阵落在半正定锥中的约束。

它们不是互相毫无联系的算法目录。标准形式让通用求解器利用特定锥的几何和线性代数结构，同时为模型提供统一的对偶与最优性证书。

最小二乘与正则化

岭回归

$$\min_x\frac12\|Ax-b\|^2+\frac\lambda2\|x\|^2$$

在 $\lambda>0$ 时强凸，最优点满足 $(A^TA+\lambda I)x=A^Tb$。这是最优性方程，不意味着数值实现应该显式求逆；矩阵分解通常更合适。

把二范数正则换成 $\lambda\|x\|_1$ 得到 Lasso。它仍凸，但会产生稀疏解，原因与零点处次梯度区间有关，不能把两种正则理解成只改一个平滑系数。

鲁棒约束

设系数不确定为 $a=a_0+u$，且 $\|u\|_2\le\rho$。要求对所有 u 都有 $a^Tx\le b$，等价于

$$a_0^Tx+\rho\|x\|_2\le b.$$

因为 $\sup_{\|u\|\le\rho}u^Tx=\rho\|x\|$，上界由沿 x 方向的 u 取得。这个鲁棒约束成为二阶锥形式。

这类模型保护的是所选不确定集合内部的扰动；实际误差若不在集合里，保证并不会自动延伸。

Schur 补与矩阵约束

当 $t>0$，块矩阵

$$\begin{pmatrix}tI&x\\x^T&s\end{pmatrix}\succeq0$$

等价于 $s\ge\|x\|^2/t$。可通过 Schur 补或配方验证。使用边界 $t=0$ 时需要单独处理，不能继续直接除以 t。

矩阵不等式中的半正定顺序不是逐元素非负。一个半正定矩阵可以含负的非对角项。

练习

1. 将 $\|Ax-b\|_2\le t$ 写成二阶锥约束并说明其凸性。
2. 用 Cauchy–Schwarz 推导鲁棒约束公式，并找出达到上界的扰动。
3. 给出一个含负非对角元的半正定矩阵。