拉格朗日對偶性(Lagrange duality)
- 2019 年 10 月 3 日
- 筆記
拉格朗日對偶性(Lagrange duality)
1. 從原始問題到對偶問題
對偶性是優化理論中一個重要的部分，帶約束的優化問題是機器學習中經常遇到的問題，這類問題都可以用如下形式表達
[ begin{aligned} min ;; &f(x) \ s.t.;; & g_i(x) le 0 ,;; i=1,cdots, m\ & h_i(x) = 0,;; i=1,cdots,n\ end{aligned} ]
約束條件減少需要求解的空間，但在機器學習中，約束條件往往比較複雜並且較多。因此先計算約束條件再在約束空間中計算最優值非常不方便。於是用廣義拉格朗日函數將帶約束優化問題轉化為無約束優化問題
[ L(x,lambda,eta) = f(x)+sum_i^m lambda_i g_i(x) + sum_i^n eta_i h_i(x) ]
這時，若按照拉格朗日乘數法直接對(x、lambda、eta)求偏導的話，結果對簡化複雜的約束條件沒有益處。我們希望獲取一種能夠優化原問題，又能簡化計算的方法。於是進一步挖掘(lambda、eta)能夠帶來的東西，當我們對廣義拉格朗日函數作關於(lambda、eta) 的最大化時
[ theta_P(x) = underset {lambda ge 0,eta} {max};L(x,lambda,eta) ]
其中，要求(lambda ge 0) ，很容易發現，在這個最大化問題中，若(x) 不滿足原問題中的約束，那麼這個最大化的結果一定是正無窮。例如，(g_i(x)>0) ，在關於(lambda、eta) 最大化時，其係數便會趨於無窮大使得整個式子趨於無窮大。而當(x) 滿足約束時，最大化的結果一定是(f(x)) 。依據這個特性，我們可以將原廣義拉格朗日函數的極小化問題拆解為兩步
[ underset x {min} ;L(x,lambda,eta) = underset x {min} ;theta_P(x) = underset x {min} ;underset {lambda ge 0,eta} {max};L(x,lambda,eta) ]
拆解後的問題$ underset x {min} ;underset {lambda ge 0,eta} {max};L(x,lambda,eta)$ 稱為廣義拉格朗日函數的極小極大問題，它與原問題是完全等價的。在對偶性中，這個問題被稱為原始問題（Primal problem）。
通過原始問題的極小極大問題，可以引出它的對偶問題（Dual problem），其對偶問題就是極小極大問題交換一個位置而已。首先定義
[ theta_D(lambda,eta) = underset {x} {min} L(x,lambda,eta) ]
那麼其對偶問題就是
[ underset {lambda ge 0,eta} {max} ; theta_D(lambda,eta)= underset {lambda ge 0,eta} {max} ;underset {x} {min} L(x,lambda,eta) ]
這個問題是廣義拉格朗日函數的極大極小問題，將其展開為約束最優化問題得到
[ underset {lambda ,eta} {max} ; theta_D(lambda,eta)= underset {lambda ,eta} {max} ;underset {x} {min} L(x,lambda,eta)\ s.t. lambda_i ge 0,;; i= 1,2,cdots,k ]
可以看出兩個函數的變數並不相同，對於原始問題，它的變數是(x)，而對於對偶問題，它的變數是(lambda,;eta) 。並且，這兩個問題並不等價，有時候甚至差的有點多。可以理解為其他國家最厲害的乒乓球隊員，也沒有中國最菜的乒乓球隊員厲害，當然這比喻並不準確。
2. 弱對偶與強對偶
對偶函數可以理解為給原始函數找了一個下界，在原始函數計算困難的時候，可以通過解對偶函數來得到一個近似的值。並且在函數滿足一定條件的時候，對偶函數的解與原始函數的解是等價的。具體來說，對偶 函數(theta_D(lambda,eta)=underset {x} {min} L(x,lambda,eta)) 確定了原始問題的一個下界，即
[ theta_D(lambda,eta) =underset {x} {min} L(x,lambda,eta)le L(x,lambda,eta)le underset {lambda ge 0,eta} {max};L(x,lambda,eta)=theta_P(x) tag{2-a} ]
即
[ theta_D(lambda,eta) le theta_P(x) ]
其中，(theta_d(lambda,eta))看作其他國家乒乓球運動員，(theta_P(x))看作中國乒乓球運動員，那麼其他國家最厲害的也不一定比得上中國最差的。即
[ d^* =underset {lambda ,eta} {max} ; theta_D(lambda,eta)le underset x {min} ;theta_P(x)=p^* tag{2-b} ]
這個性質便是弱對偶性（ weak duality ）。弱對偶性對任何優化問題都成立，這似乎是顯然的，因為這個下界並不嚴格，有時候甚至取到非常小，對近似原問題的解沒多大幫助。既有弱對偶性，那麼便有強對偶性，強對偶性是指
[ d^* = p^* ]
顯然這是一個令人驚喜的性質，這意味著可以通過求解較簡單的對偶問題（因為對偶問題總是一個凸優化問題）來得到原問題的解。不過強對偶性在優化問題中是一個非常高深的問題，對我來說更是如此。因此我只能介紹關於強對偶的兩個條件：嚴格條件和KKT條件。
3. KKT條件
嚴格條件是指原始問題是凸函數，約束條件是仿射函數，若此時不等式約束滿足嚴格條件，即不等號是嚴格不等號，不能取等號，則強對偶性成立。這個條件在SVM中即變成了對任意一個點，都存在超平面能對其正確劃分，也就是數據集是線性可分的。嚴格條件是強對偶性的充分條件，但並不是必要條件。有些不滿足嚴格條件的可能也有強對偶性。
KKT條件是在滿足嚴格條件的情況下，推導出的變數取值的關係，假設原始問題和對偶問題的極值點分別是(x^*)和(lambda^*,eta^*) ，對應的極值分別是(p^*)和(d^*) 。由於滿足強對偶性，有(p^*=d^*) 。將極值點帶入得到
[ d^* = theta_D(lambda^*,eta^*) =underset x {min} L(x,lambda^*,eta^*) tag{3-a} ]
這說明(x^*)是(L(x,lambda^*,eta^*))的一個極值點，那麼(L(x,lambda^*,eta^*))在(x^*)處的梯度為0，即
[ triangledown f(x^*)+sum_i^mlambda_i g_i(x^*) + sum_i^n eta_i h_i(x^*) = 0 tag{3-b} ]
由式((2-a)) ，
[ begin{aligned} d^* =& underset x {min} L(x,lambda^*,eta^*) \ le &L(x^*,lambda^*,eta^*)\ =& f(x^*) + sum_i^m lambda_i g_i(x^*) + sum_i^n eta_i h_i(x^*)\ le & p^* = f(x^*) end{aligned} tag{3-c} ]
由於(p^*=d^*)，因此上式不等號應取到等號，再與式((3-b)) 得
[ sum_i^m lambda_i g_i(x^*) + sum_i^n eta_i h_i(x^*) = 0 tag{3-d} ]
由於注意(x^*)作為該問題的解，是一定滿足(h(x^*) = 0)的，因此
[ lambda_i g_i(x) = 0,;;;i=1,2,cdots,m ]
這個條件叫做互補鬆弛性（complementary slackness）。
其中，(lambda ge 0)稱為對偶可行性。並且它似乎可以從原始問題到對偶問題的極小極大問題中總結出。不過這裡可以有另一種解釋，簡化一下，考慮只有不等式約束的問題
[ begin{aligned} min ;; &f(x) \ s.t.;; & g(x) le 0 \ end{aligned} ]
其中(g(x) le 0)稱為原始可行性，由它確定的區間稱為可行域。假設(x^*)為該問題的解，那麼其位置有兩種情況
-
(1) (g(x^*)<0)時，解在可行域中取得。這時解稱為內部解，約束條件無效，原問題變為無約束問題。
-
(2) (g(x^*)=0)時，解在邊界上取得， 這時解稱為邊界解，約束條件有效。
內部解直接由梯度為0即可解得，這裡主要討論邊界解。
對於(g(x)=0)的約束問題，建立拉格朗日函數
[ L(x,lambda) = f(x) + lambda g(x) ]
因為駐點(x^*)在其上取得，那麼該函數在(x^*)處的梯度為0，即
[ triangledown f(x^*) + lambda triangledown g(x^*) = 0 ]
這裡兩個梯度的方嚮應該是可以確定的，(f(x))的極小值在邊界取到，那麼可行域內部的(f(x))應該都是大於這個極小值的，因此(triangledown f)的方向是可行域內部。而(triangledown g)的方向是可行域外部，因為約束條件是(g(x)le 0)，也就是可行域外部都是(g(x)>0)，所以梯度方向指向函數增加的方向。這說明兩個函數的梯度方向相反，那上面這個等式要成立，(lambda)只能是大於等於0。這就是對偶可行性。
再將其他的條件組合起來，便得到了KKT條件：
[ begin{aligned} triangledown _x L(x^*,lambda^*,eta^*) =0 \ g_i(x^*) le 0\ lambda_i ge 0\ lambda_i g_i(x^*) =0 end{aligned} ]
Reference：
[2] Pattern Recognition and Machine Learning.
[3] 統計學習方法
[4] 支援向量機：Duality
[5] KKT條件
