Lagrange Duality

05-22

Lagrange Duality

來自專欄機器學習

SVM問題定義、推導中我們給出了SVM問題的定義，並給出了優化目標和約束，為了快速高效地求解SVM，會用到拉格朗日對偶，本節對拉格朗日對偶進行介紹，主要內容來自於《凸優化》和Andrew課堂。

1. 原始問題

假設 $f(x),h_{i}(x),g_{j}(x)$ 是定義在 $R^{n}$ 上的連續可微函數 $min_{w} f(w)$ ，考慮約束最優化問題

$min_{w} f(w)$

$s.t. h_{i}(w)=0,i=1,...,l.$

稱為約束最優化問題的原始問題。如果不考慮約束條件，原始問題就直接是：

$min_{w} f(w)$

利用其連續可微的性質直接對 $f(x)$ 進行假設，然後令倒數為0即可得到最優解。但是由於約束條件的存在，難以直接求解，如果能有辦法把約束條件去掉就非常方便了，那麼Lagrange Function就是為了去掉約束條件進行求解的。

我們定義Lagrangian為：

$L(w,eta)=f(w)+sum_{i=1}^{l}{eta_{i}h_{i}(w)}$

其中 $eta_{i}$ 稱為Lagrange multipliers，我們可以將L的偏導數設置為0來進行求解

$frac{partial L}{partial w_{i}}=0;frac{partial L}{partial eta_{i}}=0$

將Lagrangian推廣到約束優化問題，其不光有equality constraints but also inequality constraints. 我們稱下面為primal optimization problem:

$min_{w} f(w)$

$s.t. g_{i}(w)le 0,i=1,...,k.$

$h_{i}(w)=0,i=1,...,l.$

我們定義Generalized Lagrangian為

$L(w,alpha,eta)=f(w)+sum_{i=1}^{k}{alpha_{i}g_{i}(w)}+sum_{i=1}^{l}{eta_{i}h_{i}(w)}$

其中 $alpha_{i},eta_{i}$ 均為Lagrange Multipliers，我們將 $L(w,alpha,eta)$ 看作是關於 $alpha_{i},eta_{j}$ 的函數，要求取最大值，在給定某 $w$ 的情況下，有以下等式：

$heta_{p}(w)=max_{alpha,eta:alpha_{i}geq 0}L(w,alpha,eta)$

其中下標P表示「primal」，表示原始問題，那麼 $heta_{p}(w)$ 就變成了只有 $w$ 的函數，我們從 $w$ 是否滿足約束條件來分析這個函數：

如果 $w$ violate constraint, 那麼存在以下兩種情況：

$g_{i}(w)>0$ ，那麼令 $alpha_{i} ightarrow +infty$ ，則 $heta_{p}(w)=infty$
$h_{i}(w) e 0$ ，很容易取得 $eta_{i}$ 使得 $heta_{p}(w)=infty$

如果w滿足約束，那麼 $heta_{p}(w)=f(w)$

因此， $heta_{p}$ 對於所有滿足約束的 $w$ 所得到的結果與我們的目標函數相同，並且如果約束不滿足則取正無窮，因此，我們考慮以下最小化問題，與我們的原問題相同，並且解也相同：

$min_{w} heta_{p}(w)=min_{w}max_{alpha,eta:alpha_{i}geq 0}L(w,alpha,eta)$

假設原始問題的最優解為 $p^{*}=min_{w} heta_{p}(w)$

原始問題討論就到這裡，做一個總結：通過拉格朗日這位大神的辦法重新定義一個無約束問題（大家都喜歡無拘無束），這個無約束問題等價於原來的約束優化問題，從而將約束問題無約束化！

2. Dual Problem

現在我們定義原始問題的對偶問題，稍微與上述不同，定義：

$heta_{D}(alpha,eta)=min_{w}L(w,alpha,eta)$

其中 $D$ 表示「Dual」，在 $heta_{p}(w)$ 中我們針對 $alpha,eta$ 進行優化，而這裡我們針對 $w$ 進行優化，當 $w$ 確定之後，最小值就只與 $alpha,eta$ 相關，因此是一個關於 $alpha,eta$ 相關的函數。

我們給出dual optimization problem：

$max_{alpha,eta:alpha_{i}geq 0} heta_{D}(alpha,eta)=max_{alpha,eta:alpha_{i}geq 0}min_{w}L(w,alpha,eta)$

這與我們的原始問題相同，除了max和min的順序進行了調換，我們將對偶問題的最優值定義為： $d^{*}=max_{alpha,eta:alpha_{i}geq0} heta_{D}(alpha,eta)$

