[機器學習必知必會]從無約束優(yōu)化到拉格朗日法

了解一些簡單的數(shù)學概念

首先看一個二元函數(shù)（再復雜一點的函數(shù)就很難直觀地呈現(xiàn)出來）的三維圖像和對應的等高線似袁，其中函數(shù)表達式為 $z=x^2+y^2$ ：

二元函數(shù)的三維圖像及等高線

從導數(shù)到偏導數(shù)

對于一個一元函數(shù)而言，導數(shù)的定義想必大家都很清楚，具體的表達式為：
$f'(x)=\lim_{\triangle x\rightarrow0}\frac{f(x+\triangle x)-f(x)}{\triangle x}=\lim_{\triangle x \rightarrow 0}\frac{f(x)-f(x-\triangle x)}{\triangle x}$

一元函數(shù)中只有一個自變量屹耐，因此在某個點的導數(shù)即函數(shù)在該點的斜率期奔，高中物理在路程-時間問題中賦予導數(shù)的含義為瞬時速度。

對于一個二元函數(shù) $f(x,y)$ 仿畸，偏導數(shù)即固定其他變量時的函數(shù)變化率食棕，也就是沿著坐標軸正方向的變化率：
$f_x(x,y) = \lim_{\triangle x \rightarrow 0} \frac{f(x+\triangle x,y)-f(x,y)}{\triangle x}$
$f_y(x,y) = \lim_{\triangle y \rightarrow 0} \frac{f(x, y+\triangle y)-f(x,y)}{\triangle y}$

方向導數(shù)

這里引入偏導數(shù)的原因是因為在多元函數(shù)中朗和，經(jīng)過函數(shù)某一點的切線有無數(shù)條，這些切線共同組成切平面簿晓。借助于“基向量”的思想眶拉，我們通過兩個偏導數(shù)表示出經(jīng)過該點的任意方向切線的導數(shù)，這也就是方向導數(shù)憔儿。

現(xiàn)在我們放開對所有變量的限制忆植，記點 $(x,y)$ 為二元函數(shù)上一點，自該點引一條射線 $l$ , 在該點射線方向鄰域內存在一點 $(x+\triangle x,y+\triangle y)$ 谒臼，那么函數(shù)沿著 $l$ 方向的方向導數(shù)為：
$\frac{\partial y}{\partial l} = \lim_{\rho\rightarrow 0} \frac{f(x+\triangle x, y+\triangle x)-f(x,y)}{\rho},\rho = \sqrt{(\triangle x)^2 + (\triangle y)^2}$

方向導數(shù)與偏導數(shù)

前面提到方向導數(shù)就是二元函數(shù) $f(x,y)$ 在 $(x,y)$ 點處沿著任一方向的函數(shù)的變化率朝刊，而偏導數(shù)反映了函數(shù)沿著坐標軸方向上的變化率。

借助“基向量”的思想蜈缤，我們可以用偏導數(shù)表示任意方向的方向導數(shù)：
$\frac{\partial f}{\partial l}=\frac{\partial f}{\partial x}cos\alpha + \frac{\partial f}{\partial y} cos\beta$

梯度

一元函數(shù)在一個點只有一個斜率拾氓，二元函數(shù)在一個點處有一個切平面。在無約束最優(yōu)化問題中底哥，我們希望找到函數(shù)下降速度最快的方向咙鞍，然后不斷逼近函數(shù)的最小值點，如下圖所示：

梯度的直觀理解

一言以蔽之趾徽，梯度方向就是函數(shù)值下降最快的方向续滋。
注：為防止不同教材知識的混淆，本篇不明確區(qū)分梯度方向與負梯度方向附较，重在理解拉格朗日乘子法的思想即可吃粒，具體推導可找專業(yè)的數(shù)學資料。

下界與下確界

圖源：https://zhuanlan.zhihu.com/p/23859974

舉個例子拒课，當我們迭代求解函數(shù)

f(x)

的最小值時徐勃，所有迭代值構成一個不斷遞減的有序數(shù)列

\{x^{(k)}\}

。

如果我們能找到一個實數(shù)早像，它比這個數(shù)列中所有的數(shù)都要小僻肖，那我們就可以稱它為這個數(shù)列的下界。
不難理解卢鹦，一個有界數(shù)列可以找到無數(shù)個不同的下界臀脏，而最大的下界也是下確界。

無約束問題引入

