Convex Set

凸集愁拭，是一個(gè)在基礎(chǔ)數(shù)學(xué)課程中接觸過的概念枪汪。凸的背后，往往蘊(yùn)含著非常好的性質(zhì)暑诸，這也就是我們要去研究凸集的原因逗威。

仿射（Affine）

一個(gè)集合 $C$ 是仿射集峰搪，如果對(duì)任意 $x_1, x_2 \in C$ 和 $\theta \in \mathrm{R}$ 都有： $\theta x_1 + (1-\theta)x_2 \in C$ 需要注意的是這里的 $\theta$ 取值是全體實(shí)數(shù)（而不是介于0到1之間）。

仿射集可以寫成一個(gè)線性子空間的仿射凯旭，即存在子空間 $V$ 使得： $C=V+x_{0}=\left\{v+x_{0} \mid v \in V\right\}$ 類比非齊次線性方程組的解是一個(gè)仿射子集而對(duì)應(yīng)的齊次線性方程組的解是一個(gè)線性子空間概耻。

對(duì)任意一個(gè)集合 $C$ ，我們可以定義它的 affine hull： $\text { aff } C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} \mid x_{1}, \ldots, x_{k} \in C, \theta_{1}+\cdots+\theta_{k}=1\right\}$ 仿射包是包含這個(gè)集合的最小仿射集罐呼。

相對(duì)內(nèi)點(diǎn)：

relative interior

相對(duì)內(nèi)點(diǎn)與內(nèi)點(diǎn)是有所不同的鞠柄，比如考慮一個(gè)三維空間中的正方形。這個(gè)正方形內(nèi)部的點(diǎn)嫉柴，不是內(nèi)點(diǎn)厌杜，但是是相對(duì)內(nèi)點(diǎn)。再考慮三維空間中的一個(gè)球面计螺，它的相對(duì)內(nèi)點(diǎn)集是空集夯尽。

通過相對(duì)內(nèi)點(diǎn)還可以引出相對(duì)邊界這一概念。

凸集

一個(gè)集合 $C$ 是凸集登馒，如果對(duì)任意 $x_1, x_2 \in C$ 和 $\theta \in [0, 1]$ 都有： $\theta x_1 + (1-\theta)x_2 \in C$ 仿射集自然是凸集的一種呐萌，類比于仿射集的相關(guān)概念，我們可以得到凸包（convex hull）的定義谊娇。集合 $\mathrm{C}$ 的凸包是包含集合 $\mathrm{C}$ 的最小凸集肺孤。

cones 錐

在優(yōu)化理論中，錐是一個(gè)無限大的集合济欢，與日常所接觸的圓錐有所不同赠堵。一個(gè)集合 $C$ 是錐，如果對(duì)任意 $x \in C$ 和 $\theta \geq 0$ 都有： $\theta x \in C$

如果一個(gè)錐是凸的法褥，就稱它是一個(gè)凸錐茫叭。比如 $y=|x|$ 的圖像就是一個(gè)錐，但不是凸錐半等。但是 $y\ge |x|$ 就是一個(gè)凸的錐了揍愁。

仔細(xì)思考上述概念，任意一個(gè)錐 $K$ 是不是都有一個(gè)極限點(diǎn)是 $0$ 杀饵。如果它是閉的（closed）莽囤，那么 $0 \in K$ ！

類似的可以得到錐包（conic hull）切距，它是包含某個(gè)集合的最小的錐朽缎。 $\{\theta_1 x_1 + \cdots +\theta_k x_k \mid x_i \in C, \theta_i \geq 0, i=1, ..., k\}$

重要的例子

下面列舉一些重要的凸集的例子

一個(gè)點(diǎn)
注意這個(gè)是凸集哦~~~
超平面和半平面
球、橢球

正規(guī)錐（norm cones）
$C=\{(x, t) |\|x\| \leq t\} \subseteq \mathbf{R}^{n+1}$ 也被叫做二階錐（second order cones）。
凸多面體

