凸最佳化之拉格朗日對偶

最佳化問題存在於生活中的方方面面，大到一個公司對某個區域的物資調配，小到個人旅遊的最佳路線，都涉及到最佳化方面的知識。最佳化問題通常分為凸最佳化問題與非凸最佳化問題。什麼是凸問題呢？如果一個問題的最優解是其全域性最優解，那麼我們就說這個問題是全域性最優解。很明顯，凸問題有個最大的優點就是：一旦我們找到一個區域性最優解，那麼我們不必再去尋找更優的解，因為這個解一定是全域性最優解。然而這種情況只存在於理想狀態，現實生活中的問題往往有很多限制條件，比如物資調配，事實上沒有那麼多資源去運輸物資，也就是說需要在有限的運輸條件下完成整個物資的調配，同時儘量節省成本（詳見transportation problem）。限制條件的引入有些時候會使得問題變成一個非凸的問題，這時候就需要想一些別的辦法來解決問題，比如利用拉格朗日對偶性將原問題轉化為對偶問題進行求解。

這裡將從三個部分展開討論，再結合一個例項給出具體的應用：

廣義拉格朗日函式

對偶問題

Slater條件與KKT條件

SVM

1、廣義拉格朗日函式

首先有這樣一個問題：

對於一個連續可微的函式

，求：

$min~f(x)\\$

如果

是凸函式，可以很容易對

求導，令其為0，解得

$x^{\star}$

，再代入原函式得到

$f(x^{\star})$

就是我們所求的最優解；

如果是下面這樣的問題呢？

仍連續可微且為凸函式，求：

$min~f(x)\\ s.t.~~c_i(x)\leq0 ~~i=1,2,3,\cdots,m\\ ~~~~~~~~h_j(x)=0~~j=1,2,3,\cdots,n$

這個問題的求解就比上一個問題複雜許多了，上一個問題中x的取值是沒有限制，沒有約束的，所以我們可以直接求導，這一個問題中，x要滿足

$c_i(x)\leq0$

且

，也就是說x的取值範圍受到了限制，有了約束，其定義域不再是原函式的定義域，所以直接求導是不可取的。為了求解這樣一個問題，我們可以想：怎樣把這個有約束的問題轉化為無約束的問題呢？如果能轉化成無約束的問題，x沒有取值限制，那麼我們又可以簡單求導就能求解了。大神拉格朗日想了一個十分巧妙的辦法，把約束條件整合到原來求解的函數里面，並且給每個約束條件分配一個權重因子（拉格朗日乘子），於是乎，拉格朗日函式誕生：

$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^m\alpha_ic_i(x)+\sum_{j=1}^n\beta_jh_j(x)\\ \alpha_i\ge0$

在定義拉格朗日函式的時候，並沒有對

的具體形式要求，也就是說對任意

都可以寫成這樣的形勢，因此稱它為廣義拉格朗日函式。

可以看到，這個函式

已經沒有關於x的限制條件

了，但是它和我們要求解的問題有什麼關聯呢？我們要求的是

對吧。別急，咱們一步一步來。

現在我們已經有了拉格朗日函式，要想辦法把拉格朗日函式與原問題對等起來，為此構建一個新的函式：

$\theta_p(x)=\max_{\alpha_i\ge0,\beta}L(x,\alpha,\beta)=\max_{\alpha_i\ge0,\beta}[f(x)+\sum_{i=1}^m\alpha_ic_i(x)+\sum_{j=1}^n\beta_jh_j(x)]\\$

這個函式是關於變數x的函式，即對於每一個給定的x，去尋找合適的引數

$\alpha,\beta$

，使得找到的

$\alpha,\beta$

使拉格朗日函式的值最大。具體的，針對x的不同取值，我們觀察一下這個函式的結果。

1、如果x滿足約束條件，即

$c_i(x)\leq0$

且

，則

$\theta_p(x)=\max_{\alpha_i\ge0}[f(x)+\sum_{i=1}^m\alpha_ic_i(x)]$

，因為

$\alpha_ic_i(x)\le0$

，所以

$\theta_p(x)=f(x)$

；

2、如果x不滿足約束條件，即

$c_i(x)\geq0$

