簡單易懂的拉格朗日對偶法和KKT條件

問題描述

假設(shè)要解決的優(yōu)化問題為：
$min f_{0}(x) \tag{1}$
約束條件為 $f_{i}(x) <= 0 \quad {\forall}i \in 1,2,3...,m\tag{2}$

問題的簡單改寫

我們現(xiàn)在需要用一個函數(shù)來寫出上面問題的等價問題。也就是要把約束條件跟目標(biāo)函數(shù)寫進(jìn)一個函數(shù)中榛臼，把這個函數(shù)記作 $J(x)$ ,那么 $J(x)$ 可以寫作：

$\begin{aligned} J(x) =& \begin{cases} f_{0}(x), \quad & if \quad f_{i}(x) \leq 0 \quad \forall i \\ +\infty, & otherwise \\ \end{cases} \\ =& f_{0}(x) + \sum_{i} I[f_{i}(x)] \\ \end{aligned}$

這里的 $I[u]$ 是個無窮階躍函數(shù),其表達(dá)式為:
$\begin{align} I(u) =& \begin{cases} 0, \quad &if \quad u \leq 0 \tag{5} \\ +\infty, & otherwise\ \end{cases} \end{align}$

如果 $f_{i}(x)$ 大于0, 由于階躍函數(shù) $I[f_{i}(x)]$ 取值為正無窮, 那么函數(shù)不可能在這時取到極小值. 如果 $f_{i}(x)$ 小于等于0, 那么 $I[f_{i}(x)]$ 值為0,求 $J(x)$ 最小值就是求 $f_{0}(x)$ 的最小值.注意到此時的 $f_{i}(x)$ 小于等于0,因此完全和原問題等價.

至此已經(jīng)把求原問題最小值成功寫成求該函數(shù)最小值了.

改寫成連續(xù)可導(dǎo)形式

不難發(fā)現(xiàn), 這個函數(shù)不是連續(xù)可導(dǎo)的函數(shù), 因此不好進(jìn)行極值的求解 (連續(xù)可導(dǎo)函數(shù)可通過讓導(dǎo)數(shù)值為0來求極值).我們需要進(jìn)一步把函數(shù)轉(zhuǎn)化成一個連續(xù)函數(shù)的等價形式.

不連續(xù)的原因是函數(shù) $I(u)$ 造成的,如何去改寫 $I(u)$ 呢?

一個最簡單的方法把 $I(u)$ 給松弛成 $\lambda u$ , $\lambda \geq 0\$ .假設(shè) $\lambda = 0.6$ 如下圖所示:

無窮階躍函數(shù)I(u)和線性松弛λu

顯然,

\lambda u

是

I(u)

的一個下界,這個結(jié)論對于任意

\lambda \geq 0\

都是成立的.

現(xiàn)在可以把 $J(x)$ 中的 $I(u)$ 替換為 $\lambda u$ ,新的函數(shù)由于引入的新的參數(shù) $\lambda$ ,因此不能用一個字母來表示,于是記作:
$L(x,\lambda) = f_{0}(x) + \sum_{i} \lambda_{i}f_{i}(x) \tag{6}$
那么這個函數(shù)該如何跟之前的 $J(x)$ 等價呢?
我們注意到如果 $f_{i}(x)>0$ 時 $\lambda_{i}f_{i}(x)$ 取值為 $+\infty$ , $f_{i}(x)\leq0$ 時 $\lambda_{i}f_{i}(x)$ 取值為 $0$ , 那么 $\lambda_{i}f_{i}(x)$ 的效果將跟 $I[f_{i}(x)]$ 完全相同. 要實(shí)現(xiàn)這一步,只需要把 $L(x,\lambda)$ 寫成 $\underset{\lambda}{max} L(x,\lambda)$ 即可.也就是把(6)式中的 $\lambda$ 看作變量, $x$ 看作常量求(6)式的最大值. 如果 $f_{i}(x)>0$ 那么 $\lambda$ 取值為 $+\infty$ 時 $L(\lambda)$ 最大,如果 $f_{i}(x)\leq0$ , 那么 $\lambda_{i}f_{i}(x)$ 的值 $\leq 0$ , 當(dāng)且僅當(dāng) $\lambda = 0$ 時取到 $0$ ,才能使 $L(\lambda)$ 最大.因此, $J(x)$ 的等價函數(shù)為 $\underset{\lambda}{max} L(x,\lambda)$ . 原問題等價為 $min J(x)$ 也就是 $\underset{x}{min}{\,} \underset{\lambda}{max} L(x,\lambda)$ . 其中 $\underset{x}{min}$ 表示把 $x$ 看作變量求函數(shù)的最小值.