$\mathcal{P}=\left\{x | a_{j}^{T} x \leq b_{j}, j=1, \ldots, m, c_{j}^{T} x=d_{j}, j=1, \ldots, p\right\}$

單純形 simplex

不同的兩個(gè)點(diǎn)话肖、不共線的三個(gè)點(diǎn)北秽、不共面的四個(gè)點(diǎn)，它們生成的凸包最筒，分別構(gòu)成了一維贺氓、二維、三維的單純形床蜘。
特別地掠归，unit simplex：
$x \succeq 0, \quad \mathbf{1}^{T} x \leq 1$ 離散型隨機(jī)變量的概率分布就是一個(gè)典型的 unit simplex。

半定矩陣錐
我們用記號(hào) $\mathrm{S}^n$ 來表示所有的 $n$ 階實(shí)對(duì)稱矩陣組成的集合悄泥， $\mathrm{S}^n_+$ 表示所有的半正定矩陣虏冻， $\mathrm{S}^n_{++}$ 表示所有的正定矩陣。其中弹囚， $\mathrm{S}_{+}^n$ 是一個(gè)閉的 convex cone厨相。所有的 $n$ 階方陣是一個(gè)線性空間， $\mathrm{S}^n_{+}$ 是這個(gè)線性空間的一個(gè)錐鸥鹉。
半定矩陣錐蛮穿，讓我們對(duì)凸集的認(rèn)識(shí)，從歐式空間毁渗，飛躍到了抽象的線性空間践磅！這讓我們得以在矩陣空間上考慮優(yōu)化問題。

保持凸性的操作

集合的交灸异、和府适、差
例：

無窮多個(gè)凸集的交，仍然是凸集肺樟。

由于我們討論凸集都是在 $\mathrm{R}^n$ 這個(gè)向量空間上討論檐春，因此所謂的“和”與“差”，都是 elementwise 的么伯。

仿射變換（affine transformation）

比如橢球就可以看作是球的仿射疟暖。
例子：

線性分?jǐn)?shù)變換（Linear fractional transformation）
可以看作是仿射變換的推廣，涉及到復(fù)變函數(shù)的知識(shí)田柔。

在最簡(jiǎn)單的情況下俐巴， $f(x)=\frac{ax+b}{cx+d}$ （是不是想到了些什么？）
特殊的情況下硬爆，是透視函數(shù)

一個(gè)凸集在透視函數(shù)的映射下仍然是凸的欣舵。透視函數(shù)的作用可以理解為是“針孔攝像頭”！（參見：透視函數(shù)）

直線上方是一個(gè)凸集摆屯，下方是透視函數(shù)的映射值域

總之邻遏，凸集，在線性分?jǐn)?shù)變換下的像/原像虐骑，都是凸的准验。

廣義不等式（generalized inequalities）

proper cones

乍一看這個(gè)概念很突兀。proper cone 最重要的作用是能定義一個(gè)集合上的偏序關(guān)系（partial ordering）：

$x \preceq_{K} y \Longleftrightarrow y-x \in K\;\; , \;x \prec_{K} y \Longleftrightarrow y-x \in \mathbf{int}K$

如果取 $K=R_+$ 廷没，那么得到的序關(guān)系就是正常的實(shí)數(shù)比較糊饱。
如果取 $K=R^{n}_+$ ，那么向量 $\vec{x}\preceq\vec{y}$ 當(dāng)且僅當(dāng)每個(gè)分量 $x_i \leq y_i$ 颠黎。

$\mathrm{S^{n}_+}$ 是 $\mathrm{S^n}$ 中的一個(gè) $\mathrm{proper\; cone}$ 另锋， $X\preceq_{K} Y$ ，當(dāng)且僅當(dāng) $Y-X$ 是半正定的狭归， $X\prec_{K} Y$ 夭坪，意味著 $Y-X$ 是正定的，所以很多時(shí)候我們直接簡(jiǎn)寫 $X\succ 0$ 來聲明 $X$ 是正定矩陣过椎。

