[CVX01] Convex Set

這是XJTU秋下學期《凸分析與最佳化》課程的筆記，共32課時。概念比較多，複雜且易混淆，我放棄嘗試英文記錄。（因為我發現數學嚴格定義的語序上英文總是與中文相反。。。。。）

內容除了老師使用的的中文slides外，部分不嚴格的定義參考了斯坦福CVX的slides；同時老師對一些定理做了推導證明；

Convex Set

definition:

令集合

$C \subseteq \mathbb{R}^{n}$

，對於

$\forall x, y \in C$

和

$\forall \alpha \in [0,1]$

如果有

$\alpha \boldsymbol{x}+(1-\alpha) \boldsymbol{y} \in C$

，則稱

為凸集。約定空集是凸集。

example:

超平面

球

$B(\boldsymbol{z}, \delta)={\{x \in \mathbb{R}^{n} |\|\boldsymbol{x}-\boldsymbol{z}\|<\delta \}}$

正定矩陣、半正定矩陣、對稱矩陣

保持凸性的運算：

（

和

均為凸集）

$C_{1} \cap C_{2}$

和

（向量和）

任意scalar

$\lambda$

，

$\lambda C$

是凸集

閉包

和內部

都是凸集

仿射變換下的像和原像

$\text { suppose } f: \mathbf{R}^{n} \rightarrow \mathbf{R}^{m} \text { is affine }\left(f(x)=A x+b \text { with } A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{m}\right)$

$S \subseteq \mathbf{R}^{n} \text { convex } \Longrightarrow f(S)={f(x) | x \in S} \text { convex }$

$C \subseteq \mathbf{R}^{m} \text { convex } \quad \Longrightarrow \quad f^{-1}(C)=\{x \in \mathbf{R}^{n} | f(x) \in C\} \text { convex }$

泛函概念補充(此課程預設prerequisite是泛函分析？)

內點：對於度量空間

，

$M \subset X$

，如果

$x \in M$

，

$\exists r > 0$

，若

$B(x, r) \subset M$

，

為

的內點；（一般的度量空間需要滿足一些性質，比一般的向量空間更加寬泛，嚴格定義參看泛函中的定義）

內部：

中所有的內點集合為內部，記做

開集：如果

，

是開集

如果

差集為開集，則

是閉集

聚點（還有別的翻譯）：如果

$x\in M$

，

$M \cap (B(x, r) / {x}) \neq \emptyset$

則

是

的聚點；

閉包：所有聚合點與內點的並集即為

的閉包；那麼閉集就等價於閉包；

Convex Combination and Convex Hull

definition:

集合

$C \subseteq \mathbb{R^n}$

，則稱

$\mathbb{R^n}$

中所有包含

的凸集的交集為

的

凸包

；記做

$x^{1}, \ldots, x^{m} \in C, \alpha_{1}, \ldots, \alpha_{m} \geq 0, \sum_{i=1}^{m} \alpha_{i}=1$

，稱

$\boldsymbol{y}=\sum_{i=1}^{m} \alpha_{i} \boldsymbol{x}^{i}$

為

中

個向量的凸組合；

可以用凸組合來定義凸包：

中任意向量均可表示

中有限個向量的凸組合，既對任意

$\forall x \in C$

有：

$\boldsymbol{x}=\sum_{i=1}^{m} w_{i} \boldsymbol{x}_{i},\ \boldsymbol{x}_{i} \in C, w_{i} \in [0, 1], i=1, \ldots, m,\ \sum_{i=1}^{m} w_{i}=1$

properties

of Convec Hull：

是凸集，

$x \in conv(C)$

，則

$\operatorname{conv}(C \cup{x})=\operatorname{conv}(C)$

$C_1, C_2 \subseteq \mathbb{R^n}$

則

$\operatorname{conv}\left(C_{1}+C_{2}\right)=\operatorname{conv}\left(C_{1}\right)+\operatorname{conv}\left(C_{2}\right)$

Affine Set \ Combination \ Hull

definition:

$x^{1}, \ldots, x^{m} \in C, \alpha_{1}, \ldots, \alpha_{m} \in \mathbb{R}, \sum_{i=1}^{m} \alpha_{i}=1$

，稱

$\boldsymbol{y}=\sum_{i=1}^{m} \alpha_{i} \boldsymbol{x}^{i}$

為

仿射組合

；（與凸組合的區別在於去掉了［0， 1］的限制）

對於

$\forall x,y \in C$

和

$\forall \alpha \in \mathbb{R}$

，如果有

$\alpha \boldsymbol{x}+(1-\alpha) \boldsymbol{y} \in C$

成立，則稱

為

仿射集

。

$\mathbb{R^n}$

中所有包含

的仿射集的交集稱為

的

仿射包

，記做

Theorem:

中任意向量均可以表示為$C$ 中有限個向量的仿射組合。

example:

仿射集

實數空間

$\mathbb{R^n}$

中的點線、超平面

矩陣的零空間

$\operatorname{null}(A)=\{\boldsymbol{x} \in \mathbb{R}^{n} | A \boldsymbol{x}=0\}$

properties

of affine hull

對任何集合

。必然存在

$\operatorname{aff}(C)=\operatorname{aff}(\operatorname{conv}(C))=\operatorname{aff}(\operatorname{cl}(C))$

proof

（作業，自己的證明，待嚴格驗證）

（1）證明

a。如果

是凸集，則，

兩個集合的仿射包自然相等；

b。如果

不為凸集，

$\forall x \in conv(C)$

有

$x = \sum_i^m {\alpha_i x^i},\ x^i \in C,\ \alpha_i \in (0,1],\ \sum{\alpha_i} = 1 \\ aff(x) \sum{}\beta_i\sum{\alpha_i x^i} , \sum{\beta_i} =1,$

