线性规划

一般形式：
max ⁡ c T x  s.t.  A x ≤ b x ≥ 0

maxcTx s.t. Ax≤bx≥0​
其中$\mathbf{A}\in {\mathbb{R}}^{m\times n},\mathbf{b}\in {\mathbb{R}}^m,\mathbf{x}\in {\mathbb{R}}^n$

标准形式：
max ⁡ c T x  s.t.  A x = b x ≥ 0

maxcTx s.t. Ax=bx≥0​
其中$\mathbf{A}\in {\mathbb{R}}^{m\times n},\mathbf{b}\in {\mathbb{R}}^m,\mathbf{x}\in {\mathbb{R}}^n$

极点

设$C\subseteq {\mathbb{R}}^n$是一个非空闭凸集，$\bar{\mathbf{x}}\in C$
如果不存在${\mathbf{x}}_1,{\mathbf{x}}_2\in C,\lambda \in \left(0,1\right)$,使得$\bar{\mathbf{x}}=\lambda {\mathbf{x}}_1+(1-\lambda ){\mathbf{x}}_2$
则$\bar{\mathbf{x}}$是$C$的一个极点(extreme point)

存在性

设$C\subseteq {\mathbb{R}}^n$是一个非空闭凸集，则$C$有极点当且仅当$C$不包含直线

证明：
$\Rightarrow$设$C\in {\mathbb{R}}^n$是一个非空闭凸集，$\bar{\mathbf{x}}$是$C$的一个极点

假设$C$包含直线，即 ∃ x ∈ C ,   s . t . { x + α d ∣ α ∈ R , d ∈ R n } ⊆ C \exists \mathbf{x}\in C,\ s.t.\left\{\mathbf{x}+\alpha \mathbf{d}|\alpha \in\mathbb{R},\mathbf{d}\in\mathbb{R}^n\right\}\subseteq C ∃x∈C, s.t.{x+αd∣α∈R,d∈Rn}⊆C
令
$${\mathbf{x}}^{(n)}=\left(1-\frac{1}{n}\right)\bar{\mathbf{x}}+\frac{1}{n}\left(\mathbf{x}+n\mathbf{d}\right)$$
因为$C$是凸的，所以${\mathbf{x}}^{(n)}\in C$
因为$C$是闭的，所以${\left\{{\mathbf{x}}^{(i)}\right\}}_{i=1}^{\infty }\in C$
于是
$$\underset{n\to \infty }{\lim }{\mathbf{x}}^{(n)}=\bar{\mathbf{x}}+\mathbf{d}\in C$$
同理$\bar{\mathbf{x}}-\mathbf{d}\in C$

但是
$$\frac{1}{2}\left(\bar{\mathbf{x}}+\mathbf{d}\right)+\frac{1}{2}\left(\bar{\mathbf{x}}-\mathbf{d}\right)=\bar{\mathbf{x}}\in C$$
与$\bar{\mathbf{x}}$是极点矛盾
所以$C$不包含直线
$\Leftarrow$设$C\in {\mathbb{R}}^n$是一个非空闭凸集,且不包含直线
考虑对维度进行数学归纳法

当$C\subseteq \mathbb{R}$时，$C$是一个线段，极点就是两个端点
假设$C\subseteq {\mathbb{R}}^{n-1}$时成立
当$C\subseteq {\mathbb{R}}^n$时，
因为不包含直线，所以存在边界点$x$ （感觉时对的，但是不知道怎么严格证明）
由支撑超平面定理，存在超平面$H_{\mathbf{x}}=\left\{\mathbf{z}|{\mathbf{a}}^T\mathbf{x}={\mathbf{a}}^T\mathbf{z}\right\}$,其中$\mathbf{a}\in {\mathbb{R}}^n$
于是$\forall \mathbf{y}\in C,{\mathbf{a}}^T\mathbf{y}\le {\mathbf{a}}^T\mathbf{x}$
因此$C\cap H_{\mathbf{x}}\subseteq {\mathbb{R}}^{n-1}$,由假设$C\cap H_{\mathbf{x}}$存在极点$\bar{\mathbf{x}}$

现在证明$\bar{\mathbf{x}}$也是$C$的极点

设${\mathbf{x}}_1,{\mathbf{x}}_2\in C,\lambda \in \left(0,1\right),s.t.\bar{\mathbf{x}}=\lambda {\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{x}}_2$
那么
$${\mathbf{a}}^T\bar{\mathbf{x}}=\lambda {\mathbf{a}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{a}}^T{\mathbf{x}}_2$$
因为$H_{\mathbf{x}}$是支撑超平面，${\mathbf{x}}_1,{\mathbf{x}}_2\in C,\bar{\mathbf{x}}\in H_{\mathbf{x}}$，
所以${\mathbf{a}}^T{\mathbf{x}}_1\le {\mathbf{a}}^T\bar{\mathbf{x}},{\mathbf{a}}^T{\mathbf{x}}_2\le {\mathbf{a}}^T\bar{\mathbf{x}}$

