第2章：凸集、投影与分离

凸包与锥

集合 C 凸，当且仅当任意两点连线段都在 C 中。有限点的凸包由非负且和为 1 的系数加权组合构成；凸锥则对非负倍数与相加封闭。

半空间 $a^Tx\le b$ 、仿射子空间 $Ax=b$ 、范数球和半正定矩阵锥都是重要例子。凸集的交以及仿射像仍凸，任意并集则未必凸。

对非空闭凸集 C，投影定义为

\Pi_C(z)=\arg\min_{x\in C}\frac12\|x-z\|_2^2.

闭性与距离目标的强制性保证存在，严格凸性保证唯一。若 C 不凸，投影可能不唯一，例如原点到两个对称点。

令 $p=\Pi_C(z)$ ，沿任意可行线段 $p+t(x-p)$ 考察距离平方在 $t=0$ 的右导数，可得

\langle z-p,x-p\rangle\le0,\qquad\forall x\in C.

反过来展开 $\|z-x\|^2$ ，该不等式也足以证明 p 是最近点。这是投影的变分刻画。

投影到 $C=\{x:a^Tx\le b\}$ ，若 z 已可行则不动；否则最近点沿法向量移动：

\Pi_C(z)=z-\frac{a^Tz-b}{\|a\|^2}a.

对 $x_1+x_2\le1$ ，将 $z=(2,1)$ 投影，超出量为 2， $\|a\|^2=2$ ，结果是 $(1,0)$ 。任意沿边界方向继续移动都会增加距离。

若 z 不在闭凸集 C 中，取投影 p，向量 $z-p$ 定义一个把 z 与 C 严格分开的超平面。分离定理将“点不可行”变成一个线性证据，这也是对偶思想的重要来源。

在 $x\in C$ 处定义法锥

N_C(x)=\{v:\langle v,y-x\rangle\le0,\ \forall y\in C\}.

边界上可以有非零法向量；内点的法锥通常只有零。约束最优点梯度不必为零，而可能与可行方向正交或指向无法继续下降的方向。