凸集分离：投影、Farkas 与 Gordan 定理

凸集分离定理把“两个集合不相交”翻译成“存在一个线性函数把它们分开”。线性规划对偶、最优性条件和二择一定理都建立在这座桥上。

凸集与投影

集合 $C$ 凸，当且仅当

x,y\in C, \theta\in[0,1] \Longrightarrow \theta x+(1-\theta)y\in C.

若 $C$ 非空、闭、凸，则任意点 $x$ 在 $C$ 上存在唯一欧氏投影

p=P_C(x)=\arg\min_{z\in C}\lVert x-z\rVert.

投影满足

(x-p)^T(z-p)\le0,\qquad \forall z\in C.

几何上，从 $p$ 指向 $x$ 的向量是集合在 $p$ 处的外法向量。这条不等式已经给出一个支撑超平面。

若点 $x\notin C$ 且 $C$ 闭凸，取 $p=P_C(x)$ ，则超平面

(x-p)^Tz=(x-p)^Tp

把 $x$ 与 $C$ 严格分开。更一般地，两个互不相交凸集在适当闭性/紧性条件下可被超平面分离。

证明题的常见套路：

以下两个系统恰有一个有解：

Ax=b,\qquad x\ge0,

或

A^Ty\ge0,\qquad b^Ty<0.

若前者有解，则

b^Ty=x^TA^Ty\ge0,

不可能满足后者。若前者无解，点 $b$ 不在由 $A$ 各列生成的凸锥中，分离定理保证存在这样的 $y$ 。

$y$ 是“不可行证书”：只需检查两个矩阵不等式，就能证明原系统无解。

常用版本说，下列两个系统恰有一个可解：

Ax>0

或

A^Ty=0,\qquad y\ge0, y\ne0.

它常用于证明不存在同时严格改善所有活动约束的方向，进而导出 Fritz John 乘子。

对多面锥

C=\{x:Ax=0,x\ge0\},

非零方向的存在可转化为线性方程与非负性系统。Farkas/Gordan 提供两种互斥描述：要么有一个可行方向，要么有一组非负法向量构成阻挡证书。