前面提到的梯度下降法和牛頓法都是求解無約束最優(yōu)化問題的常用方法冀自，無約束的最優(yōu)化問題可以抽象為：
$\min _{x \in R^n} f(x)$
當函數(shù)滿足處處一階可導時揉稚，極值點存在的必要條件是該點的一階偏導數(shù)為0，高數(shù)中對于簡單的問題我們可以直接解出滿足 $\frac{df(x)}{dx}$ 為零的所有 $x$ 熬粗，并代入函數(shù)判斷他是否為極值點搀玖。

image.png

當函數(shù)復雜到我們無法輕易求出可能的極值點時，我們通過構造初始值 $x^{(0)}$ 和遞推公式去不斷逼近函數(shù)的極值點驻呐，比較典型的算法包括梯度下降法灌诅、坐標下降法和擬牛頓法等芳来。

梯度下降法和擬牛頓法回顧

假設目標函數(shù)為線性回歸的目標函數(shù)：
$h_\theta(x^{(i)})=\sum_{j=1}^{n} \theta_jx_j^{(i)}$
$J(\theta) = \frac{1}{2m}(y^{(i)}-h_\theta(x^{(i)}))^2$
其中自變量維度為 $m$ ,樣本數(shù)為 $n$ , $x_j^{(i)}$ 表示第 $i$ 個樣本的第 $j$ 個自變量的取值。
接下來我們需要做的就是找到最佳的參數(shù)組合使得目標函數(shù)值達到最小猜拾。

批量梯度下降法

以批量梯度下降法（BGD）為例即舌，每一步我們都沿著目標函數(shù)的負梯度方向更新參數(shù)值：
$\frac{\partial J(\theta)}{\partial \theta_j}=-\frac{1}{m}\sum_{i=1}{m}(y^{(i)})-h_\theta(x^{(i)}))x_j^{(i)}$
$\theta_j' = \theta_j+\frac{1}{m}\sum_{i=1}^{m}(y^{(i)}-h_\theta (x^{(i)}))$

牛頓法

牛頓法是求解函數(shù)值等于0的自變量取值的一種迭代算法，因此我們可以使用牛頓法求解滿足函數(shù)一階導為0的參數(shù)值挎袜。
迭代公式如下所示顽聂，具體推導過程可以在牛頓法那篇文章中看。
$\theta'=\theta-H^{-1}_kg_k$

從無約束最優(yōu)化到有約束最優(yōu)化

前面我們討論的都是無約束情況下的最優(yōu)化盯仪，根據(jù)極值的必要條件（一階導為0）芜飘，我們可以通過構造數(shù)列不斷逼近最優(yōu)值。但是有很多實際問題是有約束的磨总，拉格朗日乘子法就是解決有約束最優(yōu)化的一種常用方法。

直觀理解

image

上圖中的多個黑色圓圈是二元函數(shù)

f(x,y)

投影在平面上的等高線（即同一條線代表函數(shù)值相同）笼沥，藍色的箭頭代表函數(shù)的梯度方向（即函數(shù)值下降速度最快的方向）蚪燕。如果在沒有約束的情況下，我們應該直接沿著梯度方向找到使函數(shù)值不再下降的最小值奔浅，現(xiàn)在我們給函數(shù)加上了約束條件（即紅色線馆纳，代表著

(x,y)

的取值要落在紅線上）。

現(xiàn)在問題轉化為我們需要在紅線上找到使得函數(shù)值最小化的 $(x,y)$ 的取值汹桦。

由于函數(shù)的等高線是密集的鲁驶，因此我們只需要在滿足函數(shù)等高線和約束曲線相切的點集合中尋找可能的極值點。（相切是極值點的必要非充分條件）

用數(shù)學語言描述

由于在極值點處函數(shù)等高線和約束函數(shù)的梯度都與切平面垂直舞骆，從而他們的梯度方向在同一條直線上钥弯，即：

對于約束曲面上的任意點 $(x,y)$ ，該點的梯度 $\triangledown h(x,y)$ 正交于約束曲面
在最優(yōu)點處督禽，目標函數(shù)在該點的梯度 $\triangledown f(x,y)$ 正交于約束曲面
$\triangledown f(x,y) = \lambda \triangledown h(x,y)$
我們定義拉格朗日函數(shù)如下脆霎，其中 $\lambda$ 稱為拉格朗日乘子：
$L(x,y,\lambda) = f(x,y) + \lambda h(x,y)$
我們將拉格朗日函數(shù)求偏導之后就得到上述的梯度公式，因此我們可以將原約束優(yōu)化問題轉化為對拉格朗日函數(shù) $L(x,y,\lambda)$ 的無約束優(yōu)化問題狈惫。

從等式約束到非等式約束

