凸集的学习

凸集

定义

如果 x , y ∈ C ⊆ R n \mathbf{x},\mathbf{y}\in C \subseteq \mathbb{R}^n x,y∈C⊆Rn,并且 λ ∈ [ 0 , 1 ] \lambda \in \left[0,1\right] λ∈[0,1], λ x + ( 1 − λ ) y ∈ C \lambda \mathbf{x} +(1-\lambda)\mathbf{y}\in C λx+(1−λ)y∈C,那么集合 C C C称为凸集

保凸运算

交集

设 ∀ i ∈ I , C i ⊆ R n \forall i \in I,C_{i}\subseteq \mathbb{R}^n ∀i∈I,Ci​⊆Rn是凸集，那么 ∩ i ∈ I C i \cap_{i\in I} C_i ∩i∈I​Ci​也是凸集

证明：

不妨设 x , y ∈ ∩ i ∈ I C i \mathbf{x},\mathbf{y}\in \cap_{i\in I} C_i x,y∈∩i∈I​Ci​,并且 λ ∈ [ 0 , 1 ] \lambda \in \left[0,1\right] λ∈[0,1]

因为 C i C_i Ci​是凸集

所以 ∀ i ∈ I , λ x + ( 1 − λ ) y ∈ C i \forall i \in I,\lambda \mathbf{x} +(1-\lambda)\mathbf{y}\in C_i ∀i∈I,λx+(1−λ)y∈Ci​

所以 λ x + ( 1 − λ ) y ∈ ∩ i ∈ I C i \lambda \mathbf{x} +(1-\lambda)\mathbf{y}\in \cap_{i\in I} C_i λx+(1−λ)y∈∩i∈I​Ci​

线性组合

设 C 1 , C 2 , ⋯   , C k ⊆ R n C_1,C_2,\cdots,C_k\subseteq \mathbb{R}^n C1​,C2​,⋯,Ck​⊆Rn是凸集，

设 μ 1 , μ 1 , ⋯   , μ k ∈ R \mu_1,\mu_1,\cdots,\mu_k\in\mathbb{R} μ1​,μ1​,⋯,μk​∈R

则

μ 1 C 1 + μ 2 C 2 + ⋯ + μ k C k = { ∑ i = 1 k μ i x i , i = 1 , 2 , ⋯   , k } \mu_1C_1+\mu_2C_2+\cdots+\mu_kC_k=\left\{\sum_{i=1}^{k}\mu_i\mathbf{x}_i,i=1,2,\cdots,k\right\} μ1​C1​+μ2​C2​+⋯+μk​Ck​={i=1∑k​μi​xi​,i=1,2,⋯,k}

是凸集

证明：

利用数学归纳法

n = 1 n=1 n=1显然成立

n = 2 n=2 n=2时

设 a , b ∈ C 1 \mathbf{a},\mathbf{b}\in C_1 a,b∈C1​

c , d ∈ C 2 \mathbf{c},\mathbf{d}\in C_2 c,d∈C2​

μ 1 a + μ 2 c ∈ μ 1 C 1 + μ 2 C 2 \mu_1\mathbf{a}+\mu_2\mathbf{c}\in \mu_1C_1+\mu_2C_2 μ1​a+μ2​c∈μ1​C1​+μ2​C2​

μ 1 b + μ 2 d ∈ μ 1 C 1 + μ 2 C 2 \mu_1\mathbf{b}+\mu_2\mathbf{d}\in \mu_1C_1+\mu_2C_2 μ1​b+μ2​d∈μ1​C1​+μ2​C2​

设 λ ∈ [ 0 , 1 ] \lambda \in \left[0,1\right] λ∈[0,1]

则

λ ( μ 1 a + μ 2 c ) + ( 1 − λ ) ( μ 1 b + μ 2 d ) = λ μ 1 a + ( 1 − λ ) μ 1 b + λ μ 2 c + ( 1 − λ ) μ 2 d \begin{aligned} &\quad \lambda(\mu_1\mathbf{a}+\mu_2\mathbf{c})+(1-\lambda)(\mu_1\mathbf{b}+\mu_2\mathbf{d})\\ &=\lambda\mu_1\mathbf{a}+(1-\lambda)\mu_1\mathbf{b}+ \lambda\mu_2\mathbf{c}+(1-\lambda)\mu_2\mathbf{d} \end{aligned} ​λ(μ1​a+μ2​c)+(1−λ)(μ1​b+μ2​d)=λμ1​a+(1−λ)μ1​b+λμ2​c+(1−λ)μ2​d​

因为 λ μ 1 a + ( 1 − λ ) μ 1 b ∈ μ 1 C 1 \lambda\mu_1\mathbf{a}+(1-\lambda)\mu_1\mathbf{b} \in \mu_1 C_1 λμ1​a+(1−λ)μ1​b∈μ1​C1​

λ μ 2 c + ( 1 − λ ) μ 2 d ∈ μ 2 C 2 \lambda\mu_2\mathbf{c}+(1-\lambda)\mu_2\mathbf{d}\in \mu_2 C_2 λμ2​c+(1−λ)μ2​d∈μ2​C2​

所以 λ ( μ 1 a + μ 2 c ) + ( 1 − λ ) ( μ 1 b + μ 2 d ) ∈ μ 1 C 1 + μ 2 C 2 \lambda(\mu_1\mathbf{a}+\mu_2\mathbf{c})+(1-\lambda)(\mu_1\mathbf{b}+\mu_2\mathbf{d})\in \mu_1C_1+\mu_2C_2 λ(μ1​a+μ2​c)+(1−λ)(μ1​b+μ2​d)∈μ1​C1​+μ2​C2​

所以是凸集

假设 n = k n=k n=k时成立

n = k + 1 n=k+1 n=k+1时，证明类似，

所以结论成立

笛卡尔积

设 ∀ i = 1 , 2 , ⋯   , m , C i ⊆ R k i \forall i=1,2,\cdots,m,C_i \subseteq \mathbb{R}^{k_i} ∀i=1,2,⋯,m,Ci​⊆Rki​是凸集

那么笛卡尔积

C 1 × C 2 × ⋯ × C m = { ( x 1 , x 2 , ⋯   , x m ) : x i ∈ C i , i = 1 , 2 , ⋯   , m } C_1\times C_2 \times \cdots\times C_m=\left\{(\mathbf{x_1},\mathbf{x_2},\cdots,\mathbf{x_m}):\mathbf{x_i}\in C_i,i=1,2,\cdots,m\right\} C1​×C2​×⋯×Cm​={(x1​,x2​,⋯,xm​):xi​∈Ci​,i=1,2,⋯,m}

是凸集

证明：

利用数学归纳法

当 n = 1 n=1 n=1时显然成立

当 n = 2 n=2 n=2时

设 x 1 , x 2 ∈ C 1 \mathbf{x_1},\mathbf{x_2}\in C_1 x1​,x2​∈C1​

y 1 , y 2 ∈ C 2 \mathbf{y_1},\mathbf{y_2}\in C_2 y1​,y2​∈C2​

( x 1 , y 1 ) ∈ C 1 × C 2 (\mathbf{x_1},\mathbf{y_1})\in C_1\times C_2 (x1​,y1​)∈C1​×C2​

( x 2 , y 2 ) ∈ C 1 × C 2 (\mathbf{x_2},\mathbf{y_2})\in C_1\times C_2 (x2​,y2​)∈C1​×C2​