但是
$$\begin{gathered} {\mathbf{a}}^T{\mathbf{x}}_1\le \lambda {\mathbf{a}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{a}}^T{\mathbf{x}}_2\Rightarrow {\mathbf{a}}^T{\mathbf{x}}_1\le {\mathbf{a}}^T{\mathbf{x}}_2 \\ {\mathbf{a}}^T{\mathbf{x}}_2\le \lambda {\mathbf{a}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{a}}^T{\mathbf{x}}_2\Rightarrow {\mathbf{a}}^T{\mathbf{x}}_2\le {\mathbf{a}}^T{\mathbf{x}}_1 \end{gathered}$$
于是
$${\mathbf{a}}^T{\mathbf{x}}_1={\mathbf{a}}^T{\mathbf{x}}_2={\mathbf{a}}^T\bar{\mathbf{x}}\Rightarrow \bar{\mathbf{x}}={\mathbf{x}}_1={\mathbf{x}}_2$$
于是$\bar{\mathbf{x}}$是极点

顶点

设$P$是一个多面体
如果存在$\mathbf{c}$，使得$\forall \mathbf{y}\in P,\mathbf{y}\ne \mathbf{x}$,有${\mathbf{c}}^T\mathbf{y}<{\mathbf{c}}^T\mathbf{x}$,
则$x$为$P$的顶点(vertex)

活跃约束

考虑多面体$P=\left\{\mathbf{z}|{\mathbf{a}}_i^T\mathbf{z}\le b_i\right\}$
如果${\mathbf{a}}_i^T\mathbf{x}=b_i$，则称约束$i$在$\mathbf{x}$活跃(active,binding,tight)

基可行解

考虑多面体$P=\left\{\mathbf{z}|{\mathbf{a}}_i^T\mathbf{z}\le b_i\right\}$,$\mathbf{x}\in P,\mathbf{x}\in {\mathbb{R}}^n$
如果$\mathbf{x}$满足所有的约束，且有$n$个线性无关的活跃约束（${\mathbf{a}}_1,{\mathbf{a}}_2,\cdots ,{\mathbf{a}}_n$线性无关），
则$\mathbf{x}$称为基可行解（basic feasible solution, BFS）

基可行解、极点、顶点等价

设$\mathbf{x}\in P=\left\{\mathbf{z}|{\mathbf{a}}_i^T\mathbf{z}\le b_i\right\},\mathbf{x}\in {\mathbb{R}}^n$，则下面3个等价
1）$\mathbf{x}$是顶点
2）$\mathbf{x}$是极点
3）$\mathbf{x}$是BFS

证明：
$1)\Rightarrow 2)$
设${\mathbf{x}}_1,{\mathbf{x}}_2\in P,\lambda \in \left[0,1\right],s.t.\mathbf{x}=\lambda {\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{x}}_2$
如果$\lambda =0$或者$\lambda =1$,则$\mathbf{x}$为极点
如果$\lambda \in \left(0,1\right)$,
因为$\mathbf{x}$是顶点，$\exists \mathbf{c},\forall \mathbf{y}\in P,\mathbf{y}\ne \mathbf{x},s.t.{\mathbf{c}}^T\mathbf{y}<{\mathbf{c}}^T\mathbf{x}$
所以${\mathbf{c}}^T{\mathbf{x}}_1<{\mathbf{c}}^T\mathbf{x},{\mathbf{c}}^T{\mathbf{x}}_2<{\mathbf{c}}^T\mathbf{x}$
又因为${\mathbf{c}}^T{\mathbf{x}}_1<{\mathbf{c}}^T\left(\lambda {\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{x}}_2\right)\Rightarrow {\mathbf{c}}^T{\mathbf{x}}_1<{\mathbf{c}}^T{\mathbf{x}}_2$
${\mathbf{c}}^T{\mathbf{x}}_2<{\mathbf{c}}^T\left(\lambda {\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{x}}_2\right)\Rightarrow {\mathbf{c}}^T{\mathbf{x}}_2<{\mathbf{c}}^T{\mathbf{x}}_1$
矛盾
所以$\mathbf{x}$是极点

$2)\Rightarrow 3)$
假设$\mathbf{x}$不是BFS
设$\mathbf{x}$使得前k个约束活跃$(k<n)$
即${\mathbf{a}}_i^T\mathbf{x}=b_i,i=1,2,\cdots ,k$
令 A ~ = ( a 1 T a 2 T ⋮ a k T ) \tilde{\mathbf{A}}=