下圖展示了拉格朗日乘子法的幾何含義：在左邊的等式約束( $g(x)=0$ )下和右邊的不等式約束 $g(x)\leq 0$ 下最小化目標函數(shù) $f(x,y)$ 睛蛛。其中紅色曲線表示 $g(x)=0$ 圍成的曲面。

image

不等于約束

g(x)\leq 0

的情形中胧谈，最優(yōu)點

x^*

要么出現(xiàn)在邊界

g(x) = 0

上忆肾，要么出現(xiàn)在區(qū)域

g(x)<0

中：

對于 $g(x)<0$ 的情形，因為 $\triangledown f(x)$ 方向向里菱肖，因此約束條件 $g(x)\leq 0$ 不起作用客冈，我們只需要通過條件 $\triangledown f(x) = 0$ 求得可能的極值即可。
$g(x)=0$ 的約束類似于前面提到的等式約束蔑滓，但是 $\triangledown f(x^*)$ 的方向和 $\triangledown g(x^*)$ 必須相反郊酒，即存在常數(shù) $\lambda > 0$ 使得 $\triangledown f(x^*) + \lambda \triangledown g(x^*)=0$

當最優(yōu)值落在 $g(x)<0$ 區(qū)域時遇绞，約束條件件 $g(x)\leq 0$ 不起作用，因此我們令約束條件的乘子 $\lambda =0$ 燎窘；當最優(yōu)值落在 $g(x)=0$ 邊界上時摹闽， $\lambda g(x)$ 自然等于0『纸。考慮到這兩種情形付鹿，我們可以推出 $\lambda g(x)=0$ 。