λ ( x 1 , y 1 ) + ( 1 − λ ) ( x 2 , y 2 ) = ( λ x 1 , λ y 1 ) + ( ( 1 − λ ) x 2 , ( 1 − λ ) y 2 ) = ( λ x 1 + ( 1 − λ ) x 2 , λ y 1 + ( 1 − λ ) y 2 ) ∈ C 1 × C 2 \begin{aligned} &\quad \lambda (\mathbf{x_1},\mathbf{y_1})+(1-\lambda)(\mathbf{x_2},\mathbf{y_2})\\ &=(\lambda\mathbf{x_1},\lambda\mathbf{y_1})+((1-\lambda)\mathbf{x_2},(1-\lambda)\mathbf{y_2})\\ &=(\lambda\mathbf{x_1}+(1-\lambda)\mathbf{x_2},\lambda\mathbf{y_1}+(1-\lambda)\mathbf{y_2})\\ &\in C_1\times C_2 \end{aligned} ​λ(x1​,y1​)+(1−λ)(x2​,y2​)=(λx1​,λy1​)+((1−λ)x2​,(1−λ)y2​)=(λx1​+(1−λ)x2​,λy1​+(1−λ)y2​)∈C1​×C2​​

假设当 n = k n=k n=k时成立

当 n = k + 1 n=k+1 n=k+1时

证明类似

所以结论成立

仿射变换

设 M ⊆ R n M\subseteq \mathbb{R}^n M⊆Rn是凸集， A ∈ R m × n \mathbf{A}\in\mathbb{R}^{m\times n} A∈Rm×n,则

A ( M ) = { A x : x ∈ M } \mathbf{A}(M)=\left\{\mathbf{Ax}:\mathbf{x}\in M\right\} A(M)={Ax:x∈M}

是凸集

逆仿射变换

设 D ⊆ R m D\subseteq \mathbb{R}^m D⊆Rm是凸集， A ∈ R m × n \mathbf{A}\in\mathbb{R}^{m\times n} A∈Rm×n,则

A − 1 ( D ) = { x ∈ R n : A x ∈ D } \mathbf{A}^{-1}(D)=\left\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{Ax}\in D\right\} A−1(D)={x∈Rn:Ax∈D}

是凸集

unit-simplex

简单来说就是一个向量，他的分量都是非负的，且加起来为1

Δ n = { x ∈ R n : x ≥ 0 , e T x = 1 } \Delta_n=\left\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{x}\ge0,\mathbf{e}^T\mathbf{x}=1\right\} Δn​={x∈Rn:x≥0,eTx=1}

凸包

凸组合

给定 k k k个向量 x 1 , ⋯   , x k ∈ R n \mathbf{x}_1,\cdots,\mathbf{x}_k\in\mathbb{R}^n x1​,⋯,xk​∈Rn

凸组合就是 λ 1 x 1 + ⋯ + λ k x k \lambda_1\mathbf{x}_1+\cdots+\lambda_k\mathbf{x}_k λ1​x1​+⋯+λk​xk​

其中 λ i ≥ 0 , λ 1 + ⋯ + λ k = 1 \lambda_i\ge 0,\lambda_1+\cdots+\lambda_k=1 λi​≥0,λ1​+⋯+λk​=1

定理1

设 C ∈ R n C\in\mathbb{R}^n C∈Rn是凸集， x 1 , x 2 , ⋯   , x m ∈ C \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_m\in C x1​,x2​,⋯,xm​∈C

则

∀ λ ∈ Δ m , ∑ i = 1 m λ i x i ∈ C \forall \lambda \in \Delta_m,\sum\limits_{i=1}^{m}\lambda_i \mathbf{x}_i\in C ∀λ∈Δm​,i=1∑m​λi​xi​∈C

证明：

用数学归纳法

当 n = 1 n=1 n=1时显然成立

假设当 n = m n=m n=m时成立

当 n = m + 1 n=m+1 n=m+1时

z = ∑ i = 1 m + 1 λ i x i = ∑ i = 1 m λ i x i + λ m + 1 x m + 1 = ( 1 − λ m + 1 ) ∑ i = 1 m λ i ( 1 − λ m + 1 ) x i + λ m + 1 x m + 1 ∈ C \begin{aligned} \mathbf{z}&=\sum\limits_{i=1}^{m+1}\lambda_i\mathbf{x}_i\\ &=\sum\limits_{i=1}^{m}\lambda_i\mathbf{x}_i+\lambda_{m+1}\mathbf{x}_{m+1}\\ &=(1-\lambda_{m+1})\sum\limits_{i=1}^{m}\frac{\lambda_i}{(1-\lambda_{m+1})}\mathbf{x}_i+\lambda_{m+1}\mathbf{x}_{m+1}\\ &\in C \end{aligned} z​=i=1∑m+1​λi​xi​=i=1∑m​λi​xi​+λm+1​xm+1​=(1−λm+1​)i=1∑m​(1−λm+1​)λi​​xi​+λm+1​xm+1​∈C​

所以成立

凸包定义

设 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn

则 S S S的凸包记为 c o n v ( S ) conv(S) conv(S)

c o n v ( S ) ≡ { ∑ i = 1 k λ i x i : x 1 , ⋯   , x k ∈ S , λ ∈ Δ k , k ∈ N } conv(S)\equiv\left\{\sum\limits_{i=1}^{k}\lambda_i\mathbf{x}_i:\mathbf{x}_1,\cdots,\mathbf{x}_k\in S,\lambda\in\Delta_k,k\in\mathbb{N}\right\} conv(S)≡{i=1∑k​λi​xi​:x1​,⋯,xk​∈S,λ∈Δk​,k∈N}

也就是能包住S的凸集中，最小的那个

引理

设 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn,如果 S ⊆ T S\subseteq T S⊆T，且 T T T是一个凸集，则 c o n v ( S ) ⊆ T conv(S)\subseteq T conv(S)⊆T

证明：

存在 x 1 , ⋯   , x k ∈ S ⊆ T \mathbf{x_1},\cdots,\mathbf{x}_k\in S\subseteq T x1​,⋯,xk​∈S⊆T

设 λ ∈ Δ k , z = ∑ i = 1 k λ k x i \lambda \in \Delta_k,\mathbf{z}=\sum_{i=1}^{k}\lambda_k\mathbf{x}_i λ∈Δk​,z=∑i=1k​λk​xi​

因为 T T T是凸集，所以 x 1 , ⋯   , x k \mathbf{x_1},\cdots,\mathbf{x}_k x1​,⋯,xk​的凸组合也属于 T T T,即 z ∈ T \mathbf{z}\in T z∈T

根据凸包的定义 z ∈ c o n v ( S ) \mathbf{z}\in conv(S) z∈conv(S)

所以 c o n v ( S ) ⊆ T conv(S)\subseteq T conv(S)⊆T

Carathéodory 定理

设 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn, x ∈ c o n v ( S ) \mathbf{x}\in conv(S) x∈conv(S)

则存在 x 1 , ⋯   , x n + 1 ∈ S \mathbf{x_1},\cdots,\mathbf{x}_{n+1} \in S x1​,⋯,xn+1​∈S,使得 x ∈ c o n v ( { x 1 , ⋯   , x n + 1 } ) \mathbf{x}\in conv(\left\{\mathbf{x_1},\cdots,\mathbf{x}_{n+1}\right\}) x∈conv({x1​,⋯,xn+1​})

即

∃ λ ∈ Δ n + 1 , x = ∑ i = 1 n + 1 λ i x i \exists \lambda\in\Delta_{n+1},\mathbf{x}=\sum_{i=1}^{n+1}\lambda_i\mathbf{x}_i ∃λ∈Δn+1​,x=i=1∑n+1​λi​xi​

证明：

设 x ∈ c o n v ( S ) \mathbf{x}\in conv(S) x∈conv(S)

根据凸包的定义，存在 x 1 , ⋯   , x n + 1 ∈ S , λ ∈ Δ k \mathbf{x_1},\cdots,\mathbf{x}_{n+1} \in S,\lambda\in\Delta_k x1​,⋯,xn+1​∈S,λ∈Δk​使得