A~=⎝ ⎛​a1T​a2T​⋮akT​​⎠ ⎞​
则$\tilde{\mathbf{A}}\mathbf{x}=0$有非零解
设$\mathbf{d}\ne 0,\tilde{\mathbf{A}}\mathbf{d}=0$
存在$ϵ>0$，使得$\mathbf{x}+ϵ\mathbf{d},\mathbf{x}-ϵ\mathbf{d}\in P$
$$\mathbf{x}=\frac{1}{2}\left(\mathbf{x}+ϵ\mathbf{d}\right)+\frac{1}{2}\left(\mathbf{x}-ϵ\mathbf{d}\right)$$
$\mathbf{x}$不是极点，矛盾
所以$\mathbf{x}$是BFS

$3)\Rightarrow 1)$
因为$\mathbf{x}$是BFS，设 A ~ = ( a 1 T a 2 T ⋮ a n T ) , b ~ = ( b 1 b 2 ⋮ b n ) , A ~ x = b ~ \tilde{\mathbf{A}}=

,\tilde{\mathbf{b}}=,\tilde{\mathbf{A}}\mathbf{x}=\tilde{\mathbf{b}} A~=⎝ ⎛​a1T​a2T​⋮anT​​⎠ ⎞​,b~=⎝ ⎛​b1​b2​⋮bn​​⎠ ⎞​,A~x=b~
因为$\tilde{\mathbf{A}}$可逆，所以$\tilde{\mathbf{A}}\mathbf{x}=\tilde{\mathbf{b}}$有唯一解
令$\mathbf{c}={\sum }_{i=1}^n{\mathbf{a}}_i$
${\mathbf{c}}^T\mathbf{x}={\sum }_{i=1}^n{b}_i$
$\forall \mathbf{y}\ne \mathbf{x},\mathbf{y}\in P,s.t.{\mathbf{c}}^T\mathbf{y}<{\sum }_{i=1}^n{b}_i={\mathbf{c}}^T\mathbf{x}$
所以$\mathbf{x}$是顶点

极点的最优性

设 P = { x ∈ R n ∣ A x ≤ b } P=\left\{\mathbf{x}\in\mathbb{R}^n|\mathbf{Ax}\le \mathbf{b}\right\} P={x∈Rn∣Ax≤b}
考虑线性规划问题$LP:\max \left\{{\mathbf{c}}^T\mathbf{x}|\mathbf{x}\in P\right\}$
如果$P$至少有一个极点，并且LP有最优解，那么至少有一个最优解是$P$的一个极点

证明：
设${\alpha }^{\ast }$是最优解，$O=\left\{\mathbf{x}\in P|{\mathbf{c}}^T\mathbf{x}={\alpha }^{\ast }\right\}\subseteq P$
因为$P$有极点，所以$P$不包含直线，因此$O$不包含直线，于是$O$存在极点$\bar{\mathbf{x}}$

设${\mathbf{x}}_1,{\mathbf{x}}_2\in P,\lambda \in \left(0,1\right),s.t.\bar{\mathbf{x}}=\lambda {\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{x}}_2$
$${\mathbf{c}}^T\bar{\mathbf{x}}=\lambda {\mathbf{c}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{c}}^T{\mathbf{x}}_2$$

因为${\alpha }^{\ast }$是最优解，所以
${\mathbf{c}}_1^T\mathbf{x}\le {\mathbf{c}}^T\bar{\mathbf{x}}={\alpha }^{\ast }$
${\mathbf{c}}_2^T\mathbf{x}\le {\mathbf{c}}^T\bar{\mathbf{x}}={\alpha }^{\ast }$
但是
$$\begin{gathered} {\mathbf{c}}^T{\mathbf{x}}_1\le \lambda {\mathbf{c}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{c}}^T{\mathbf{x}}_2\Rightarrow {\mathbf{c}}^T{\mathbf{x}}_1\le {\mathbf{c}}^T{\mathbf{x}}_2 \\ {\mathbf{c}}^T{\mathbf{x}}_2\le \lambda {\mathbf{c}}^T{\mathbf{x}}_1+\left(1-\lambda \right){\mathbf{c}}^T{\mathbf{x}}_2\Rightarrow {\mathbf{c}}^T{\mathbf{x}}_2\le {\mathbf{c}}^T{\mathbf{x}}_1 \end{gathered}$$
$${\mathbf{c}}^T{\mathbf{x}}_1={\mathbf{c}}^T{\mathbf{x}}_2={\mathbf{c}}^T\bar{\mathbf{x}}\Rightarrow \bar{\mathbf{x}}={\mathbf{x}}_1={\mathbf{x}}_2$$
于是$\bar{\mathbf{x}}$是极点

以前高中做线性规划，只知道最优解肯定在顶点上，然而并不知道为啥，上面这个就是证明

参考
https://people.seas.harvard.edu/~yaron/AM221-S16/lecture_notes/AM221_lecture7.pdf
http://math.sfsu.edu/serkan/math430/lecture4.pdf