拉格朗日對偶性

10-12

拉格朗日對偶性

來自專欄機器學習中的數學知識

在約束最優化問題中，常常利用拉格朗日對偶性（Lagrange duality）將原始問題轉換為對偶問題，通過解對偶問題而得到原始問題的解。該方法應用在許多統計學習方法中，例如，最大熵模型與支持向量機。這裡簡要敘述拉格朗日對偶性的主要概念和結果。

1.原始問題

假設 $f(x)$ ， $c_i(x)$ ， $h_j(x)$ 是定義在 $mathbf R^n$ 上的連續可微函數，考慮約束最優化問題

$underset {xin mathbf R^n}{min} f(x)qquad(C.1)\ s.t.quad c_i(x) le 0,i=1,2,dots,kqquad(C.2)\ h_j(x)=0,j=1,2,dots,lqquad(C.3)$

稱此約束最優化問題為原始最優化問題或原始問題。

引進廣義拉格朗日函數（generalized Lagrange function）

$L(x,alpha,eta)=f(x)+sum_{i=1}^{k}alpha_ic_i(x)+sum_{j=1}^{l}eta_jh_j(x)qquad(C.4)$

這裡， $x=(x^{(1)},x^{(2)},dots,x^{(n)})^Tinmathbf R^n$ ， $alpha_i,eta_j$ 是拉格朗日乘子， $alpha_i ge 0$ 。考慮 $x$ 的函數

$heta_P(x)=underset{alpha,eta;alpha_ige0}{max} L(x,alpha,eta)$

這裡，下標 $P$ 表示原始問題。將上式看做 $x$ 的函數，關於這一點，可能有人會有疑問，特此解釋一下：等式右邊可以看做固定 $x$ 的情況下，求關於 $alpha,eta$ 的函數 $L$ 的最大值的問題， $alpha,eta$ 一旦解出， $L$ 的最大值也解出，這個最大值將只和 $x$ 有關，因此記為 $heta_P(x)$ 。

進一步，可以推導出 $heta_P(x)$ 的取值如下

$heta_P(x)= egin{cases} f(x),x滿足原始問題約束\ +infty,otherwise end{cases}qquad(C.7)$

所以如果考慮極小化問題

$underset{x}{min} heta_P(x)=underset{x}{min} underset{alpha,eta;alphage0}{max}L(x,alpha,eta)qquad(C.8)$

它是與原始最優化問題(C.1)~(C.3)等價的，即它們有相同的解。為何等價呢，這是因為當 $x$ 不滿足約束條件時， $heta_P(x)=+infty$ ，顯然不可能成為最小值。

問題 $underset{x}{min} underset{alpha,eta;alphage0}{max}L(x,alpha,eta)$ 稱為廣義拉格朗日函數的極小極大問題，為了方便，定義原始問題的最優值

$p^{*}=underset {x}{min} heta_P(x)qquad(C.9)$

稱為原始問題的值。

2.對偶問題

定義

$heta_D(alpha,eta)=underset{x}{min} L(x,alpha,eta)qquad(C.10)$

再考慮極大化 $heta_D(alpha,eta)=underset{x}{min} L(x,alpha,eta)$ ，即

$underset{alpha.eta;alpha_ige0}{max} heta_D(alpha,eta)=underset{alpha.eta;alpha_ige0}{max} underset{x}{min} L(x,alpha,eta)qquad(C.11)$

問題 $underset{alpha.eta;alpha_ige0}{max} underset{x}{min} L(x,alpha,eta)$ 稱為廣義拉格朗日函數的極大極小問題。

可以將廣義拉格朗日函數的極大極小問題表示為約束最優化問題：

$underset{alpha.eta}{max} heta_D(alpha,eta)=underset{alpha.eta}{max} underset{x}{min} L(x,alpha,eta)qquad(C.12)\ s.t.qquadalpha_ige0,i=1,2,dots,kqquad(C.13)$

稱為原始問題的對偶問題。定義對偶問題的最優值

$d^{*}=underset{alpha,eta;alpha_ige0}{max} heta_D(alpha,eta)qquad(C.14)$

稱為對偶問題的值。

3.原始問題和對偶問題的關係

若原始問題和對偶問題都有最優解，則

$d^{*}le p^{*}qquad(C.15)$

這個性質叫做弱對偶性（weak duality），任何情況下都成立。

與弱對偶性相對應的是強對偶性（strong duality），即滿足

$d^{*}= p^{*}qquad(C.16)$

在滿足強對偶性的情況下，原始問題與對偶問題的解完全等價，可以通過求解對偶問題來得到原始問題的解。強對偶性要成立，須滿足Slater條件或KKT條件，這裡不細述，讀者可自行了解。

對偶問題還有一個十分良好的性質，即無論原始問題是否為凸，對偶問題都是凸優化問題，這會為我們的計算帶來相當的便利。因此，在約束最優化問題中，我們通常將原始問題轉化為對偶問題來求解，即便只滿足弱對偶性，我們也能得到原始問題的一個下界，若運氣好，滿足強對偶性，此時求出的便是原始問題的最優解。

參考文獻

[1] 簡易解說拉格朗日對偶（Lagrange duality）

[2] 拉格朗日對偶性

[3] 如何通俗地講解對偶問題？尤其是拉格朗日對偶lagrangian duality？

[4] 從對偶問題到KKT條件 | Absolute Zero

[5] 對偶理論

[6] http://www.hanlongfei.com/convex/2015/11/05/duality/

以上為本文的全部參考文獻，對原作者表示感謝。

我的足跡

CSDN
GitHub