x = ∑ i = 1 k λ i x i \mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i x=i=1∑k​λi​xi​

不放假设 ∀ i = 1 , 2 , ⋯   , k , λ i > 0 \forall i=1,2,\cdots,k, \lambda_i>0 ∀i=1,2,⋯,k,λi​>0,否则，我们可以删去 λ i = 0 \lambda_i=0 λi​=0对应的 x i \mathbf{x}_i xi​

如果 k ≤ n + 1 k\le n+1 k≤n+1

则结论成立

如果 k ≥ n + 2 k \ge n+2 k≥n+2

x 2 − x 1 , x 3 − x 1 , ⋯   , x k − x 1 \mathbf{x}_2-\mathbf{x}_1,\mathbf{x}_3-\mathbf{x}_1,\cdots,\mathbf{x}_{k}-\mathbf{x}_1 x2​−x1​,x3​−x1​,⋯,xk​−x1​线性相关

即不全为0的 μ 2 , ⋯   , μ k \mu_2,\cdots,\mu_k μ2​,⋯,μk​,使得

∑ i = 2 k μ i ( x i − x 1 ) = 0 \sum_{i=2}^{k}\mu_i(\mathbf{x}_i-\mathbf{x}_1)=0 i=2∑k​μi​(xi​−x1​)=0

设 μ 1 = − ∑ i = 2 k μ i \mu_1=-\sum_{i=2}^{k}\mu_i μ1​=−∑i=2k​μi​，则

∑ i = 1 k μ i x i = 0 \sum_{i=1}^{k}\mu_i\mathbf{x}_i=0 i=1∑k​μi​xi​=0

因为 μ 1 , ⋯   , μ k \mu_1,\cdots,\mu_k μ1​,⋯,μk​不全为0，但是 ∑ i = 1 k μ i = 0 \sum_{i=1}^{k}\mu_i=0 ∑i=1k​μi​=0

所以必然存在 i i i，使得 μ i < 0 \mu_i<0 μi​<0

设 α ∈ R + \alpha \in \mathbb{R}_{+} α∈R+​

x = ∑ i = 1 k λ i x i = ∑ i = 1 k λ i x i + α ∑ i = 1 k μ i x i = ∑ i = 1 k ( λ i + α μ i ) x i \mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i+\alpha \sum_{i=1}^{k}\mu_i\mathbf{x}_i=\sum_{i=1}^{k}(\lambda_i+\alpha\mu_i)\mathbf{x}_i x=i=1∑k​λi​xi​=i=1∑k​λi​xi​+αi=1∑k​μi​xi​=i=1∑k​(λi​+αμi​)xi​

∑ i = 1 k ( λ i + α μ i ) = 1 \sum_{i=1}^{k}(\lambda_i+\alpha\mu_i)=1 ∑i=1k​(λi​+αμi​)=1

所以上式这是一个凸组合当且仅当

∀ i = 1 , ⋯   , k , λ i + α μ i ≥ 0 \forall i=1,\cdots,k,\lambda_i+\alpha\mu_i\ge 0 ∀i=1,⋯,k,λi​+αμi​≥0

因为 λ i > 0 \lambda_i>0 λi​>0,所以当 α ∈ [ 0 , ϵ ] \alpha\in \left[0,\epsilon\right] α∈[0,ϵ],满足不等式

其中 ϵ = min ⁡ i : μ i < 0 { − μ i λ i } \epsilon=\min\limits_{i:\mu_i<0}\left\{-\frac{\mu_i}{\lambda_i}\right\} ϵ=i:μi​<0min​{−λi​μi​​}

那么如果用 α = ϵ \alpha=\epsilon α=ϵ替换凸组合，则虽然不等式满足，但是

λ j + ϵ μ j = 0 \lambda_j+\epsilon \mu_j=0 λj​+ϵμj​=0,其中 j = arg ⁡ min ⁡ i : μ i < 0 { − μ i λ i } j=\arg\min\limits_{i:\mu_i<0}\left\{-\frac{\mu_i}{\lambda_i}\right\} j=argi:μi​<0min​{−λi​μi​​}

这意味着只要 k − 1 k-1 k−1个向量就可以了，也就是说可以删去 x j \mathbf{x}_j xj​

这个过程可以一直持续到 k ≥ n + 1 k\ge n+1 k≥n+1

所以结论成立

这个定理告诉我们，一个集合只要 n + 1 n+1 n+1个向量，他们的凸组合就可以表示集合的凸包中的所有向量

凸锥

锥

如果 x ∈ S \mathbf{x}\in S x∈S则 λ ≥ 0 , λ x ∈ S \lambda \ge 0,\lambda \mathbf{x}\in S λ≥0,λx∈S，则 S S S称为锥

凸锥

凸锥就是一个锥+凸集

即

如果 x , y ∈ S \mathbf{x},\mathbf{y}\in S x,y∈S,则

∀ λ 1 , λ 2 ≥ 0 , λ 1 x + λ 2 y ∈ S \forall \lambda_1,\lambda_2\ge0, \lambda_1\mathbf{x}+\lambda_2\mathbf{y}\in S ∀λ1​,λ2​≥0,λ1​x+λ2​y∈S

等价定义

如果 S S S是凸集，等价于

a)

x , y ∈ S ⇒ x + y ∈ S \mathbf{x},\mathbf{y}\in S\Rightarrow \mathbf{x}+\mathbf{y}\in S x,y∈S⇒x+y∈S

b)

x ∈ S , λ ≥ 0 ⇒ λ x ∈ S \mathbf{x}\in S,\lambda\ge 0\Rightarrow \lambda \mathbf{x}\in S x∈S,λ≥0⇒λx∈S

同时成立

证明：

充分性：如果 S S S是凸锥

a)

利用凸集的定义

1 2 x + 1 2 y ∈ S \frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}\in S 21​x+21​y∈S

利用锥的定义

2 ( 1 2 x + 1 2 y ) = x + y ∈ S 2(\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y})=\mathbf{x}+\mathbf{y}\in S 2(21​x+21​y)=x+y∈S

b)

利用锥的定义，显然成立

必要性：

利用b)

λ x , ( 1 − λ ) y ∈ S \lambda \mathbf{x},(1-\lambda)\mathbf{y}\in S λx,(1−λ)y∈S

利用a)

λ x + ( 1 − λ ) y ∈ S \lambda \mathbf{x}+(1-\lambda)\mathbf{y}\in S λx+(1−λ)y∈S

得到凸性

利用b)

得到锥

所以 S S S时凸锥

凸锥组合

给定 k k k个点 x 1 , x 2 , ⋯   , x k ∈ R n \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_k\in\mathbb{R}^n x1​,x2​,⋯,xk​∈Rn

凸锥组合为 λ 1 x 1 + ⋯ + λ k x k \lambda_1\mathbf{x}_1+\cdots+\lambda_k\mathbf{x}_k λ1​x1​+⋯+λk​xk​

其中 λ ∈ R + k \lambda \in \mathbb{R}_{+}^{k} λ∈R+k​

引理

设 C C C是凸锥，设 x 1 , ⋯   , x k ∈ C \mathbf{x}_1,\cdots,\mathbf{x}_k\in C x1​,⋯,xk​∈C, λ 1 , ⋯   , λ k ≥ 0 \lambda_1,\cdots,\lambda_k\ge 0 λ1​,⋯,λk​≥0

则 ∑ i = 1 k λ i x i ∈ C \sum_{i=1}^{k}\lambda_i \mathbf{x}_i\in C ∑i=1k​λi​xi​∈C

利用刚刚的等价定义，显然成立

凸锥包

设 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn

凸锥包表示为 c o n e ( S ) cone(S) cone(S)