即是

中向量正組合，

$aff(x) \subseteq aff(C)$

反過來一樣，

可以證明；

（2）證明

a。若

是閉集，則

，相應仿射包也相同

b。若

是開集，

$cl(C) = {x| B(x,\epsilon) \cap C \neq \emptyset}$

，則

$aff(x) = \sum{\beta_i x^i},\ x^i \in cl(C)$

則一定能找到

$\exists y^i \in C$

，使得

$\exists y^i \in C$

，

仍可以表示為

中向量的正組合，兩個仿射包相同；

Cone 錐

definition

$C \subseteq \mathbb{R^n}$

，

$x \in C$

，

$\forall \alpha>0$

， if

$\alpha x \in C$

，則

為一個

錐

，若

為凸集，

是凸錐；

錐不一定是凸集；（如兩個交叉直線）

如果

是錐，一定有

$0 \in cl(C)$

中所有元素的

非負組合

的全體成為

的

生成錐

，記做

生成錐為凸錐且一定包含原點；

不一定為閉集

有限，其生成錐一定是閉集

properties

of 錐集

$C1 \cap C2$

也是錐

$C1 \times C2$

笛卡爾積也是錐；

向量和也是錐；

也是錐

線性變換

也是錐

properties

$aff(conv(C)) \subseteq aff(cone(C))$

若

$0 \in conv(C),\ aff(conv(C)) = aff(cone(C))$

Caratheodory定理

設

$C \subseteq \mathbb{R^n}$

非空，則

中每一個向量均可以表示為

中

個線性獨立向量的正組合；

中每一個不屬於

的向量均可以表示為

中

個向量的凸組合，且

$m \leq n+ 1$

；

乍一看這個定理貌似與凸包的定義相似，貌似是很顯然的事情；區別在於

$m \leq n+1$

的證明上，因為從凸包的定義出發只能證明凸包中的向量可以由其他有限個向量的凸組合。而上述定理說明了不屬於

的向量最多用

個向量表示出來；

Proof：

令

$x \in C$

，

$C \subseteq \mathbb{R^n}$

則定義

，

$Y \subseteq \mathbb{R^{n+1}}$

，

令

$\bar{x} \in conv(C) / C$

，由凸包定義，

$\bar{x}= \sum_i^I\alpha_ix^i\ ,\ x^i \in C,\ \sum{\alpha_i} = 1,\ \alpha_i \in (0,1]$

那麼

$(\bar{x}, 1) = (\sum_i^I\alpha_ix^i, \sum_i^I\alpha_i) = \sum_i^I\alpha_i(x^i, 1) \subseteq cone(Y)$

則，依據定理第一條（證明略）：

$(\bar{x}, 1) = \sum_i^M r_i(x^i, 1)$

，且

$M \leq n+1$

Fig1

顯示了第二條定理：

Fig1 凸包中不在原凸集中的點一定能由凸集中至多n+1個向量凸組合表示

相對內部

相對內部的概念對之後凸分析有幫助，這裡先給出定於與相關性質

definition:

令集合

是非空凸集，若

$x \in C$

，

$B(x, \epsilon)$

是開球，若滿足

$B\ \cap\ aff(C) \subseteq C$

，則稱

是

的

相對內部點

全體相對內部點稱作$C$的相對內部，記做

；約定單點集的相對內部是他本身。

若

，則稱集合$C$是相對開的。

稱作

的相對邊界

example

$\mathbb{R^3}$

中的集合

$C=\{\boldsymbol{x} \in \mathbb{R}^{3} | x_{1}^{2}+x_{2}^{2} \leq 1, x_{3}=1\}$

仿射包與相對內部分別為：

$\operatorname{aff}(C)=\{\boldsymbol{x} \in \mathbb{R}^{3} | x_{3}=1\}, \\\operatorname{ri}(C)=\{\boldsymbol{x} \in \mathbb{R}^{3} | x_{1}^{2}+x_{2}^{2}<1, x_{3}=1\}$

其內部是空集，閉包是非空凸集；可以看出三維空間中平面上的內部的定義就失效了，因為內點是相對

$\mathbb{R^3}$

定義的，而相對內點是針對仿射包定義的；

Theorem：線段原理、延伸引理

令集合

為非空凸集，

若

$x \in ri(C)$

，

$\bar{x} \in cl(C)$

，則連線

與

$\bar{x}$

的線段上，除

$\bar{x}$

外，所有點均屬於

；

$x \in ri(C)$

iif，對於任意

$\bar{x} \in C$

存在

$\gamma > 0$

使得

$x+\gamma(x-\bar{x}) \in C$

properties

設集合

是非空凸集，則

是非空凸集；

$\operatorname{aff}(\operatorname{ri}(C))=\operatorname{aff}(C), \operatorname{cl}(C)=\operatorname{cl}(\operatorname{ri}(C), \operatorname{ri}(C)=\operatorname{ri}(\operatorname{cl}(C))$

設

$\bar{C}$

是另一個非空凸集，則下面三個條件是等價的

$ri(C) = ri(\bar{C})$

$cl(C) = cl(\bar{C})$

Reference

老師的課件

Stanford CVPX ~Boyd 第一講的slides

泛函的內部定義

Carathéodory‘s theorem （convex hull））

課上老師的證明還有很多，部分沒跟上，下次課儘量全部記錄下來；下一講是凸函式。

小蜜蜂問答

小蜜蜂問答

[CVX01] Convex Set

推薦文章

小蜜蜂問答

小蜜蜂問答

[CVX01] Convex Set

相關文章

火字旁一個文組詞？

衛星恆星定義？

解向量和基礎解系區別？

n-ra是否表示基礎解系中的向量個數？

推薦文章