凸函数定理，凸集分离定理的应用

凸集与凸集分离定理、Farkas引理

文章目录凸集与凸集分离定理、Farkas引理凸集定义：凸集凸集性质（逐个证明）超平面定义：超平面证明：超平面是凸集定义：支撑超平面定义：多面体定义：凸锥凸集分离定理定义：分离定义：凸集分离定理 Farkas引理定义：Farkas引理证明：Farkas引理

凸集定义：凸集

注意凸集的定义，任取两点满足某个条件为凸集：

证明是凸集的目标有了凸集的性质也有了，可以利用凸集性质（逐个证明）

分析：

任取 x A , y A ∈ λ C x_A,y_A \in \lambda C xA,yA∈λC，因为是要证明 λ C \lambda C λC是凸集也就是要对于所有的 x A , y A ∈ λ C , β ∈ [ 0 , 1 ] x_A,y_A \in \lambda C,\beta \in [0,1] xA,yA∈λC,β∈[0,1]，都有 β x A + 1 − β ) y A ∈ λ C \beta x_A + 1-\beta) y_A \in \lambda C βxA+1−β)yA∈λC能利用的性质只有 C C C是凸集以及 C C C与 λ C \lambda C λC两个集合的关系（从微观上，一定存在 C C C中元素乘上实数 λ \lambda λ在 λ C \lambda C λC中），应该在二者间建立联系

分析：

与上一题思路相同

有限个凸集的交集为凸集。

由以上凸集性质，我们做下面两点例题。

分析：

分别在集合间取元素，根据集合性质建立元素间关系然后带回去，这样从原理出发计算不会出错超平面定义：超平面

分析：

a ′ x = b a’ x = b a′x=b在 R 2 R^2 R2是直线，在 R 3 R^3 R3是平面，在 R k , k > 3 R^k,k>3 Rk,k>3当然就是超平面了注意 a a a实际上超平面的法向量，与超平面垂直； b ∈ R 1 b\in R^1 b∈R1决定了超平面的位置闭半空间一共有两个（一侧的点与法向量构成锐角，一侧是锐角）证明：超平面是凸集

很简单，对于闭半空间是凸集同理，将 = = =换成 ≤ \le ≤或 ≥ \ge ≥即可。

定义：支撑超平面

分析：

“支撑”即超平面对这个空间的生成起了作用，“触碰”到了这个空间定义：多面体

多面体：

是多胞形（上图的多胞形定义，我觉得不对）有界非空定义：凸锥

分析：

经过原点 0 ⃗ \vec{0} 0 ，因此超平面中 b = 0 b=0 b=0 λ 1 x \lambda_1 x λ1x 与 λ 2 y \lambda_2 y λ2y 相加，实际上表示了两个超平面的中和，即相互趋近凸集分离定理定义：分离

分析：

两个非空集合，可以被几何的概念（超平面）分开，不重叠（但是可以重叠在超平面上）如果没有 ≤ \le ≤与 ≥ \ge ≥即等号关系，则是严格分离定义：凸集分离定理

如上是凸集分离定理（如果两个集合是不相交的凸集，那么可以被一个超平面分开）。

证明过程很长，证明并应用了：Weierstrass定理、点集严格分离定理、支撑超平面定理。

Farkas引理定义：Farkas引理

用于后面的凸规划，这里注意一点：

1)有解了，2)必无解证明：Farkas引理

首先，假设1)有解，证明2)无解即可；接着证明1)无解情况下，2)必有解，大概思路是：

∀ y ∈ S \forall y \in S ∀y∈S，由1)无解可得 b ∉ S b \notin S b∈/S，由此，利用点集分离定理，得到 p ′ b < p ′ y p’ b < p’ y p′b<p′y进一步，由 0 ∈ S 0 \in S 0∈S，则有 p ′ b < 0 p’b < 0 p′b<0，现在2)的第二个式子已经证明完毕了，接下来是第一个式子 p ′ A ≥ 0 p’A \ge 0 p′A≥0的证明