c o n e ( S ) = { ∑ i = 1 k λ i x i : x 1 , ⋯   , x k ∈ S , λ ∈ R + k , k ∈ N } cone(S)=\left\{\sum_{i=1}^{k}\lambda_i\mathbf{x}_i:\mathbf{x}_1,\cdots,\mathbf{x}_k\in S,\lambda\in\mathbb{R}_{+}^{k},k\in\mathbb{N}\right\} cone(S)={i=1∑k​λi​xi​:x1​,⋯,xk​∈S,λ∈R+k​,k∈N}

conic representation theorem

设 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn, x ∈ c o n e ( S ) \mathbf{x}\in cone(S) x∈cone(S)

则存在 k k k个线性无关的向量 x 1 , ⋯   , x k ∈ S \mathbf{x}_1,\cdots,\mathbf{x}_k\in S x1​,⋯,xk​∈S

使得 x ∈ c o n e ( { x 1 , ⋯   , x k } ) \mathbf{x}\in cone(\{\mathbf{x}_1,\cdots,\mathbf{x}_k\}) x∈cone({x1​,⋯,xk​})

即

∃ λ ∈ R + k , x = ∑ i = 1 k λ i x i \exists\lambda\in\mathbb{R}_{+}^{k},\mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i ∃λ∈R+k​,x=i=1∑k​λi​xi​

其中 k ≥ n k\ge n k≥n

证明：

设 x ∈ c o n e ( S ) \mathbf{x}\in cone(S) x∈cone(S)

根据凸锥包的定义， ∃ x 1 , x 2 + ⋯ + x k ∈ S , λ ∈ R + k \exists \mathbf{x}_1,\mathbf{x}_2+\cdots+\mathbf{x}_k\in S,\lambda \in \mathbb{R}_+^k ∃x1​,x2​+⋯+xk​∈S,λ∈R+k​ 使得

x = ∑ i = 1 k λ i x i \mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i x=i=1∑k​λi​xi​

不妨设 λ i > 0 \lambda_i>0 λi​>0，以为如果 λ i = 0 \lambda_i=0 λi​=0,则 x i x_i xi​可以被删去。

如果 x 1 , ⋯   , x k \mathbf{x}_1,\cdots,\mathbf{x}_k x1​,⋯,xk​线性无关，则结论成立

如果线性相关，则存在不全为0的 μ 1 , ⋯   , μ k \mu_1,\cdots,\mu_k μ1​,⋯,μk​，使得

∑ i = 1 k μ i x i = 0 \sum_{i=1}^{k}\mu_i\mathbf{x}_i=0 i=1∑k​μi​xi​=0

于是对于 α ∈ R \alpha \in \mathbb{R} α∈R

x = ∑ i = 1 k λ i x i + α ∑ i = 1 k μ i x i = ∑ i = 1 k ( λ i + α μ i ) x i \mathbf{x}=\sum_{i=1}^{k}\lambda_i\mathbf{x}_i+\alpha\sum_{i=1}^{k}\mu_i\mathbf{x}_i=\sum_{i=1}^{k}(\lambda_i+\alpha \mu_i)\mathbf{x}_i x=i=1∑k​λi​xi​+αi=1∑k​μi​xi​=i=1∑k​(λi​+αμi​)xi​

这是一个凸锥组合，当且仅当

λ i + α μ i ≥ 0 \lambda_i+\alpha \mu_i\ge 0 λi​+αμi​≥0

因为 λ i > 0 \lambda_i>0 λi​>0,所以上面的不等式成立的条件是 α ∈ I \alpha \in I α∈I

其中 I I I是一个非空的闭区间，而且至少有一边不是无穷（我觉得有点问题，可以保证至少一边是闭，但是是不是闭区间，我觉得有点问题

max ⁡ μ i > 0 { − λ i μ i } ≤ α ≤ min ⁡ μ i < 0 { − λ i μ i } \max_{\mu_i>0}\left\{-\frac{\lambda_i}{\mu_i}\right\}\le\alpha\le\min_{\mu_i<0}\left\{-\frac{\lambda_i}{\mu_i}\right\} μi​>0max​{−μi​λi​​}≤α≤μi​<0min​{−μi​λi​​}

如果 μ i \mu_i μi​没有负的，则左闭右开

如果 μ i \mu_i μi​没有正的，则左开右闭

因为 μ i \mu_i μi​不全为0，所以不会没有正且没有负

所以可以保证至少一边是闭

）

不妨设边界点为 α ~ \tilde{\alpha} α~,显然满足不等式

但是存在 j j j,使得 λ j + α ~ μ j = 0 \lambda_j+\tilde{\alpha} \mu_j=0 λj​+α~μj​=0

因此 x j \mathbf{x}_j xj​ 可以被删去，只需要 k − 1 k-1 k−1个向量就能表示 x \mathbf{x} x

这个过程可以持续到 x 1 , ⋯   , x k \mathbf{x}_1,\cdots,\mathbf{x}_k x1​,⋯,xk​线性无关

所以 k ≤ n k\le n k≤n

基本可行解

basic feasible solutions

设 P = { x ∈ R n : A x = b , x ≥ 0 } P=\left\{\mathbf{x} \in \mathbb{R}^{n}: \mathbf{A} \mathbf{x}=\mathbf{b}, \mathbf{x} \geq 0\right\} P={x∈Rn:Ax=b,x≥0}

其中 A ∈ R m × n , b ∈ R m \mathbf{A}\in\mathbb{R}^{m\times n },\mathbf{b}\in \mathbb{R}^m A∈Rm×n,b∈Rm

假设 A \mathbf{A} A的行线性无关

则 x ˉ \bar{\mathbf{x}} xˉ被称为 P P P的一个基本可行解（简称bfs)如果 A \mathbf{A} A对应于 x ˉ \bar{\mathbf{x}} xˉ正的分量的下标的列向量是线性无关的

比如说 x ˉ \bar{\mathbf{x}} xˉ的1,3,5分量是正的，则 A \mathbf{A} A的1,3,5列的向量线性无关

定理

设 P = { x ∈ R n : A x = b , x ≥ 0 } P=\left\{\mathbf{x} \in \mathbb{R}^{n}: \mathbf{A} \mathbf{x}=\mathbf{b}, \mathbf{x} \geq 0\right\} P={x∈Rn:Ax=b,x≥0}

其中 A ∈ R m × n , b ∈ R m \mathbf{A}\in\mathbb{R}^{m\times n },\mathbf{b}\in \mathbb{R}^m A∈Rm×n,b∈Rm

如果 P ≠ ∅ P \neq \emptyset P​=∅,则至少存在一个可行解

证明：

设 A = ( a 1 , a 2 , … , a n ) \mathbf{A}=\left(\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{n}\right) A=(a1​,a2​,…,an​)

则 b ∈ c o n e ( { a 1 , a 2 , … , a n } ) \mathbf{b}\in cone\left(\left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{n} \right\}\right) b∈cone({a1​,a2​,…,an​})

根据conic representation theorem, b \mathbf{b} b可以用来自 { a 1 , a 2 , … , a n } \left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{n} \right\} {a1​,a2​,…,an​}的 k k k个线性无关的向量表示

所以 ∃ i 1 < ⋯ < i k \exists i_1<\cdots < i_k ∃i1​<⋯<ik​， y i 1 , ⋯   , y i k ≥ 0 y_{i_1},\cdots,y_{i_k}\ge 0 yi1​​,⋯,yik​​≥0

使得 b = ∑ j = 1 k y i j a i j \mathbf{b}=\sum_{j=1}^{k}y_{i_j}\mathbf{a}_{i_j} b=∑j=1k​yij​​aij​​,并且 a i 1 , ⋯   , a i k \mathbf{a}_{i_1},\cdots,\mathbf{a}_{i_k} ai1​​,⋯,aik​​线性无关