這樣的偏序關(guān)系有非常良好的性質(zhì)：

最大和最小元素

有了序關(guān)系室梅，自然就會(huì)考慮這樣一個(gè)偏序集的最大/最小的元素（maximum/minimum）。

顯然疚宇，如果這樣的元素存在亡鼠，那么必然是唯一的。但實(shí)際上敷待，并不是所有的元素都是可比較的（comparable）间涵，我們可以藉此定義“極小元”、“極大元”（minimal, maximal）榜揖，意為勾哩，沒有元素比它們來的更大/更小，容易知道它們不是唯一的举哟。

用 $x-K$ 表示钳幅，所有的可以與 $x$ 比較的、并且小于等于 $x$ 的元素全體炎滞，此時(shí) $x$ 是 $S$ 中的極小元敢艰，當(dāng)且僅當(dāng)：
$(x-K) \cap S=\{x\}$

類似地，用 $x+K$ 表示所有與 $x$ 可以比較的册赛、并且大于等于 $x$ 的元素全體钠导。

$K=R^2_+$ 的情況如下圖，左圖的 $x_1$ 是最小點(diǎn)森瘪，而右圖的 $x_2$ 是極小點(diǎn)

分割和支撐超平面定理

?考慮兩個(gè)不相交的凸集牡属，是不是能找到一個(gè)超平面把它們分割開？扼睬？如果其中一個(gè)變成凹集逮栅，是不是就做不到了悴势？？

?對(duì)于 $n$ 維空間中的一個(gè)超平面措伐，我們習(xí)慣用 $\left\{x | a^{T} x=b\right\}$ 來表示特纤。一個(gè)超平面將全空間分割成兩個(gè)半空間。

?超平面分割定理侥加，說的就是兩個(gè)不相交的凸集捧存，一定存在 $a \neq 0$ 的超平面使得在其中一個(gè)凸集滿足 $a^T x\ge b$ ，而另一個(gè)凸集中成立 $a^T x \leq b$ 担败。這個(gè)超平面 $\left\{x | a^{T} x=b\right\}$ 就叫做這兩個(gè)凸集的分割超平面昔穴。

?進(jìn)一步，如果不等關(guān)系嚴(yán)格成立提前，就說這兩個(gè)凸集被嚴(yán)格分割（strict separation）吗货。

定義兩個(gè)凸集的歐幾里得距離是這兩個(gè)集合中兩個(gè)點(diǎn)距離的下確界： $\operatorname{dist}(C, D)=\inf \left\{\|u-v\|_{2} | \;u \in C, v \in D\right\}$

?乍一看，好像很多的凸集對(duì)都是可以被嚴(yán)格分割的狈网。注意凸集不一定要是閉的卿操。

兩個(gè)開的不相交的凸集很容易找到例子說明它們可能不能被嚴(yán)格分割。當(dāng)兩個(gè)不相交的凸集都是閉的孙援，比如 $A=\{(x, y) | x y \geq 1, x, y>0\}$ 和 $B=\{(x, y) | x \leq 0\}$ 害淤，也可能不能被嚴(yán)格分割。

?其實(shí)不然拓售，嚴(yán)格分割只在某些特定的情況下窥摄。比如一個(gè)閉凸集和這個(gè)凸集外的一點(diǎn)，這兩個(gè)凸集是可以被嚴(yán)格分割的础淤。如果這個(gè)凸集是開的崭放，并且這個(gè)點(diǎn)選為凸集的邊界點(diǎn)，那么就不能被嚴(yán)格分割鸽凶。

點(diǎn)與凸集的分離定理币砂，說的正是閉凸集和集合外一點(diǎn)可以被嚴(yán)格分割；利用它玻侥，我們進(jìn)一步才得到下面的支持超平面定理决摧。