因此蚜迅，拉格朗日乘子法可以寫成如下的等價形式舵匾，括號的條件也叫做KKT條件。
$L(x,\lambda) = f(x) + \lambda g(x)$
$\left\{\begin{matrix} g(x)\leq 0\\ \lambda \ge1 0\\ \lambda g(x) = 0 \end{matrix}\right.$

拉格朗日乘子法的一般寫法

考慮具有 $m$ 個等式約束和 $n$ 個不等式約束的一般優(yōu)化情形：
$\min_{x} f(x)$
$\left\{\begin{matrix} h_i(x) = 0 \quad (i=1,2,...,m)\\ g_j(x) \leq 0 \quad (j=1,2,...,n) \end{matrix}\right.$

引入拉格朗日乘子 $\lambda = (\lambda_1, \lambda_2,...,\lambda_m)^T$ 和 $\mu=(\mu_1,\mu_2,...,\mu_n)^T$ 谁不，對應的拉格朗日函數(shù)為：
$L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m} \lambda_i h_i(x)+\sum_{j=1}^{n}\mu_jg_j(x)$
不等式問題對應的KKT條件為：
$\left\{\begin{matrix} g_j(x) \leq 0 \\ \mu_j \geq 0\\ \mu_j g_j(x) = 0 \end{matrix}\right.$

拉格朗日對偶性

推導出對偶問題

主問題：
$\min_x f(x)$
$\left\{\begin{matrix} h_i(x) = 0 \quad (i=1,2,...,m)\\ g_j(x) \leq 0 \quad (j=1,2,...,n) \end{matrix}\right.$
對應的拉格朗日函數(shù)為：
$\min_{x\in\mathbb{D},\mu_i\geq 0,\lambda} L(x,\lambda,\mu)=\min_{x\in\mathbb{D},\mu_i\geq 0,\lambda}f(x)+\sum_{i=1}^{m} \lambda_i h_i(x)+\sum_{j=1}^{n}\mu_jg_j(x)$
其中 $\mathbb{D}$ 為主問題中基于等式和不等式約束的可行域坐梯，那么對于任意的 $\mu\geq 0, \lambda$ ，都有：
$\sum_{i=1}^{m}\lambda_ih_i(x)+\sum_{j=1}^{n}\mu_j g_j(x) \leq0$
我們通過對偶函數(shù)給出主問題最優(yōu)值的下界
$\Gamma(\lambda,\mu)=\inf_{x\in \mathbb{D}}L(x,\lambda,\mu)=\inf_{x\in \mathbb{D}} \bigg( f(x)+\sum_{i=1}^{m}\lambda_ih_i(x)+\sum_{j=1}^{n}\mu_j g_j(x) \bigg)$
假設主問題的最優(yōu)點為 $x^*$ 刹帕，對應的最優(yōu)值為 $p^*$ 吵血，則對于任意的 $\mu \geq 0$ 、 $\lambda$ 和可行域內的任一點 $\tilde{x} \in \mathbb{D}$ 都有：
$\Gamma(\lambda, \mu)=\inf_{x\in \mathbb{D}}L(x,\lambda,\mu) \leq L(\tilde{x},\lambda,\mu) \leq f(\tilde{x})$
即對偶函數(shù)小于主問題中的每一個函數(shù)值（下界的定義）偷溺，給出了主問題的一個下界蹋辅，并且這個下界的值取決于 $\mu, \lambda$ 的值。一個很自然的問題是：基于對偶函數(shù)能獲得的最好下界是什么（下確界的思想）挫掏，這就引入了對偶問題：
$\max_{\lambda, \mu \geq0} \Gamma(\lambda,\mu)$

為什么要引入對偶問題

無論主問題的凸性如何侦另，對偶問題始終是凸優(yōu)化問題
凸優(yōu)化問題的研究較為成熟，當一個具體被歸為一個凸優(yōu)化問題尉共，基本可以確定該問題是可被求解的

弱對偶性與強對偶性

假設主問題的最優(yōu)值 $p^*$ 褒傅，對偶問題的最優(yōu)值為 $d^*$ ，根據(jù)下界的定義爸邢，顯然有 $d^*\leq p^*$ 樊卓。

弱對偶性： $d^*\leq p^*$
強對偶性： $d^* = p^*$

在強對偶性成立時，將拉格朗日函數(shù)分別對原變量和對偶變量求導杠河，再令導數(shù)等于零碌尔，即可得到原變量與對偶變量的數(shù)值關系。于是券敌，對偶問題解決了唾戚，主問題也就解決了。

Reference

[1]https://www.cnblogs.com/lyr2015/p/9010532.html
[2]https://www.cnblogs.com/xinchen1111/p/8804858.html
[3]https://puui.qpic.cn/fans_admin/0/3_1692378290_1568465189769/0
[4]《統(tǒng)計學習方法》
[5]《機器學習》

最后編輯于：2022.03.20 17:40:51

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

人面猴
序言：七十年代末待诅，一起剝皮案震驚了整個濱河市叹坦，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌卑雁，老刑警劉巖募书，帶你破解...
沈念sama閱讀 221,576評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件绪囱，死亡現(xiàn)場離奇詭異，居然都是意外死亡莹捡，警方通過查閱死者的電腦和手機鬼吵，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,515評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來篮赢，“玉大人齿椅，你說我怎么就攤上這事∑羝” “怎么了涣脚？”我有些...
開封第一講書人閱讀 168,017評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長寥茫。經(jīng)常有香客問我遣蚀，道長，這世上最難降的妖魔是什么纱耻？我笑而不...
開封第一講書人閱讀 59,626評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任妙同，我火速辦了婚禮，結果婚禮上膝迎，老公的妹妹穿的比我還像新娘。我一直安慰自己胰耗，他們只是感情好限次，可當我...
茶點故事閱讀 68,625評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著柴灯，像睡著了一般卖漫。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上赠群，一...
開封第一講書人閱讀 52,255評論 1贊 308
城市分裂傳說
那天羊始，我揣著相機與錄音，去河邊找鬼查描。笑死突委，一個胖子當著我的面吹牛，可吹牛的內容都是我干的冬三。我是一名探鬼主播匀油，決...
沈念sama閱讀 40,825評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼勾笆！你這毒婦竟也來了敌蚜？” 一聲冷哼從身側響起，我...
開封第一講書人閱讀 39,729評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤窝爪，失蹤者是張志新（化名）和其女友劉穎弛车，沒想到半個月后齐媒，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,271評論 1贊 320
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡纷跛，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 38,363評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年喻括，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片忽舟。...
茶點故事閱讀 40,498評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡双妨，死狀恐怖，靈堂內的尸體忽然破棺而出叮阅，到底是詐尸還是另有隱情刁品，我是刑警寧澤，帶...
沈念sama閱讀 36,183評論 5贊 350
?日本核電站爆炸內幕
正文年R本政府宣布浩姥，位于F島的核電站挑随，受9級特大地震影響，放射性物質發(fā)生泄漏勒叠。R本人自食惡果不足惜兜挨，卻給世界環(huán)境...
茶點故事閱讀 41,867評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望眯分。院中可真熱鬧拌汇，春花似錦、人聲如沸弊决。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,338評論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽飘诗。三九已至与倡，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間昆稿，已是汗流浹背纺座。一陣腳步聲響...
開封第一講書人閱讀 33,458評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留溉潭，地道東北人净响。一個月前我還...
沈念sama閱讀 48,906評論 3贊 376
代替公主和親
正文我出身青樓，卻偏偏與公主長得像喳瓣，于是被迫代替她去往敵國和親别惦。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 45,507評論 2贊 359