令 x ‾ = ∑ j = 1 k y i j e i j \overline{\mathbf{x}}=\sum_{j=1}^{k} y_{i_{j}} \mathbf{e}_{i_{j}} x=∑j=1k​yij​​eij​​

显然 x ˉ ≥ 0 \bar{\mathbf{x}}\ge 0 xˉ≥0

并且

A x ‾ = ∑ j = 1 k y i j A e i j = ∑ j = 1 k y i j a i j = b \mathbf{A} \overline{\mathbf{x}}=\sum_{j=1}^{k} y_{i_{j}} \mathbf{A e}_{i_{j}}=\sum_{j=1}^{k} y_{i_{j}} \mathbf{a}_{i_{j}}=\mathbf{b} Ax=j=1∑k​yij​​Aeij​​=j=1∑k​yij​​aij​​=b

满足条件，是一个bfs

拓扑基本概念

内点

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn，如果存在 r > 0 r>0 r>0使得 B ( c , r ) ∈ U B(\mathbf{c},r)\in U B(c,r)∈U,则 c \mathbf{c} c是一个 U U U的一个内点

开集

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn是一个开集，当且仅当

∀ x ∈ U , ∃ r > 0 , s . t . B ( x , r ) ∈ U \forall \mathbf{x}\in U,\exists r>0, s.t. B(\mathbf{x},r)\in U ∀x∈U,∃r>0,s.t.B(x,r)∈U

int ⁡ ( U ) = { x ∈ U : B ( x , r ) ⊆ U  对于某些  r > 0 } \operatorname{int}(U)=\{\mathrm{x} \in U: B(\mathrm{x}, r) \subseteq U \text { 对于某些 } r>0\} int(U)={x∈U:B(x,r)⊆U 对于某些 r>0}

闭集

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn是一个闭集，当且仅当

对于所有的序列 { x i } i ≥ 1 ⊆ U \left\{\mathbf{x}_{i}\right\}_{i \geq 1} \subseteq U {xi​}i≥1​⊆U

当 i → ∞ i\to \infty i→∞时, x i → x ∗ \mathbf{x}_i\to \mathbf{x}^{*} xi​→x∗,且 x ∗ ∈ U \mathbf{x}^{*}\in U x∗∈U

边界点

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn

x ∈ R n \mathbf{x}\in\mathbb{R}^n x∈Rn是一个边界点，如果满足：邻域内存在一个点在 U U U，且存在一个点在 U c U^{c} Uc

U U U的边界点的集合记为 b d ( U ) bd(U) bd(U)

闭包

cl ⁡ ( U ) = ⋂ { T : U ⊆ T , T  是闭集  } \operatorname{cl}(U)=\bigcap\{T: U \subseteq T, T \text { 是闭集 }\} cl(U)=⋂{T:U⊆T,T 是闭集 }

等价定义

c l ( U ) = U ∪ b d ( U ) \mathrm{cl}(U)=U \cup \mathrm{bd}(U) cl(U)=U∪bd(U)

有界

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn

如果存在 M > 0 M>0 M>0,使得 U ⊆ B ( 0 , M ) U\subseteq B(0,M) U⊆B(0,M),则 U U U是有界的

紧集

U ⊆ R n U\subseteq \mathbb{R}^n U⊆Rn

如果 U U U是一个闭集，且有界,则 U U U是紧集

凸集的拓扑性质

定理1

设 C ⊆ R n C\subseteq \mathbb{R}^n C⊆Rn是一个凸集，则 c l ( C ) cl(C) cl(C)是一个凸集

证明：

设 x , y ∈ cl ⁡ ( C ) \mathbf{x}, \mathbf{y} \in \operatorname{cl}(C) x,y∈cl(C), λ ∈ [ 0 , 1 ] \lambda \in \left[0,1\right] λ∈[0,1]

根据闭集的定义

∃ { x k } k ≥ 0 ⊆ C , { y k } k ≥ 0 ⊆ C \exists \left\{\mathbf{x}_{k}\right\}_{k \geq 0} \subseteq C,\left\{\mathbf{y}_{k}\right\}_{k \geq 0} \subseteq C ∃{xk​}k≥0​⊆C,{yk​}k≥0​⊆C

当 k → ∞ k\to \infty k→∞时, x k → x , y k → y \mathbf{x}_{k} \rightarrow \mathbf{x},\mathbf{y}_{k} \rightarrow \mathbf{y} xk​→x,yk​→y

根据凸集的定义

∀ k ≥ 0 , λ x k + ( 1 − λ ) y k ∈ C \forall k\ge 0, \lambda \mathbf{x}_{k}+(1-\lambda) \mathbf{y}_{k} \in C ∀k≥0,λxk​+(1−λ)yk​∈C

因为 λ x k + ( 1 − λ ) y k → λ x + ( 1 − λ ) y \lambda \mathbf{x}_{k}+(1-\lambda) \mathbf{y}_{k} \rightarrow \lambda \mathbf{x}+(1-\lambda) \mathbf{y} λxk​+(1−λ)yk​→λx+(1−λ)y

所以 C C C中存在序列，收敛于 λ x + ( 1 − λ ) y \lambda \mathbf{x}+(1-\lambda) \mathbf{y} λx+(1−λ)y

从而 λ x + ( 1 − λ ) y ∈ cl ⁡ ( C ) . \lambda \mathbf{x}+(1-\lambda) \mathbf{y} \in \operatorname{cl}(C) . λx+(1−λ)y∈cl(C).

line segment principle

设 C C C是一个凸集，假设 i n t ( C ) ≠ ∅ int(C)\neq \emptyset int(C)​=∅

假设 x ∈ i n t ( C ) , y ∈ c l ( C ) \mathbf{x}\in int(C),\mathbf{y}\in cl(C) x∈int(C),y∈cl(C)

则 ∀ λ ∈ ( 0 , 1 ) , ( 1 − λ ) x + λ y ∈ int ⁡ ( C ) \forall \lambda \in (0,1),(1-\lambda) \mathbf{x}+\lambda \mathbf{y} \in \operatorname{int}(C) ∀λ∈(0,1),(1−λ)x+λy∈int(C)

证明：

因为 x ∈ i n t ( C ) \mathbf{x}\in int(C) x∈int(C),则 ∃ ϵ > 0 , B ( x , ϵ ) ⊆ C \exists \epsilon >0,B(\mathbf{x},\epsilon)\subseteq C ∃ϵ>0,B(x,ϵ)⊆C

设 z = ( 1 − λ ) x + λ y \mathbf{z}=(1-\lambda) \mathbf{x}+\lambda \mathbf{y} z=(1−λ)x+λy

为了证明 z ∈ i n t ( C ) \mathbf{z}\in int(C) z∈int(C),可以试着证明 B ( z , ( 1 − λ ) ϵ ) ⊆ C B(\mathbf{z},(1-\lambda)\epsilon)\subseteq C B(z,(1−λ)ϵ)⊆C

设 w \mathbf{w} w满足 ∥ w − z ∥ < ( 1 − λ ) ϵ \| \mathbf{w}-\mathbf{z}\|< (1-\lambda)\epsilon ∥w−z∥<(1−λ)ϵ

因为 y ∈ c l ( C ) \mathbf{y}\in cl(C) y∈cl(C)

所以 ∃ w 1 ∈ C \exists \mathbf{w}_1\in C ∃w1​∈C,使得

∥ w 1 − y ∥ < ( 1 − λ ) ε − ∥ w − z ∥ λ \left\|\mathbf{w}_{1}-\mathbf{y}\right\|<\frac{(1-\lambda) \varepsilon-\|\mathbf{w}-\mathbf{z}\|}{\lambda} ∥w1​−y∥<λ(1−λ)ε−∥w−z∥​