?通過上一段的那個(gè)結(jié)論，我們可以得到凑兰，任意一個(gè)閉凸集是所有包含這個(gè)凸集的半空間的交掌桩。

利用凸集分離定理，可以得到一個(gè)有趣的結(jié)論：

支撐超平面

?對(duì)凸集 $C$ 姑食，如果有 $x_{0} \in \mathbf{b d} C=\mathbf{cl} C \backslash \mathbf{ int } C$ 波岛，并且 $a^{T} x \leq a^{T} x_{0}\;\;\; \text { for all } x \in C$

?那么超平面 $\left\{x | a^{T} x=a^{T} x_{0}\right\}$ 就叫做 $C$ 在 $x_0$ 這點(diǎn)的支撐超平面。凸集的任何個(gè)邊界點(diǎn)都存在支撐超平面音半，這就是支撐超平面定理则拷。

support hyperplane

?值得一提的是贡蓖，支撐超平面定理的逆定理也成立。即如果一個(gè)內(nèi)點(diǎn)集非空的閉集煌茬，在每一個(gè)邊界點(diǎn)上都有一個(gè)支撐超平面斥铺，那么它是凸的。

對(duì)偶錐（dual cones）

設(shè) $K$ 是個(gè)錐宣旱，定義 $K$ 的對(duì)偶錐為： $K^{*}=\left\{y | x^{T} y \geq 0 \text { for all } x \in K\right\}$ 仅父。顧名思義叛薯， $K^{*}$ 是一個(gè)錐浑吟，更有意思的是 $K^*$ 總是凸的，不論 $K$ 是不是凸的耗溜。

例：

線性空間的子空間 $V$ 的對(duì)偶錐是其正交補(bǔ) $V^\perp$ 组力。

從幾何上看， $K^*$ 中任意一點(diǎn)與 $K$ 中所有點(diǎn)的夾角不超過90°抖拴。

非負(fù)象限和半正定錐的對(duì)偶錐是其本身燎字，稱其為自對(duì)偶錐（self-dual）。

The dual of the $p$ norm, denoted by $\|\cdot\|^{*},$ is the $q$ norm, where $\frac{1}{p}+\frac{1}{q}=1$

對(duì)偶錐有以下性質(zhì)：

pointed: if $x\in K, -x \in K$ 阿宅，then $x=0$

這些性質(zhì)說明如果 $K$ 是一個(gè) proper cone候衍，那么 $K^*$ 也是一個(gè) proper cone，并且 $K=K^{**}$ 洒放。

對(duì)偶廣義不等式

之前我們已經(jīng)知道 proper cone $K$ 能誘導(dǎo)出一個(gè)偏序關(guān)系◎嚷梗現(xiàn)在 $K^*$ 也是一個(gè) proper cone，是不是通過 $K^*$ 也能定義一個(gè)偏序關(guān)系了往湿。

此外妖异，通過對(duì)偶性可以給出廣義不等式的等價(jià)命題：

$x \preceq_{K} y \Leftrightarrow \lambda^{T} x \leq \lambda^{T} y ,\; \; \forall \lambda \succeq_{K^{*}} 0$
$x \prec_{K} y \Leftrightarrow \lambda^{T} x<\lambda^{T} y,\;\; \forall \lambda \succeq_{K^{*}} 0, \lambda \neq 0 .$

通過定義很容易驗(yàn)證上圖的結(jié)論。

上式的含義是领追，對(duì)偶錐中的每個(gè)元素（向量）可以看成原來錐的一個(gè)合法的投影方向他膳，原來錐上兩個(gè)點(diǎn)在這些合法的投影方向上序不變！ 在錐形式的對(duì)偶中就要用到這條性質(zhì)绒窑。

we have $\lambda \preceq_{K^*} \mu$ if and only if $\lambda^{T} x \leq \mu^{T} x$ for all $x \succeq_K 0$