3. dual problem 與 primal problem的關係

定理：如果原始問題和對偶問題都有最優值，那麼其最優解滿足：

$d^{*}=max_{alpha,eta:alpha_{i}geq 0} heta_{D}(alpha,eta)leq min_{w} heta_{p}(w) =p^{*}$

證明：對任意的 $alpha,eta,w$ ，有

$heta_{D}(alpha,eta)=min_{w}L(w,alpha,eta)leq L(w,alpha,eta)leq max_{alpha,eta:alpha_{i}geq 0}L(w,alpha,eta)= heta_{P}(w)$

即 $heta_{D}(alpha,eta)le heta_{P}(w)$

由於原始問題和對偶問題都有最優解，因此

$d^{*}=max_{alpha,eta:alpha_{i}geq 0} heta_{D}(alpha,eta)leq min_{w} heta_{p}(w) =p^{*}$

也就是說原始問題的最優值不小於對偶問題的最優值，到那時我們要通過對偶問題求解原始問題，就必須使得原始問題的最優解與對偶問題的最優解相等，於是可以得到以下推論。

推論：假設 $w^{*}$ 是原始問題的可行解， $alpha^{*},eta^{*}$ 是對偶問題的可行解，如果 $d^{*}=p^{*}$ ，那麼 $w^{*}$ 是原始問題的最優解， $alpha^{*},eta^{*}$ 是對偶問題的最優解。

所以當原始問題和對偶問題的最優值相等時，可以用求解對偶問題來求解原始問題，因為對偶問題求解比直接求解原始問題更為簡單，但是原始問題滿足什麼樣的條件才能使得 $d^{*}=p^{*}$ 呢？這就是KKT條件。

4. KKT條件

定理1：對於原始問題和對偶問題，假設 $f(x),g_{i}(x)$ 是convex function，並且 $h_{i}(x)$ 是affine(仿射函數, 即由一階多項式構成的函數，f(x)=Ax + b, A是矩陣,x,b是向量)，並且假設不等式約束 $g_{i}(x)$ 是嚴格可行的，即存在 $w$ 滿足 $g_{i}(x)<0,i=1,...,k.$ ,則存在 $w^{*},alpha^{*},eta^{*}$ 使得 $w^{*}$ 是原始問題的最優解， $alpha^{*},eta^{*}$ 是對偶問題的最優解，並且 $d^{*}=p^{*}=L(w^{*},alpha^{*},eta^{*})$ 。

上述定理1說明了最優解存在，那麼下面的定理2來說明什麼樣的解是最優解，即滿足KTT條件。

定理2是KTT條件，用來說明什麼樣的解是最優解

定理2：對於原始問題和對偶問題，假設 $f(x),g_{i}(x)$ 是convex function，並且 $h_{i}(x)$ 是affine(仿射函數, 即由一階多項式構成的函數，f(x)=Ax + b, A是矩陣,x,b是向量)，並且假設不等式約束 $g_{i}(x)$ 是嚴格可行的，即存在 $w$ 滿足 $g_{i}(x)<0,i=1,...,k.$ ,則存在 $w^{*},alpha^{*},eta^{*}$ 分別是原始問題和對偶問題的最優解的充分必要條件是 $w^{*},alpha^{*},eta^{*}$ 滿足以下條件

其中的式5稱為KTT dual complementarity condition，這意味著如果 $alpha_{i}>0$ ，則 $g_{i}(w^{*})=0$ ;這意味著不等式約束變成了等式約束，後面這對於解釋SVM只有少量支持向量是很重要的。同時在隨後的SMO演算法中，KTT dual complementarity condition也給我們收斂性測試。

5. 一些注意

$heta_{p}(w)=max_{alpha,eta:alpha_{i}geq 0}L(w,alpha,eta)$ 這裡將 $w$ 看作變數固定下來，然後求取 $alpha,eta$ 來使得 $L(w,alpha,eta)$ 因。此 $heta_{p}(w)$ 是只包含了 $w$ 的函數；同樣 $heta_{D}(alpha,eta)=min_{w}L(w,alpha,eta)$ 是只包含了 $alpha,eta$ 的函數

例如假設 $L(w,alpha,eta)=w^{2}+alpha w+eta w$ ，那麼 $heta_{D}(alpha,eta)=min_{w}L(w,alpha,eta)$ 就等於求解二次方程，得到的 $heta_{D}(alpha,eta)=frac{4eta-alpha^{2}}{4}$