令 w 2 = 1 1 − λ ( w − λ w 1 ) \mathbf{w}_{2}=\frac{1}{1-\lambda}\left(\mathbf{w}-\lambda \mathbf{w}_{1}\right) w2​=1−λ1​(w−λw1​)

∥ w 2 − x ∥ = ∥ w − λ w 1 1 − λ − x ∥ = 1 1 − λ ∥ ( w − z ) + λ ( y − w 1 ) ∥ ≤ 1 1 − λ ( ∥ w − z ∥ + λ ∥ w 1 − y ∥ ) < ε \begin{aligned} \left\|\mathbf{w}_{2}-\mathbf{x}\right\| &=\left\|\frac{\mathbf{w}-\lambda \mathbf{w}_{1}}{1-\lambda}-\mathbf{x}\right\| \\ &=\frac{1}{1-\lambda}\left\|(\mathbf{w}-\mathbf{z})+\lambda\left(\mathbf{y}-\mathbf{w}_{1}\right)\right\| \\ & \leq \frac{1}{1-\lambda}\left(\|\mathbf{w}-\mathbf{z}\|+\lambda\left\|\mathbf{w}_{1}-\mathbf{y}\right\|\right) \\ & < \varepsilon \end{aligned} ∥w2​−x∥​=∥∥∥∥​1−λw−λw1​​−x∥∥∥∥​=1−λ1​∥(w−z)+λ(y−w1​)∥≤1−λ1​(∥w−z∥+λ∥w1​−y∥)<ε​

因为 B ( x , ε ) ⊆ C B(\mathbf{x}, \varepsilon) \subseteq C B(x,ε)⊆C，所以 w 2 ∈ C \mathbf{w_2}\in C w2​∈C

所以 w = λ w 1 + ( 1 − λ ) w 2 ∈ C \mathbf{w}=\lambda \mathbf{w}_{1}+(1-\lambda) \mathbf{w}_{2} \in C w=λw1​+(1−λ)w2​∈C

定理2

设 C ⊆ R n C\subseteq \mathbb{R}^n C⊆Rn是凸集,则 i n t ( C ) int(C) int(C)也是凸集

证明：

如果 i n t ( C ) = ∅ int(C)=\emptyset int(C)=∅，则结论成立

如果 i n t ( C ) ≠ ∅ int(C)\neq \emptyset int(C)​=∅,则设 x 1 , x 2 ∈ int ⁡ ( C ) , λ ∈ ( 0 , 1 ) \mathbf{x}_{1}, \mathbf{x}_{2} \in \operatorname{int}(C),\lambda \in (0,1) x1​,x2​∈int(C),λ∈(0,1)

根据line segment principle，

λ x 1 + ( 1 − λ ) x 2 ∈ int ⁡ ( C ) \lambda \mathbf{x}_{1}+(1-\lambda) \mathbf{x}_{2} \in \operatorname{int}(C) λx1​+(1−λ)x2​∈int(C)

引理1

设 C C C是凸集， i n t ( C ) ≠ ∅ int(C)\neq \emptyset int(C)​=∅,则

(a) c l ( i n t ( C ) ) = c l ( C ) cl(int(C))=cl(C) cl(int(C))=cl(C)

(b) i n t ( c l ( C ) ) = i n t ( C ) int(cl(C))=int(C) int(cl(C))=int(C)

证明：

(a)

显然 i n t ( C ) ⊆ C ⇒ c l ( i n t ( C ) ) ⊆ c l ( C ) int(C)\subseteq C\Rightarrow cl(int(C))\subseteq cl(C) int(C)⊆C⇒cl(int(C))⊆cl(C)

现在证明反向的版本

x ∈ c l ( C ) , y ∈ i n t ( C ) \mathbf{x}\in cl(C),\mathbf{y}\in int(C) x∈cl(C),y∈int(C)

根据line segment principle，

∀ k ≥ 1 , x k = 1 k y + ( 1 − 1 k ) x ∈ i n t ( C ) \forall k\ge 1,\mathbf{x}_k=\frac{1}{k}\mathbf{y}+(1-\frac{1}{k})\mathbf{x}\in int(C) ∀k≥1,xk​=k1​y+(1−k1​)x∈int(C)

而 x \mathbf{x} x是 { x k } k ≥ 1 ⊆ C \left\{\mathbf{x}_{k}\right\}_{k \geq 1}\subseteq C {xk​}k≥1​⊆C收敛的点

即 x ∈ c l ( i n t ( C ) ) \mathbf{x}\in cl(int(C)) x∈cl(int(C))

(b)

C ⊆ c l ( C ) ⇒ i n t ( C ) ⊆ i n t ( c l ( C ) ) C\subseteq cl(C)\Rightarrow int(C)\subseteq int(cl(C)) C⊆cl(C)⇒int(C)⊆int(cl(C))

现在证明反向的版本

因为 x ∈ i n t ( c l ( C ) ) \mathbf{x} \in int(cl(C)) x∈int(cl(C))， ∃ ϵ > 0 , B ( x , ϵ ) ⊆ c l ( C ) \exists \epsilon >0,B(\mathbf{x},\epsilon)\subseteq cl(C) ∃ϵ>0,B(x,ϵ)⊆cl(C)

设 y ∈ i n t ( C ) \mathbf{y}\in int(C) y∈int(C)

如果 x = y \mathbf{x}=\mathbf{y} x=y则结论成立

否则

设

z = x + α ( x − y ) \mathbf{z}=\mathbf{x}+\alpha(\mathbf{x}-\mathbf{y}) z=x+α(x−y)

其中 α = ε 2 ∥ x − y ∥ \alpha=\frac{\varepsilon}{2\|\mathrm{x}-\mathrm{y}\|} α=2∥x−y∥ε​

所以 ∥ z − x ∥ = ε 2 \|\mathbf{z}-\mathbf{x}\|=\frac{\varepsilon}{2} ∥z−x∥=2ε​, z ∈ c l ( C ) \mathbf{z}\in cl(C) z∈cl(C)

∀ λ ∈ [ 0 , 1 ) , ( 1 − λ ) y + λ z ∈ i n t ( C ) \forall \lambda \in \left[0,1\right), (1-\lambda) \mathbf{y}+\lambda \mathbf{z} \in int(C) ∀λ∈[0,1),(1−λ)y+λz∈int(C)

特别地， λ = λ α = 1 1 + α \lambda =\lambda_{\alpha}=\frac{1}{1+\alpha} λ=λα​=1+α1​时，有 ( 1 − λ α ) y + λ α z = x \left(1-\lambda_{\alpha}\right) \mathbf{y}+\lambda_{\alpha} \mathbf{z}=\mathbf{x} (1−λα​)y+λα​z=x

即 x ∈ i n t ( C ) \mathbf{x}\in int(C) x∈int(C)

定理3

如果 S ⊆ R n S\subseteq \mathbb{R}^n S⊆Rn是一个紧集，则 c o n v ( S ) conv(S) conv(S)是紧集

证明：

先证明有界性

因为 S S S是紧集， ∀ x ∈ S , ∃ M > 0 , ∥ x ∥ ≤ M \forall \mathbf{x}\in S,\exists M>0,\|\mathbf{x}\| \le M ∀x∈S,∃M>0,∥x∥≤M

设 y ∈ c o n v ( S ) \mathbf{y}\in conv(S) y∈conv(S)

根据Carathéodory 定理

∃ x 1 k , x 2 k , … , x n + 1 k ∈ S , λ k ∈ Δ n + 1 \exists \mathbf{x}_{1}^{k}, \mathbf{x}_{2}^{k}, \ldots, \mathbf{x}_{n+1}^{k} \in S,\lambda^{k}\in \Delta_{n+1} ∃x1k​,x2k​,…,xn+1k​∈S,λk∈Δn+1​使得 y k = ∑ i = 1 n + 1 λ i k x i k \mathbf{y}_{k}=\sum_{i=1}^{n+1} \lambda_{i}^{k} \mathbf{x}_{i}^{k} yk​=∑i=1n+1​λik​xik​,因此