對偶問題

注意到求 $\underset{x}{min}{\,}\underset{\lambda}{max} L(x,\lambda)$ 與求原問題等價, 都不好進(jìn)行求解. 但是,如果我們考慮調(diào)換求極值的順序, 也就是先把 $x$ 看作變量求函數(shù)的最小值, 再把 $\lambda$ 看作變量求函數(shù)的最大值. 那么問題就變成:
$\underset{\lambda}{max}{\,}\underset{x}{min} L(x,\lambda) = \underset{\lambda}{max} {\,}g(\lambda) \tag{7}$
這個問題跟原問題是不等價的,它被稱為原問題的對偶問題. 雖然不等價, 但是對偶問題的最優(yōu)值是原問題最優(yōu)值的一個下界,證明如下:

$L(x, \lambda) \leq J(x) \forall \lambda \geq 0$

$\Rightarrow \min _{x} L(x, \lambda) = g(\lambda) \leq \min _{x} J(x)=: p^{\star}$

$\Rightarrow d^{\star} =\max _{\lambda} g(\lambda) \leq p^{\star} \tag{8}$

第一項(xiàng)是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda%20u%20%5Cleq%20I%5Bu%5D" alt="\lambda u \leq I[u]" mathimg="1">, 第二項(xiàng)就是把 $x$ 看作變量同時取極小值, $p^{\star}$ 是原問題的最優(yōu)值. 第三項(xiàng)是因?yàn)橛傻诙?xiàng)可知 $g(\lambda)$ 的所有值都小于等于 $p^{\star}$ ,因此, $g(\lambda)$ 的最大值, 也就是對偶問題的最優(yōu)值 $d^{\star}$ 是小于等于 $p^{\star}$ 的.所以對偶問題的最優(yōu)值是原問題最優(yōu)值的一個下界.
$g(\lambda)$ 根據(jù)凸優(yōu)化的相關(guān)理論是一個凹函數(shù), 因此容易求解.具體證明可參考:https://github.com/ShiqinHuo/Numerical-Optimization-Books/blob/master/Convex%20Optimization%20Boyd.pdf.

當(dāng)問題具有強(qiáng)對偶性時, $d^{\star} = p^{\star}$ . 若 $d^{\star} < p^{\star}$ 則問題具有弱對偶性.一般來說,幾乎所有的凸優(yōu)化問題都滿足強(qiáng)對偶性.比如SVM中, 它的損失函數(shù)就是凸函數(shù), 我們幾乎就能斷定它是一個強(qiáng)對偶的問題.

KKT條件

對于一個沒有約束的凸優(yōu)化問題, 只需要對函數(shù)的梯度求導(dǎo)并令其為0即可. 對于由約束的凸優(yōu)化問題而言, 它的最優(yōu)解一定滿足KKT條件. 第一個條件如下所示:
$\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x} f_{i}\left(x^{\star}\right)=0 \tag{9}$
這個條件可以解釋為目標(biāo)函數(shù)和約束函數(shù)的梯度必須平行且相反, 如下圖所示:

假設(shè)目標(biāo)函數(shù)為

f_{0}(x)=(x_1-1.1)^{2}+(x_2+1.1)^{2}

耳峦，不等值約束為

f_{1}(x)=x_{1}^2+x_{2}^{2}?1

,如圖所示, 最小值點(diǎn)取在

f_{0}(x)

梯度的反方向和約束條件

f_{1}(x)

梯度的方向上. 值得注意的是,如果

