小蜜蜂問答

小蜜蜂問答

學習筆記 - 拉格朗日函式

Kun LU 發表于娛樂2017-05-14

本文僅為個人學習筆記的整理，歡迎指錯。

最最佳化問題通常是指對於給定的某一函式，求其在指定作用域上的全域性最小值。一般情況下，最最佳化問題會碰到以下三種情況：

1，無約束最佳化問題

可以寫為

注意到，粗體

表示的是一個向量（

），下同

對於無約束最最佳化問題，有很多經典的求解方法，參見無約束最最佳化方法 - Orisun - 部落格園

注意到，我們高中常見的求函式最值問題就是無約束最佳化問題（例如

$min (x_1-3)^{2}$

）

2，等式約束最最佳化

可以寫為：

引入拉格朗日乘子（

$\lambda _i\ne 0$

）把問題轉換成拉格朗日函式

$L(x,\lambda)=\left[ f(x) +\sum_{i=1}^{n}\lambda_ih_i(x) \right]$

因為對於任何可行解，有

，所以有

$f(x)=L(x,\lambda )$

，也就是，

$minf(x)=minL(x,\lambda )$

。

求解。對

$L(x,\lambda)$

分別求

$x,\lambda$

的偏導數為零，得到方程組求解極值點，然後從極值點挑出最值點。

令

的偏導為零，使得目標函式和約束函式的法向量共線（梯度共線）。為什麼梯度共線能求到極值？

綠線標出的是約束

的點的軌跡。藍線是

的等高線，箭頭是各個點的梯度。

從圖上可以看到，藍線（

）與綠線相交，意味著肯定還存在其它的等高線（

）在該條等高線的內部或者外部，使得新的等高線與目標函式的交點的值更大或者更小。所以當取到極值時，藍線與綠線相切，而切點的梯度共線。

3，不等式約束最最佳化

可以寫為：

引入拉格朗日乘子（

$\mu _i\geq 0$

），定義上述問題的拉格朗日量（Lagrangian）如下

$L(x,\mu )=\left[ f(x) +\sum_{i=1}^{m}\mu _ig_i(x) \right]$

同時定義拉格朗日對偶函式（Lagrange dual function）如下：

$F(\mu )=inf_x L(x,\mu )=inf_x \left[ f(x)+\sum_{i=1}^{m}\mu _ig_i(x) \right]$

一般情況下，

$L(x,\mu )$

是能取到最小值的，所以

$F(\mu )=inf_x L(x,\mu )=min_x L(x,\mu )$

求解。

當強對偶性成立時

，透過KKT條件求解極值點，然後從極值點挑出最值點。

第一個條件使得目標函式和約束函式的法向量共線（梯度共線）。

最後一個條件稱為互補鬆弛條件（Complementary Slackness Condition）。透過引入這個條件，增加了m個等式約束，使得等式的數量跟變數一樣。

更一般地

，我們把等式約束也加進來，最佳化問題可以寫為：

KKT條件為

如果沒有“不等式”約束條件，即

，KKT條件就是拉格朗日乘數法中極值點滿足的方程組。所以KKT條件是拉格朗日乘數法的推廣，拉格朗日乘數法是KKT條件的特例。

注意到：

KKT條件是強對偶性的必要條件，強對偶性下KKT條件才成立

一般僅用KKT條件來驗證找到的解

當目標函式和約束都是線性時，最佳化問題為我們熟悉的線性規劃（LP）

在線性規劃裡，

$\lambda ,\mu$

表示的是對應約束的影子價格

4，KKT與強對偶性

這裡討論只有不等式約束，並且

強對偶性

的情況

由強對偶性，有

$f(x)=max_\mu L(x,\mu )$

，也就是，

$min_xf(x)=min_x max_\mu L(x,\mu )$

。

原問題目標函式為

$f(x)=max_\mu L(x,\mu )$

，對應的對偶函式為

$F(\mu) =min_x L(x,\mu )$

。

由強對偶性，我們有

$min_x f(x)= max_\mu F(\mu )$

，也就是

$min_x max_\mu L(x,\mu ) = max_\mu min_x L(x,\mu )$

為什麼強對偶下可以得到KKT條件？

首先看梯度共線。

用

表示原問題取得最優值的解，也就是

$f(x^*)=min_x f(x)=min_x max_\mu L(x,\mu )$

。由強對偶性，可得

$max_\mu min_x L(x,\mu )=min_x max_\mu L(x,\mu )=f(x^*)$

。也就是說，

$min_x L(x,\mu )$

在

處取得極值，也就是，偏導數為零。

然後看互補鬆弛條件。

當

時，有

$max_\mu min_x L(x,\mu )=max_\mu\left[ f(x^*) +\sum_{i=1}^{m}\mu _ig_i(x^*) \right]=f(x^*)+max_\mu\left[ \sum_{i=1}^{m}\mu _ig_i(x^*) \right]=f(x^*)$

。

也就是，

$max_\mu\left[ \sum_{i=1}^{m}\mu _ig_i(x^*) \right]=0$

，也就是

$\mu _ig_i(x^*)=0,\forall i=1,...,m$

5，拉格朗日函式與對偶性

對於不等式約束，

一般的，由

$\mu \geq 0,g_i(x)\leq 0$

，有

$f(x)\geq max_\mu L(x,\mu )$

。所以

$min_xf(x)\geq min_x max_\mu L(x,\mu )$

。

而根據拉格朗日對偶函式，有對偶問題為

$max_\mu F(\mu )=max_\mu min_x L(x,\mu )$

。由因為對偶問題是凸最佳化（Slater條件也滿足），根據對偶問題的強對偶性，有

$max_\mu F(\mu )=max_\mu min_x L(x,\mu )= min_x max_\mu L(x,\mu )$

。

所以，有

$min_xf(x)\geq min_x max_\mu L(x,\mu )=max_\mu min_x L(x,\mu )=max_\mu F(\mu )$

。這就是原問題的對偶性。

當原問題有強對偶性時，由

$min_xf(x)=max_\mu F(\mu )$

，有

$min_xf(x)= min_x max_\mu L(x,\mu )$

。

6，參考

無約束最最佳化方法 - Orisun - 部落格園

拉格朗日乘子法和KKT條件 - Orisun - 部落格園

【整理】深入理解拉格朗日乘子法（Lagrange Multiplier）和KKT條件

KKT conditions深入理解拉格朗日乘子法（Lagrange Multiplier）和KKT條件最佳化問題中的對偶性理論

supremum infimum 和maximum minimum 到底有什麼區別？

上一篇：<<見與不見是誰寫的

下一篇：什麼叫奧林匹克?>>

標籤： KKT 對偶性拉格朗條件極值