∥ y ∥ = ∥ ∑ i = 1 n + 1 λ i x i ∥ ≤ ∑ i = 1 n + 1 λ i ∥ x i ∥ ≤ M ∑ i = 1 n + 1 λ i = M \|\mathbf{y}\|=\left\|\sum_{i=1}^{n+1} \lambda_{i} \mathbf{x}_{i}\right\| \leq \sum_{i=1}^{n+1} \lambda_{i}\left\|\mathbf{x}_{i}\right\| \leq M \sum_{i=1}^{n+1} \lambda_{i}=M ∥y∥=∥∥∥∥∥​i=1∑n+1​λi​xi​∥∥∥∥∥​≤i=1∑n+1​λi​∥xi​∥≤Mi=1∑n+1​λi​=M

接着证明闭集

设 { y k } k ≥ 1 ⊆ c o n v ( S ) \left\{\mathbf{y}_{k}\right\}_{k \geq 1} \subseteq conv(S) {yk​}k≥1​⊆conv(S)收敛于 y ∈ R n \mathbf{y}\in \mathbb{R}^n y∈Rn

根据Carathéodory 定理

∃ x 1 k , x 2 k , … , x n + 1 k ∈ S , λ k ∈ Δ n + 1 \exists \mathbf{x}_{1}^{k}, \mathbf{x}_{2}^{k}, \ldots, \mathbf{x}_{n+1}^{k} \in S, \lambda^{k} \in \Delta_{n+1} ∃x1k​,x2k​,…,xn+1k​∈S,λk∈Δn+1​ 使得

y k = ∑ i = 1 n + 1 λ i k x i k \mathbf{y}_{k}=\sum_{i=1}^{n+1} \lambda_{i}^{k} \mathbf{x}_{i}^{k} yk​=i=1∑n+1​λik​xik​

根据 S S S是紧集， { ( λ k , x 1 k , x 2 k , … , x n + 1 k ) } k ≥ 1 \left\{\left(\lambda^{k}, \mathbf{x}_{1}^{k}, \mathbf{x}_{2}^{k}, \ldots, \mathbf{x}_{n+1}^{k}\right)\right\}_{k \geq 1} {(λk,x1k​,x2k​,…,xn+1k​)}k≥1​的子列 { ( λ k j , x 1 k j , x 2 k j , … , x n + 1 k j ) } j ≥ 1 \left\{\left(\lambda^{k_{j}}, \mathbf{x}_{1}^{k_{j}}, \mathbf{x}_{2}^{k_{j}}, \ldots, \mathbf{x}_{n+1}^{k_{j}}\right)\right\}_{j \geq 1} {(λkj​,x1kj​​,x2kj​​,…,xn+1kj​​)}j≥1​的极限为

( λ , x 1 , x 2 , … , x n + 1 ) \left(\lambda, \mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n+1}\right) (λ,x1​,x2​,…,xn+1​)

其中 λ ∈ Δ n + 1 , x 1 , x 2 , … , x n + 1 ∈ S \lambda \in \Delta_{n+1},\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n+1} \in S λ∈Δn+1​,x1​,x2​,…,xn+1​∈S

当 j → ∞ j\to \infty j→∞

y = ∑ i = 1 n + 1 λ i x i \mathbf{y}=\sum_{i=1}^{n+1} \lambda_{i} \mathbf{x}_{i} y=i=1∑n+1​λi​xi​

即 y ∈ c o n v ( S ) \mathbf{y}\in conv(S) y∈conv(S)

引理2

设 a 1 , a 2 , … , a k ∈ R n \mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{k} \in \mathbb{R}^{n} a1​,a2​,…,ak​∈Rn，则 cone ⁡ ( { a 1 , a 2 , … , a k } ) \operatorname{cone}\left(\left\{\mathrm{a}_{1}, \mathrm{a}_{2}, \ldots, \mathrm{a}_{k}\right\}\right) cone({a1​,a2​,…,ak​})是闭集

证明：

根据conic representation theorem，

cone ⁡ ( { a 1 , a 2 , ⋯   , a k } ) \operatorname{cone}\left(\left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \cdots, \mathbf{a}_{k}\right\}\right) cone({a1​,a2​,⋯,ak​})的每一个元素，都可以被 { a 1 , a 2 , ⋯   , a k } \left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \cdots, \mathbf{a}_{k}\right\} {a1​,a2​,⋯,ak​}的线性无关子集的凸锥组合表示

因此，设 S 1 , ⋯   , S N S_1,\cdots,S_N S1​,⋯,SN​是 { a 1 , a 2 , ⋯   , a k } \left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \cdots, \mathbf{a}_{k}\right\} {a1​,a2​,⋯,ak​}的子集，且 S i S_i Si​中的元素线性无关

那么

cone ⁡ ( { a 1 , a 2 , … , a k } ) = ⋃ i = 1 N cone ⁡ ( S i ) \operatorname{cone}\left(\left\{\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{k}\right\}\right)=\bigcup_{i=1}^{N} \operatorname{cone}\left(S_{i}\right) cone({a1​,a2​,…,ak​})=i=1⋃N​cone(Si​)

让 i ∈ { 1 , 2 , ⋯   , N } i\in \left\{1,2,\cdots,N\right\} i∈{1,2,⋯,N},那么

S i = { b 1 , b 2 , … , b m } S_{i}=\left\{\mathbf{b}_{1}, \mathbf{b}_{2}, \ldots, \mathbf{b}_{m}\right\} Si​={b1​,b2​,…,bm​}

其中 b 1 , b 2 , … , b m \mathbf{b}_{1}, \mathbf{b}_{2}, \ldots, \mathbf{b}_{m} b1​,b2​,…,bm​线性无关

也可以写成

cone ⁡ ( S i ) = { B y : y ∈ R + m } \operatorname{cone}\left(S_{i}\right)=\left\{\mathbf{B y}: \mathbf{y} \in \mathbb{R}_{+}^{m}\right\} cone(Si​)={By:y∈R+m​}

其中 B = ( b 1 , b 2 , … , b m ) \mathbf{B}=(\mathbf{b}_{1}, \mathbf{b}_{2}, \ldots, \mathbf{b}_{m}) B=(b1​,b2​,…,bm​)

设 ∀ k ≥ 1 , x k ∈ c o n e ( S i ) \forall k\ge 1,\mathbf{x}_k\in cone(S_i) ∀k≥1,xk​∈cone(Si​),

x k → x ˉ \mathbf{x}_k\to \bar{\mathbf{x}} xk​→xˉ

因为 x k ∈ c o n e ( S i ) \mathbf{x}_k\in cone(S_i) xk​∈cone(Si​),

∃ y k ∈ R + m , s . t .   x k = B y k \exists \mathbf{y}_k\in\mathbb{R}_{+}^{m},s.t.\ \mathbf{x}_{k}=\mathbf{B y}_{k} ∃yk​∈R+m​,s.t. xk​=Byk​

因为 B \mathbf{B} B的列向量线性无关，所以

y k = ( B T B ) − 1 B T x k \mathbf{y}_{k}=\left(\mathbf{B}^{T} \mathbf{B}\right)^{-1} \mathbf{B}^{T} \mathbf{x}_{k} yk​=(BTB)−1BTxk​

令 k → ∞ k\to \infty k→∞,于是 y k → y ˉ \mathbf{y}_k\to \bar{\mathbf{y}} yk​→yˉ​

其中 y ˉ = ( B T B ) − 1 B T x ˉ \bar{\mathbf{y}}=\left(\mathbf{B}^{T} \mathbf{B}\right)^{-1} \mathbf{B}^{T} \bar{\mathbf{x}} yˉ​=(BTB)−1BTxˉ

