凸优化学习笔记 2：超平面分离定理

个人博客地址 Glooow，欢迎光临~~~

文章目录

• • 1. 超平面分离定理
  • 2. 支撑超平面定理

1. 超平面分离定理

超平面分离定理(Separating hyperplane theorem)：若 $C,D$ 为非空凸集，且 $C\cap D=\varnothing$，则存在 $a\ne 0,b$，使得
a T x ≤ b for x ∈ C , a T x ≥ b for x ∈ D a^Tx\le b\quad\text{for}\quad x\in C,\quad a^Tx\ge b \quad\text{for}\quad x\in D aTx≤bforx∈C,aTx≥bforx∈D
也可以等价表示为 inf ⁡ x ∈ D a T x ≥ sup ⁡ x ∈ C a T x \inf_{x\in D}a^Tx \ge \sup_{x\in C}a^Tx infx∈D​aTx≥supx∈C​aTx

Lemma 1：$C$ closed，convex，$y\notin C$，那么存在唯一的 $x\in C$，使得 ∥ y − x ∥ = inf ⁡ { ∥ y − z ∥ ∣ z ∈ C } = d ( y , C ) \Vert y-x\Vert=\inf\{\Vert y-z\Vert|z\in C\}=d(y,C) ∥y−x∥=inf{∥y−z∥∣z∈C}=d(y,C)

Proof：omit…

Lemma 2：$C$ closed，convex，$y\notin C$，那么存在 $a\ne 0,b$，使得
a T y < b , a T x ≥ b ∀ x ∈ C a^TyaTy<b,aTx≥b∀x∈C
Proof：omit…

Remark：上述定理表明存在超平面可以严格分开 $y$ 与 $C$。

Lemma 3：$C$ convex，$y\notin C$，那么存在 $a\ne 0,b$，使得
a T y ≤ b , a T x ≥ b ∀ x ∈ C a^Ty\le b,\quad a^Tx\ge b\quad\forall x\in C aTy≤b,aTx≥b∀x∈C
Proof：omit…

超平面分离定理逆定理：若 $C$ 为开集，且存在超平面分离 $C,D$，则 $C\cap D=\varnothing$

2. 支撑超平面定理

支撑超平面：对于集合 $C$ 的边界点 x 0 x_0 x0​，支撑超平面为 { x ∣ a T x = a T x 0 } \{x|a^Tx=a^Tx_0\} {x∣aTx=aTx0​}，其满足 $a\ne 0$ 且 a T x ≤ a T x 0 , ∀ x ∈ C a^Tx\le a^Tx_0,\ \forall x\in C aTx≤aTx0​, ∀x∈C

支撑超平面定理：如果 $C$ 为凸集，那么 $C$ 的每个边界点都存在一个支撑超平面

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！