【通俗理解】凸優化

註：以下內容參考了Shu-Cherng Fang教授2009年在清華的夏季學期課程《Global Optimization with Applications》講義。

今天介紹一點凸優化方面的知識～內容可能有點無聊，看懂了這篇文章，會對求極值和收斂有進一步理解，比如：

了解為什麼向量機（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是否存在之類的，我們工科的學生不管這些了，直接套公式先跑起來再說～