拉格朗日乘子、KKT條件與對偶問題

1. 拉格朗日算子

1.1 基本流程

假設\boldsymbol{x}=[x_1,x_2,...,x_d]，是一個d維的向量，f(x)和g(x)是定義在實數集上連續(xù)可微的函數，現(xiàn)在需要找一個x^*使得f(x)具有最小值，且g(x) \leq 0。即有：
\begin{align} \min _x f(x) \\ s.t. \ g(x) \leq 0 \tag{1.1} \end{align}
那么，通過拉格朗日乘子法，可以構造出下面的式子：
\begin{align} L(\boldsymbol{x}, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x}) \tag{1.2} \end{align}

令L(\boldsymbol{x},w)的對\boldsymbol{x}的導數為0，求解出x, w的值，那么，\boldsymbol{x}就是函數f(\boldsymbol{x})在附加條件g(\boldsymbol{x})下可能的極值點。

會做題拿分就夠了?。。?/div>

1.2 理解

第一層理解：

在學高數的時候，對拉格朗日的理解僅限于：構造了一個函數L(x,y,\lambda)，對該函數L(x,y,\lambda)求極導，令導數為0，可以算出極大值極小值。

第二層理解：

在進行第二層理解時，需要明白幾個概念：

  • 數學里面，梯度指的是函數變化最快的方向。
  • 梯度跟函數約束曲線是垂直的，既然垂直于約束曲面，就一定垂直于等高線。

具體可以參考這篇文章拉格朗日乘子法。該文比較直觀的介紹了拉格朗日的基本定理，并且從切線、梯度的角度分析了拉格朗日算子。

拉格朗日附體，我是最牛逼的！

2. KKT條件

2.1 一個限制條件的情況

看完這個例子之后，在公式(1.2)可能取到的所有點中，的的確確找到了一個\boldsymbol{x^*}，使得f(\boldsymbol{x})最小且滿足g(\boldsymbol{x}) \leq 0，在這樣的情況下，必然有
\begin{align} \bigtriangledown f(\boldsymbol{x^*}) + w \bigtriangledown g(\boldsymbol{x^*}) = 0 \tag{2.1} \end{align}
而公式(2.1)在某些條件下剛好是公式(1.2)：L(x, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x})對\boldsymbol{x}的偏導數等于0的情況。
\begin{align} \frac{\partial{L(\boldsymbol{x}, w)}}{\partial{\boldsymbol{x}}} = \bigtriangledown f(\boldsymbol{x}) + w \bigtriangledown g(\boldsymbol{x}) \end{align}
那么，某些條件是什么呢？

