第8章：最优性证书与数值实验

可行不等于最优

求解器返回向量后，应分别检查约束残差和最优性残差。对 KKT 系统，可查看等式残差、不等式违反、驻点残差及互补松弛残差。

若有原可行 x 和对偶可行 y，弱对偶给出

$$0\le f_0(x)-p^*\le f_0(x)-g(y).$$

右侧的原对偶间隙是全局误差证书。任意两个近似数值之差不能直接作为证书，必须核对双方的可行性与数值误差。

缩放与病态

同一问题可以因单位不同而出现数值尺度悬殊。例如同时使用米与微米而未合理缩放，会使线性系统条件数和终止阈值解释变得困难。

目标值变化很小不保证接近最优点，平坦区域中离解很远也可能变化不大。梯度小、步长小、可行残差小分别是不同证据，不能互换。

一个可核对的实验

对 $f(x)=\tfrac12x^TQx-b^Tx$，取 $Q=\operatorname{diag}(1,100)$、$b=(1,1)$。精确最优为 $(1,0.01)$，可用于比较梯度法与牛顿法。

从零出发，梯度法步长 0.01，第一步为 $(0.01,0.01)$；第二坐标立即到解，第一坐标缓慢收敛。牛顿法解 $Qd=b$，全步直接到最优。该例展示曲率不均衡，并不能证明牛顿法在大规模问题总比梯度法便宜，因为每步成本不同。

建模误差

最优解只对给定数据与目标最优。拟合误差很小可能来自过拟合；鲁棒模型只防护规定的不确定集合；正则化改变了目标，不能把其解称为原无正则问题的精确解。

综合练习

1. 对带非负约束的最小二乘问题写 KKT，并解释边界坐标的梯度符号。
2. 比较不同条件数二次函数的迭代次数和总计算时间，明确终止指标。
3. 为一个实际资源分配问题写出变量单位、约束、凸性证明、存在性条件和可检查的最优性证书。