或

$h_i(x)\ne0$

，如果要maxmize函式，

$\alpha$

可以取得無窮大，所以

$\theta_p(x)=+\infty$

。

綜合1和2，

$\begin{equation} \theta_p(x)=\left\{ \begin{aligned} f(x) & & x滿足約束條件 \\ +\infty& & x不滿足約束條件 \end{aligned} \right. \end{equation}$

所以

$\min \theta_p(x)=\min f(x)$

，這樣一來，我們成功的用拉格朗日函式表示了原始問題，並且將原始問題取值的限制條件去掉了，最終原始問題的表達形式如下：

$\min_x \theta_p(x)=\min_x\max_{\alpha_i\ge0,\beta}L(x,\alpha,\beta)\\$

有的時候，這個問題的求解仍然比較複雜，比如在約束多變數少的時候，直接求解會很麻煩，這個時候需要考慮對偶問題。

2、對偶問題

什麼是對偶呢？通俗的說就是

$\min \max f(x)$

轉化成

$\max \min f(x)$

。怎樣轉化呢？

定義一個新的函式

$\theta_D(\alpha,\beta)=\min_{x}L(x,\alpha,\beta)$

，易知對任意的

$x,\alpha,\beta$

都有：

$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\le L(x,\alpha,\beta)\le \max_{\alpha_i\ge0,\beta}L(x,\alpha,\beta)=\theta_p(x)\\$

即對任意的

$x,\alpha,\beta$

都有

$\theta_D(\alpha,\beta)\le\theta_p(x)$

，那麼：

$\max_{\alpha,\beta} \theta_D(\alpha,\beta)\le \min_x\theta_p(x)\\$

我們稱

$\min_x\theta_p(x)$

為原始問題（primal problem），

$\max_{\alpha,\beta} \theta_D(\alpha,\beta)$

為對偶問題（當然要滿足條件

$\alpha_i\ge0$

）。對偶問題的最優解總是小於等於原始問題的最優解，稱之為

弱對偶性

。得到這個性質有什麼用呢，就算求出對偶問題的最優解，仍然不知道原始問題的最優解對吧，所以我們要把不等號去掉。不等號去掉是有一定條件的，好在這個條件大部分情況下我們都能滿足，不然轉化為對偶問題也沒什麼意義了。

3、Slater條件和KKT條件

Slater條件如下：

這裡的

$d^\star,p^\star$

分別為對偶問題與原始問題的最優解。也就是說，原函式以及不等式約束的函式必須是凸函式，等式約束函式是線性函式，以及不等式條件是嚴格不等式，這樣對偶問題的最優解就是原始問題的最優解。取得最優解的

$x^\star,\alpha^\star,\beta^\star$

滿足下面的關係：

$\nabla_xL(x^\star,\alpha^\star,\beta^\star)=0\\ \alpha_i^\star c_i(x^\star)=0\\ c_i(x^\star)\le0\\ h_i(x^\star)=0\\ \alpha_i^\star\ge0$

以上就是著名的KKT（Karush-Kuhn-Tucker）條件，用這個條件可以很方便的求解引數。其中第二個是KKT中非常重要的對偶互補條件。這個條件有兩層含義：1）如果

$\alpha_i^\star=0$

，意味著這個條件不是嚴格的約束條件，可以省略掉；2）如果

$\alpha_i^\star\ne0$

，意味著

$c_i(x^\star)=0$

，那麼最優解

$x^\star$

的取值落在約束條件的邊界上，因此演算法可以直接從邊界尋找最優解，比如單純形演算法。

以上就是對於一個約束的最佳化問題轉換成無約束的對偶問題的全部過程，比較注重公式推導，下面用一個機器學習中十分常用的演算法SVM，看如何用對偶問題求原問題的解。

4、SVM

SVM示意圖如下：

分離超平面為

，支援向量之間的間隔為

$\frac{2}{||w||}$

，因此目標函式可以寫成：

$\max \frac{2}{||w||}\\ s.t.~y_i(w^Tx_i+b)\ge1$

其中

$y_i\in\{-1,1\}$

，轉化為最小問題：

$\min \frac{1}{2}||w||^2\\ s.t.~1-y_i(w^Tx_i+b)\le0$

寫出對應的拉格朗日函式：

$L(\alpha,w,b)=\frac{1}{2}w^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))~~~(\alpha_i\ge0)\\$