?聯(lián)系超平面分割定理棕孙，我們還能得到下面這個(gè)非常重要的結(jié)論：

Theorem of alternatives for linear strict generalized inequalities
$A x \prec_{K} b$ is infeasible if and ony if $\lambda \neq 0, \quad \lambda \succeq_{K^*} 0, \quad A^{T} \lambda=0, \quad \lambda^{T} b \leq 0$

對(duì)偶不等式與最小元/極小元

借助對(duì)偶性可以建立起最小元和極小元的相關(guān)理論。

?對(duì)于極小元些膨，沒有充分必要的條件散罕。

?充分條件：如果 $\lambda \succ_{K^*} 0$ 并且 $x$ 使得 $\lambda^{T} z$ 最小（對(duì) $z \in S$ ）傀蓉，那么 $x$ 就是極小元欧漱。（找到一個(gè)方向，在這個(gè)方向上的投影是最小的葬燎。）

?反之不然误甚。但如果 $S$ 是凸集缚甩，那么就是充分必要的。

（完結(jié)撒花）

最后編輯于：2021.04.18 16:41:27

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末窑邦，一起剝皮案震驚了整個(gè)濱河市擅威，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌冈钦，老刑警劉巖郊丛，帶你破解...
沈念sama閱讀 211,290評(píng)論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異瞧筛，居然都是意外死亡厉熟，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,107評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門较幌，熙熙樓的掌柜王于貴愁眉苦臉地迎上來揍瑟，“玉大人，你說我怎么就攤上這事乍炉【钇” “怎么了？”我有些...
開封第一講書人閱讀 156,872評(píng)論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵岛琼，是天一觀的道長底循。經(jīng)常有香客問我，道長槐瑞，這世上最難降的妖魔是什么熙涤？我笑而不...
開封第一講書人閱讀 56,415評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮随珠，結(jié)果婚禮上灭袁，老公的妹妹穿的比我還像新娘。我一直安慰自己窗看，他們只是感情好茸歧，可當(dāng)我...
茶點(diǎn)故事閱讀 65,453評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著显沈，像睡著了一般软瞎。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上拉讯，一...
開封第一講書人閱讀 49,784評(píng)論 1贊 290
城市分裂傳說
那天涤浇，我揣著相機(jī)與錄音，去河邊找鬼魔慷。笑死只锭，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的院尔。我是一名探鬼主播蜻展，決...
沈念sama閱讀 38,927評(píng)論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼喉誊，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了纵顾？” 一聲冷哼從身側(cè)響起伍茄，我...
開封第一講書人閱讀 37,691評(píng)論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎施逾，沒想到半個(gè)月后敷矫，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,137評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡汉额，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,472評(píng)論 2贊 326
?白月光啟示錄
正文我和宋清朗相戀三年曹仗，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片闷愤。...
茶點(diǎn)故事閱讀 38,622評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡整葡，死狀恐怖件余，靈堂內(nèi)的尸體忽然破棺而出讥脐，到底是詐尸還是另有隱情，我是刑警寧澤啼器，帶...
沈念sama閱讀 34,289評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布旬渠，位于F島的核電站，受9級(jí)特大地震影響端壳，放射性物質(zhì)發(fā)生泄漏告丢。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,887評(píng)論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一损谦、第九天我趴在偏房一處隱蔽的房頂上張望岖免。院中可真熱鬧，春花似錦照捡、人聲如沸颅湘。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,741評(píng)論 0贊 21
一樁弒父案栗精，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽闯参。三九已至，卻和暖如春悲立，著一層夾襖步出監(jiān)牢的瞬間鹿寨，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,977評(píng)論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工薪夕，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留脚草，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,316評(píng)論 2贊 360
代替公主和親
正文我出身青樓原献，卻偏偏與公主長得像馏慨，于是被迫代替她去往敵國和親涩蜘。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,490評(píng)論 2贊 348