于是 x ‾ = B y ‾ \overline{\mathbf{x}}=\mathrm{B} \overline{\mathbf{y}} x=By​

因此 x ‾ ∈ cone ⁡ ( S i ) \overline{\mathbf{x}} \in \operatorname{cone}\left(S_{i}\right) x∈cone(Si​)

极点

定义

extreme points

设 S ∈ ⊆ R n S\in \subseteq \mathbb{R}^n S∈⊆Rn是一个凸集

x ∈ S \mathbf{x}\in S x∈S

如果不存在 x 1 , x 2 ∈ S ( x 1 ≠ x 2 ) , λ ∈ ( 0 , 1 ) \mathbf{x}_1,\mathbf{x}_2\in S(\mathbf{x}_1\neq \mathbf{x}_2),\lambda \in (0,1) x1​,x2​∈S(x1​​=x2​),λ∈(0,1),使得 x = λ x 1 + ( 1 − λ ) x 2 \mathbf{x}=\lambda \mathbf{x}_1+(1-\lambda)\mathbf{x}_2 x=λx1​+(1−λ)x2​

则 x \mathbf{x} x称为 S S S的一个极点

S S S的极点的集合记为 e x t ( S ) ext(S) ext(S)

定理

设 P = { x ∈ R n : A x = b , x ≥ 0 } P=\left\{\mathbf{x} \in \mathbb{R}^{n}: \mathbf{A x}=\mathbf{b}, \mathbf{x} \geq 0\right\} P={x∈Rn:Ax=b,x≥0}

其中 A ∈ R m × n , b ∈ R m \mathbf{A}\in\mathbb{R}^{m\times n },\mathbf{b}\in \mathbb{R}^m A∈Rm×n,b∈Rm,并且 A \mathbf{A} A行线性无关

那么 x ˉ \bar{\mathbf{x}} xˉ是一个 P P P的一个bfs，当且仅当他是一个 P P P的一个极点

证明：

充分性：当 x ˉ \bar{\mathbf{x}} xˉ是bfs

不妨设 x ˉ 1 > 0 , x ˉ 2 > 0 , ⋯   , x ˉ k > 0 , x ˉ k + 1 = x ˉ k + 2 = ⋯ = x ˉ n = 0 \bar{\mathbf{x}}_{1}>0, \bar{\mathbf{x}}_{2}>0, \cdots, \bar{\mathbf{x}}_{k}>0,\bar{\mathbf{x}}_{k+1}=\bar{\mathbf{x}}_{k+2}=\cdots=\bar{\mathbf{x}}_{n}=0 xˉ1​>0,xˉ2​>0,⋯,xˉk​>0,xˉk+1​=xˉk+2​=⋯=xˉn​=0

根据bfs的定义， a 1 , a 2 , ⋯   , a k \mathbf{a}_{1}, \mathbf{a}_{2}, \cdots, \mathbf{a}_{k} a1​,a2​,⋯,ak​线性无关

假设 x ‾ ∉ ext ⁡ ( P ) \overline{\mathbf{x}} \notin \operatorname{ext}(P) x∈/​ext(P)

则设 ∃ y , z ≥ 0 , λ ∈ ( 0 , 1 ) , s . t .   x ˉ = λ y + ( 1 − λ ) z \exists\mathbf{y}, \mathbf{z} \geq 0,\lambda \in(0,1),s.t.\ \bar{\mathbf{x}}=\lambda \mathbf{y}+(1-\lambda)\mathbf{z} ∃y,z≥0,λ∈(0,1),s.t. xˉ=λy+(1−λ)z

因为 y , z ≥ 0 \mathbf{y}, \mathbf{z} \geq 0 y,z≥0,可以得到他们至少有 n − k n-k n−k个分量是0

∑ i = 1 k y i a i = b ∑ i = 1 k z i a i = b ∑ i = 1 k ( y i − z i ) a i = 0 \begin{aligned} &\sum_{i=1}^{k} \mathbf{y}_{i} \mathbf{a}_{i}=\mathbf{b} \\ &\sum_{i=1}^{k} \mathbf{z}_{i} \mathbf{a}_{i}=\mathbf{b}\\ &\sum_{i=1}^{k} (\mathbf{y}_{i}-\mathbf{z}_{i}) \mathbf{a}_{i}=0 \end{aligned} ​i=1∑k​yi​ai​=bi=1∑k​zi​ai​=bi=1∑k​(yi​−zi​)ai​=0​

因为 y ≠ z \mathbf{y}\neq \mathbf{z} y​=z，所以 a 1 , a 2 , ⋯   , a k \mathbf{a}_{1}, \mathbf{a}_{2}, \cdots, \mathbf{a}_{k} a1​,a2​,⋯,ak​线性相关

矛盾

必要性：

设 x ~ ∈ P \tilde{\mathbf{x}}\in P x~∈P是一个极点

假设 x ~ \tilde{\mathbf{x}} x~不是bfs

这意味着对应的列向量线性相关

不妨设 x ~ \tilde{\mathbf{x}} x~的前 k k k个分量为正

存在 0 ≠ y ∈ R k 0\neq \mathbf{y}\in \mathbb{R}^{k} 0​=y∈Rk,使得

∑ i = 1 k y i a i = 0 \sum_{i=1}^{k} y_{i} \mathbf{a}_{i}=0 i=1∑k​yi​ai​=0

也可以写成 A y ~ = 0 A \tilde{\mathbf{y}}=0 Ay~​=0,其中 y ~ = ( y 0 n − k ) \tilde{\mathbf{y}}=\begin{pmatrix}\mathbf{y}\\0_{n-k}\end{pmatrix} y~​=(y0n−k​​)

因为 x ~ \tilde{\mathrm{x}} x~的前 k k k个分量是正的，所以 ∃ ϵ > 0 \exists \epsilon>0 ∃ϵ>0,使得 x 1 = x ~ + ϵ y ~ ≥ 0 \mathbf{x}_{1}=\tilde{\mathbf{x}}+\epsilon \tilde{\mathbf{y}} \geq 0 x1​=x~+ϵy~​≥0,以及 x 2 = x ~ − ϵ y ~ ≥ 0 \mathbf{x}_{2}=\tilde{\mathbf{x}}-\epsilon \tilde{\mathbf{y}} \geq 0 x2​=x~−ϵy~​≥0

所以 A x 1 = A x ~ + ϵ A y ~ = b + ϵ ⋅ 0 = b \mathbf{A x}_{1}=\mathbf{A} \tilde{\mathbf{x}}+\epsilon \mathbf{A} \tilde{\mathbf{y}}=\mathbf{b}+\epsilon \cdot \mathbf{0}=\mathbf{b} Ax1​=Ax~+ϵAy~​=b+ϵ⋅0=b

类似地 A x 2 = b \mathbf{Ax}_{2}=\mathbf{b} Ax2​=b

因此 x 1 , x 2 ∈ P \mathbf{x}_{1}, \mathbf{x}_{2} \in P x1​,x2​∈P

因为 x 1 ≠ x 2 , y ~ ≠ 0 \mathbf{x}_1\neq \mathbf{x}_2,\tilde{\mathbf{y}}\neq 0 x1​​=x2​,y~​​=0

所以 x ~ = 1 2 x 1 + 1 2 x 2 ∈ e x t ( P ) \tilde{\mathbf{x}}=\frac{1}{2}\mathbf{x}_1+\frac{1}{2}\mathbf{x}_2\in ext(P) x~=21​x1​+21​x2​∈ext(P)

矛盾

Krein-Milman

设 S ⊆ R n S\subseteq \mathbb{R}^{n} S⊆Rn是一个紧的凸集则

S = c o n v ( e x t ( S ) ) S=conv(ext(S)) S=conv(ext(S))