【通俗理解】凸優化
注：如下內容參考了Shu-Cherng Fang教授2009年在清華的夏季學期課程《Global Optimization with Applications》講義。python
今天介紹一點凸優化方面的知識～內容可能有點無聊，看懂了這篇文章，會對求極值和收斂有進一步理解，好比：
算法
瞭解爲何向量機（SVM）等的推導中，求極值時能夠把約束條件加在目標函數後面來變成一個無約束的優化問題。微信
理解EM算法（聚類，GMM等）爲何收斂。網絡
以前文章有介紹過，一個算法有效至少要知足兩個條件：1）極值存在，2）收斂。極值不存在說明模型無效，算法無心義。算法不能收斂意味着找不到極值，也沒有價值。這兩個問題凸優化均可以幫咱們回答。框架
在開始以前，咱們先來回顧一下支持向量機（SVM）的推導過程。機器學習
SVM的任務就是尋找這樣一個超平面H把樣本無誤地分割成兩部分，而且使H1和H2的距離最大。要找到這樣的超平面，只需最大化間隔Margin，也就是最小化w^2。函數
而後直接告訴你：對於不等式約束的條件極值問題，能夠用拉格朗日方法求解。而拉格朗日方程的構造規則是：用約束方程乘以非負的拉格朗日系數，而後再從目標函數中減去。因而獲得拉格朗日方程以下：學習
爲何能夠這樣作？看完本文你就能理解了。區塊鏈
凸集合與凸函數：在前面一篇《黨給我智慧給我膽，梯度給我努力的方向》中，已經說明了梯度的做用，並指出我的的行爲都自覺或無心地順着梯度方向。優化
這不難理解。若是讓一個蒙上眼睛的人去山頂，他天然會選擇海拔升高的方向行走。至於最後能不能到達，要看地形。要是一個土丘（凸函數）那沒問題，若是要是連綿不斷的羣山（非凸函數），只能保證到達一個小山峯（極值），而這個不必定是全部山峯中最高的（最值）。
因爲凸函數的極值點就是最值點，相對於非凸函數，咱們更喜歡凸函數。這裏不但要求目標函數是凸的，其定義的空間也必須是凸的集合。正如要求地形是凸的，能走的路構成的集合也必須是凸的。
凸凸凸，到底啥是凸集合，啥是凸函數？？？
凸集合：知足集合內任意兩點的連線也在這個集合裏的就是凸集合。凸集合有個有趣的separating性質，以二維空間爲例，任意一點y不屬於這個凸集合，則必定存在一條直線把這個點和凸集合分開。
凸函數：下面兩個圖畫出了凸函數，也給出了凸函數的兩個性質：
兩點永遠過高；以下面第一個圖，用凸函數兩點之間的連線上的一點R來估計函數值L，永遠有R>L。
一點永遠過低；以下面第二個圖，用凸函數的切線上的一點R來估計函數值L，永遠有R<L。寫出
上面的第一個性質「兩點永遠過高」也能夠擴展到多個點的線性組合，寫起來就是Jensen不等式的形式
其中a_i取值0~1，a_i的和爲1。
根據第二個性質「一點永遠過高」，很容易證實黨給我智慧給我膽，梯度給我努力的方向裏提到的凸函數極值點的一個性質：
根據上面性質「一點永遠過高」的公式，有：
上面公式能夠從兩個層面來理解。一方面x*是極值，即任取定義域內一點獲得的f(y)>f(x*)；另外一方面定義域任選一點y沿着y-x*的方向必定能達到x*。找到x*以前是不知道方向y-x*的，一般用梯度。
上鏡圖：爲了把凸函數（convex function）和凸集合（convex set）一塊兒討論，要介紹一下上鏡圖（epigraph）的概念，以下圖所示就是函數f上方的全部點構成的集合。
分割定理和支撐定理：顯然，凸函數對應的上鏡圖是一個凸集合。這樣能夠和上面的第二個性質「一點永遠過低」聯繫起來了。稍微擴展一下到多維空間，二維空間的直線對應着多維空間的超平面（hyperplane）。第二個性質擴展到多維空間就是：存在一個超平面能夠支撐起這個函數對應的上鏡圖，並且這個超平面和函數有一個交點。這個超平面叫作「支撐超平面」（supporting hyperplane）。
如今能夠總結一下凸集合的兩個重要性質了：
separating：即凸集合能夠被一個超平面把凸集合和凸集合外的一點區分開（separating hyperplane存在）；
supporting：凸集合邊緣上任意一點都對應一個和凸集合相切的超平面（把整個空間分紅含有凸集合和不含凸集合兩部分）（supporting hyperplane存在）。
其中supporting定理經過函數上鏡圖的概念和凸函數聯繫起來了，這構成了凸優化中對偶性duality的基石。在凸優化中的對偶，和信號處理裏的傅里葉變換同樣重要。
對偶：對偶性，是經過對偶變換（conjugate transform）把原函數變成了另外一個函數（必定是凸的）。對函數y=f(x)來講，其對偶函數是以切線斜率k爲自變量，以切線和y軸交點y*爲值的函數。對應到多維函數，其對偶函數是以其支撐超平面（切平面）的正交方向向量，函數值是這個超平面和函數值對應座標軸的交點。寫出來是這個樣子的：
看不懂吧？先思考下面兩個問題：
前面說的「支撐切平面的正交方向向量」是個什麼鬼？
上面conjugate transform獲得的公式h(y)，爲何是個集合的形式，會有sup/inf？（sup/inf表示全部知足條件的當中選最大/小的那個）
回顧一下前面講supporting hyperplane前，先介紹了separating hyperplane。設想負無窮有一個點M，那麼存在separating hyperplane把這個凸函數的上鏡圖和M區分開，這無數個separating hyperplane構成一個集合，取sup/inf就是取到和函數上鏡圖相切的超平面！因此對偶函數對應着原函數對全部separating hyperplane組成的集合取sup/inf，即對偶函數對應着原函數的全部supporting hyperplane的集合。
對偶函數知足對偶不等式（conjugate inequality）
當y取值對應到切平面時取等號。此時y就是「支撐切平面的正交方向向量」，即梯度！上面第一個問題你回答上來了麼？
Primal problem & Dual problem：好了，如今大體對「對偶性」有一點幾何理解了，但這又和求極值有什麼關係？是否還記得小學「線性規劃」一節，極值必定出如今兩條直線的交點或某條直線上？換句話說，極值必定出如今幾條直線圍成的形狀的邊緣上，再換句話說，極值必定出如今幾條直線圍成的形狀的切線/切平面上。
受此啓發，因此對「切平面」重點研究多是正確的方向。再看上面的對偶不等式，若是有一些約束使得<x,y>=0，則f(x)的最小值就和-h(y)的最大值相等了，這樣就把求min{f(x)}問題轉化成求max{-h(y)}=min{h(y)}問題。稱初始求min{f(x)}的問題成爲primal problem，求min{h(y)}問題稱爲dual problem。
好的，如今知道了，某些條件下能夠經過求dual problem來間接求primal problem。但爲何有什麼好處？這是由於不少狀況下dual problem比primal problem好求解！
下圖是一個典型的問題，求X內函數f(x)的極值。
即便f(x)是一個簡單的凸函數（好比二次函數）也不太容易求解。問題的複雜性在於定義域是有約束條件（subject to some constraint）的。若是對x取值沒有約束（定義域X爲整個超平面），則根據凸函數極值點性質
很容易知道在極值點x*有對應的導數/梯度爲0。而對偶變換後，獲得的dual problem多是一個無約束條件的問題，很是容易求解。好比要求解：
s.t.是subject to的簡寫，是對x的約束條件。其對應的dual problem爲
是一個無約束的求極值問題，要簡單多了。
注意，上面說的求到了dual problem的極值，就知道了primal problem的極值，這是有條件的：<x,y>=0。當大於零時，所謂的duality gap就出現了。搞數學的人給出了一堆各類條件的定理，指出什麼條件下能夠沒有duality gap，這不是咱們工程師所關心的，不去浪費時間探討了。看到這裏，只要瞭解對偶是什麼回事就能夠了。
拉格朗日對偶：拉格朗日乘數法（Lagrange multiplier）在中學就學過了，用來求解有約束狀況下的極值問題。好比一我的從家M點到公司C點，中間要去小河邊打一桶水，在小河的哪一個位置打水最近？
河流的曲線方程g(x,y)就是這個問題的約束，要求的就是在這個約束條件下，到M和C點的距離和最近。直接套公式很容易求解，但相信不少人不明白爲何拉格朗日乘數法爲何起做用。這裏咱們把它套在duality的框架下進行討論。
定義拉格朗日函數（lagrangian function）以下
這和conjugate transform的區別僅僅在於一個<x,y>。不繼續說了，不然還要介紹鞍點（saddle point），強對偶，弱對偶，還有min-max和max-min的概念。這裏只是告訴你們拉格朗日乘數法也能夠歸結於duality的框架中。最前面的對偶一般叫作conjugate dual或geometric dual，Fenchel's dual，後面用拉格朗日函數的叫作Lagrangian dual。
對支持向量機（SVM）熟悉的同窗知道，推導時的目標函數是一個二次函數，約束條件是一個超平面把兩類標記的點分開。求解這個最優化問題（quadratic programing）就用了Lagrangian dual。有人說了，好像沒有看到有求所謂的h(y)啊，是否是打開方式不對？這是由於二次函數的duality仍是一個二次函數……好尷尬～下圖f(x)=0.5x^2，其conjugate dual是g(y)=-0.5y^2。
中學老師可沒有告訴你duality，直接讓你在目標函數後面把約束乘以一個拉格朗日乘子加在後面，你能理解纔怪……
KKT條件：實際上是對拉格朗日方法的一個擴展。必定要背下來，之後求解quadratic programing（目標函數是一個二次函數）時就套公式。不少實際問題的目標函數都是二次函數，由於二次函數能夠表明歐式距離（回想距離公式x^2+y^2），能夠表明能量（x^2），是一個好的error/cost function。
總結
對偶是凸優化的基石，延伸出各類優化方法。正如信號處理中時域上很差解決的問題變換到頻域去解決。遇到目標函數是二次函數的，直接看看KKT條件能不能用。數學系的學生要考察並證實duality gap是否存在之類的，咱們工科的學生無論這些了，直接套公式先跑起來再說～
往期回顧：