找到這些條件，就可以嘿嘿嘿

  1. g(\boldsymbol{x}) \leq 0：這個沒什么好說的，限制條件。
  2. w \geq 0：要滿足這個條件，考慮g(\boldsymbol{x})<0和g(\boldsymbol{x})=0兩種情況：

    • 當g(\boldsymbol{x^*})=0時：說明這個點在 g(\boldsymbol{x})=0構成的邊界上，此時必然有\bigtriangledown f(\boldsymbol{x^*})和\bigtriangledown g(\boldsymbol{x^*})平行，但是無法保證他們倆方向和大小相同，因此標量w>0，使得等式(2.1)成立。

      g(x)=0, w>0的情況

    • 當g(\boldsymbol{x^*})<0時：說明這個點在g(\boldsymbol{x})=0構成邊界的內部，此時限制條件g(\boldsymbol{x}) \leq 0就打醬油了，沒卵用，可以直接通過條件\bigtriangledown f(\boldsymbol{x})=0獲得最優(yōu)點，這個時候w=0。

      g(x)<0, w=0的情況

  1. wg(\boldsymbol{x})=0：要加上這個條件的原因是，為了滿足條件2中的兩種情況。
    \begin{align} \left\{\begin{matrix} g(\boldsymbol{x}) \leq 0 \\ w \geq 0 \\ wg(\boldsymbol{x})=0 \end{matrix}\right. \tag{2.2} \end{align}
    所以啊，公式(2.2)就被稱為Karush-Kuhn-Tucker (KKT)條件。

2.2 多個限制條件的情況

一個限制條件說清楚了，那么多當有多個約束條件時，考慮l個等式約束和k個不等式約束。
\begin{align} \min _x f(\boldsymbol{x}) & \\ s.t. \ c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \ h_j(\boldsymbol{x}) = 0 \ & (j=1,2,...,l) \tag{2.3} \end{align}
這個時候，引入拉格朗日算子\boldsymbol{\alpha}=[\alpha_1,\alpha_2,...,\alpha_l]和\boldsymbol{\beta}=[\beta_1,\beta_2,...,\beta_k]，拉格朗日函數為
\begin{align} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = f(\boldsymbol{x}) + \sum_{i=1}^{k} \alpha_i c_i(\boldsymbol{x}) + \sum_{j=1}^{l} \beta_j h_j(\boldsymbol{x}) \tag{2.4} \end{align}
則他們的KKT條件是：
\begin{align} \left\{\begin{matrix} c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \alpha_i \geq 0 \ & (i=1,2,...,k)\\ \alpha_i c_i(\boldsymbol{x})=0\\ h_j(\boldsymbol{x})=0 \end{matrix}\right. \tag{2.5} \end{align}

這有啥難的？瞎幾把套就行

3. 對偶問題

KKT條件中提到，在公式(1.2)可能取到的所有點中，的的確確找到了一個\boldsymbol{x^*}，使得f(\boldsymbol{x})最小且滿足g(\boldsymbol{x}) \leq 0。

但是，如果找不到呢。。。

馬德?。?！

3.1 原始問題

3.1 一個限制條件的情況下

找不到\boldsymbol{x^*}，公式(2.1)就不能成立了，
\begin{align} \bigtriangledown f(\boldsymbol{x^*}) + w \bigtriangledown g(\boldsymbol{x^*}) = 0 \tag{2.1} \end{align}
但是，我要怎么告訴公式(2.1)不能成立?。。?！

找不到\boldsymbol{x^*}，說明存在一個\boldsymbol{x^{fake}}違背了g(\boldsymbol{x}) \leq 0的條件，有g(\boldsymbol{x^{fake}}) > 0，既然這樣的話，在
\begin{align} L(\boldsymbol{x}, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x}) \end{align}
中，我們令w \rightarrow {+\infty}。這樣的話，

  • 若\boldsymbol{x}不違反g(\boldsymbol{x}) \leq 0約束，則\max_w L(\boldsymbol{x}, w) =f(\boldsymbol{x})
  • 若\boldsymbol{x}違反g(\boldsymbol{x}) \leq 0約束，則\max_w L(\boldsymbol{x}, w) = {+\infty}

所以就變成了
\begin{align} \min _x \max_w L(\boldsymbol{x}, w)\tag{3.1} \end{align}

3.2 多個限制條件的情況下

\begin{align} \min _x \max_{\alpha_i, \beta_j; \alpha_i \geq0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\tag{3.2} \end{align}

again？？？

3.2 轉化者

換個心情，換個思路。。。（透。。。）
這個問題稱為廣義拉格朗日函數的極大極小問題。
\begin{align} \max_{\alpha_i, \beta_j;\alpha_i \geq0} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\tag{3.3} \end{align}
也就是求
\begin{align} \max_{\alpha_i, \beta_j;}\min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\\ s.t. \ \alpha_i \geq0 \tag{3.4} \end{align}

3.3 大小安排一波？？？

假設公式(3.2) 原始人 的最優(yōu)解為p^*，公式(3.4) 轉化者 的最優(yōu)解為d^*。
因為
\begin{align} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \max_{\alpha_i, \beta_j; \alpha_i \geq0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{3.5} \end{align}
因為原始人和轉化者都有最優(yōu)解，所以有
\begin{align} d^*=\max_{\alpha_i, \beta_j;} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \min_x \max_{\alpha_i, \beta_j} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=p^* \tag{3.5} \end{align}
所以在KKT條件中，還要加上這幾條，最后是：
\begin{align} \left\{\begin{matrix} \bigtriangledown_{\boldsymbol{x}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ \bigtriangledown_{\boldsymbol{\alpha}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ \bigtriangledown_{\boldsymbol{\beta}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \alpha_i \geq 0 \ & (i=1,2,...,k)\\ \alpha_i c_i(\boldsymbol{x})=0\\ h_j(\boldsymbol{x})=0 \end{matrix}\right. \tag{3.6} \end{align}

4. 小結

所以，要求一個連續(xù)可微函數的最小值，并且還有一堆限制條件，可以這么做：

  1. 引入拉格朗日乘子，構造拉格朗日函數；
  2. 計算拉格朗日函數對未知參數的偏導數，并令導數為0，求解參數。

  3. 將參數代入拉格朗日函數中，并轉化成對偶問題后求解。（轉換的時候注意其KKT條件）


    疲憊。。。

5. 參考文獻

《西瓜書》
《統(tǒng)計學習方法》
《拉格朗日乘子法》

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容