f_{0}(x)

最小值落在可行域內(nèi),約束將不起作用,

\lambda

取值為

0

,上面的等式依然成立,求極小值的方法就是直接令

f_{0}(x)

梯度為

0

根據(jù)(8)式我們有:
$f_{0}\left(x^{\star}\right)=g\left(\lambda^{\star}\right)=\min _{x} L\left(x, \lambda^{\star}\right) = f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) \leq f_{0}\left(x^{\star}\right) \tag{10}$

最右邊的不等式成立的原因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda_%7Bi%7D%20%5Cgeq%200%2Cf_%7Bi%7D(x%5E%7B%5Cstar%7D)%20%5Cleq%200" alt="\lambda_{i} \geq 0,f_{i}(x^{\star}) \leq 0" mathimg="1">.(10)式成立的條件只有取等號, 因此我們得到了第二個KKT條件:
$\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i\tag{11}$
綜上, 在不等式約束下凸優(yōu)化問題的所有KKT條件包括:
$\lambda_{i} \geq 0$

$f_{i}(x^{\star}) \leq 0$

$\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x}f_{i}\left(x^{\star}\right) =0$

$\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i$

參考資料

[1] David Knowles,Lagrangian Duality for Dummies,November 13, 2010
[2] 瑞典皇家理工學(xué)院（KTH）“統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)”課程的KKT課件：http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf

最后編輯于：2021.05.29 22:27:23

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末恩静，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子蹲坷，更是在濱河造成了極大的恐慌蜕企，老刑警劉巖，帶你破解...
沈念sama閱讀 212,383評論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件冠句，死亡現(xiàn)場離奇詭異，居然都是意外死亡幸乒，警方通過查閱死者的電腦和手機(jī)懦底，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,522評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來罕扎，“玉大人聚唐，你說我怎么就攤上這事∏徽伲” “怎么了杆查？”我有些...
開封第一講書人閱讀 157,852評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長臀蛛。經(jīng)常有香客問我亲桦，道長，這世上最難降的妖魔是什么浊仆？我笑而不...
開封第一講書人閱讀 56,621評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任客峭，我火速辦了婚禮，結(jié)果婚禮上抡柿，老公的妹妹穿的比我還像新娘舔琅。我一直安慰自己，他們只是感情好洲劣，可當(dāng)我...
茶點(diǎn)故事閱讀 65,741評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布备蚓。她就那樣靜靜地躺著课蔬，像睡著了一般。火紅的嫁衣襯著肌膚如雪郊尝。梳的紋絲不亂的頭發(fā)上二跋，一...
開封第一講書人閱讀 49,929評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音虚循，去河邊找鬼同欠。笑死，一個胖子當(dāng)著我的面吹牛横缔，可吹牛的內(nèi)容都是我干的铺遂。我是一名探鬼主播，決...
沈念sama閱讀 39,076評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼茎刚，長吁一口氣：“原來是場噩夢啊……” “哼襟锐！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起膛锭，我...
開封第一講書人閱讀 37,803評論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤粮坞，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后初狰，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體莫杈，經(jīng)...
沈念sama閱讀 44,265評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,582評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年奢入，在試婚紗的時候發(fā)現(xiàn)自己被綠了筝闹。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,716評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡腥光，死狀恐怖关顷，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情武福，我是刑警寧澤议双，帶...
沈念sama閱讀 34,395評論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站捉片，受9級特大地震影響平痰，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜界睁，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,039評論 3贊 316
男人毒藥：我在死后第九天來索命
文/蒙蒙一觉增、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧翻斟，春花似錦逾礁、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,798評論 0贊 21
一樁弒父案嘹履，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽腻扇。三九已至，卻和暖如春砾嫉，著一層夾襖步出監(jiān)牢的瞬間幼苛，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,027評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工焕刮，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留舶沿，地道東北人。一個月前我還...
沈念sama閱讀 46,488評論 2贊 361
代替公主和親
正文我出身青樓配并，卻偏偏與公主長得像括荡，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子溉旋，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,612評論 2贊 350