由之前的推導可以寫出

原始問題

形式為：

$\min_x\max_{\alpha_i\ge0}L(\alpha,w,b)=\min_x\max_{\alpha_i\ge0}[\frac{1}{2}w^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))]\\$

其

對偶問題

為：

$\max_{\alpha_i\ge0}\min_xL(\alpha,w,b)=\max_{\alpha_i\ge0}\min_x[\frac{1}{2}w^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))]\\$

由於原問題中目標函式與約束條件均滿足slater條件，所以對偶問題的最優解就是原問題的最優解。我們把對偶問題對

求導然後等於0，可以求解

$w^\star=\sum_{i=1}^m\alpha_iy_ix_i$

，對b求導等於0得到

$\sum_{i=1}^m\alpha_iy_i=0$

，再將

$w^\star$

帶入對偶問題的目標函式，得到：

$\max_{\alpha_i\ge0}[\frac{1}{2}\sum_{j=1}^m\alpha_jy_jx_j^T\sum_{i=1}^m\alpha_iy_ix_i+\sum_{i=1}^m\alpha_i(1-y_i(\sum_{j=1}^m\alpha_jy_jx_j^Tx_i+b))]\\$

$\max_{\alpha_i\ge0}[\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_j\alpha_iy_jy_ix_j^Tx_i+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\alpha_iy_i\sum_{j=1}^m\alpha_jy_jx_j^Tx_i+\sum_{i=1}^m\alpha_iy_ib]\\$

$\max_{\alpha_i\ge0}[-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_j\alpha_iy_jy_i(x_j^T\cdot x_i)+\sum_{i=1}^m\alpha_i]\\$

其中

$\alpha_i\ge0$

。

以上就是對偶問題最終的表達形式，可以看到明顯將原問題較為複雜的最佳化條件變成

$\alpha_i\ge0$

這樣十分簡單的約束。同時，透過對偶形式，我們發現了另外一個有意思的現象，由於

$w^\star=\sum_{i=1}^m\alpha_iy_ix_i$

，因此分離超平面

就等於

$\sum_{i=1}^m\alpha_iy_i(x_i^T\cdot x)+b^\star=0$

，這意味著分類邊界只依賴於輸入的例項與訓練樣本資料間的內積，因此對於線性不可分資料，我們可以將資料特徵對映到高維，然而不用具體的計算這種對映關係，只需要計算對映到高維空間後特徵向量的內積就行了，所以就有了核函式這種十分強大的技巧去隱式的計算對映到高維空間後向量的內積。這就是轉換成對偶問題後帶來的發現。

以上是對拉格朗日函式與對偶性的小結，凸最佳化這塊內容很多，以後有時間可以好好看一下Boyd的convex optimization這本書。

參考資料：

［1］。李航，《統計學習方法》第二版

凸最佳化之拉格朗日對偶

肋骨鼻術後怎麼護理?術後七天要做哪些事情?

有限元接觸解析方法: 罰函式法，Lagrangian，遞增Lagrangian乘數法*1，內點法

隨便看看

狗狗生完孩子為什麼還會總撓地板呢？

178的十進位制計算過程？

羅漢魚苗尾巴開叉了長大能長上嗎？

好人家和錦橋香腸佐料哪個好吃？

凸最佳化之拉格朗日對偶

肋骨鼻術後怎麼護理?術後七天要做哪些事情?

有限元接觸解析方法: 罰函式法，Lagrangian，遞增Lagrangian乘數法*1， 內點法

猜你喜歡

wps表格分數的查詢與引用？

上聯，有錢任性。下聯，沒錢認命。求橫批？

生產要素最優組合是什麼？

隨便看看

狗狗生完孩子為什麼還會總撓地板呢？

178的十進位制計算過程？

羅漢魚苗尾巴開叉了長大能長上嗎？

好人家和錦橋香腸佐料哪個好吃？

有限元接觸解析方法: 罰函式法，Lagrangian，遞增Lagrangian乘數法*1，內點法