Karush-Kuhn-Tucker (KKT) 條件

本文的閱讀等級:中級

在優化理論,Karush-Kuhn-Tucker (KKT) 條件是非線性規劃 (nonlinear programming) 最佳解的必要條件[1]。KKT 條件將 Lagrange 乘數法 (Lagrange multipliers) 所處理涉及束縛等式的約束優化問題推廣至不等式。在實際應用上,KKT 條件 (方程組) 一般不存在代數解,許多優化算法可供數值計算選用[2]。這篇短文從 Lagrange 乘數法推導 KKT 條件並舉一個簡單的例子說明解法。

 
給定一個目標函數 f:\mathbb{R}^n\to\mathbb{R},我們希望找到 \mathbf{x}\in\mathbb{R}^n,在滿足束縛條件 g(\mathbf{x})=0 的前提下,使得 f(\mathbf{x}) 有最小值。這個約束優化問題記為

\displaystyle  \begin{array}{ll}  \hbox{minimize}&f(\mathbf{x})\\  \hbox{subject to}&g(\mathbf{x})=0.  \end{array}

為方便分析,假設 fg 是連續可導函數 (C^1 函數)。Lagrange 乘數法是受限束縛等式的約束優化問題的典型解法 (見“ Lagrange 乘數法”)。定義 Lagrangian 函數

\displaystyle  L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda g(\mathbf{x})

其中 \lambda 稱為 Lagrange 乘數。Lagrange 乘數法將原本的約束優化問題轉換成等價的無約束優化問題

\displaystyle  \underset{\mathbf{x},\lambda}{\hbox{minimize}}~~L(\mathbf{x},\lambda).

計算 L\mathbf{x}\lambda 的偏導數並設為零,可得最佳解的必要條件:

\displaystyle  \begin{aligned}  \nabla_{\mathbf{x}}L&=\frac{\partial L}{\partial\mathbf{x}}=\nabla f+\lambda\nabla g=\mathbf{0}\\  \nabla_{\lambda}L&=\frac{\partial L}{\partial\lambda}=g(\mathbf{x})=0,  \end{aligned}

其中第一式為定常方程 (stationary equation),第二式為束縛條件。解開上面 n+1 個方程式可得 L(\mathbf{x},\lambda) 的駐點 (stationary point) \mathbf{x}^\star 以及 \lambda 的值 (正負數皆可能)。

 
接下來我們將束縛等式 g(\mathbf{x})=0 推廣為不等式 g(\mathbf{x})\le 0。考慮這個問題

\displaystyle  \begin{array}{ll}  \hbox{minimize}&f(\mathbf{x})\\  \hbox{subject to}&g(\mathbf{x})\le 0.  \end{array}

束縛不等式 g(\mathbf{x})\le 0 稱為原始可行性 (primal feasibility),據此我們定義可行域 (feasible region) K=\{\mathbf{x}\in\mathbb{R}^n|g(\mathbf{x})\le 0\}。假設 \mathbf{x}^\star 為滿足束縛條件的最佳解,分開兩種情況討論:(1) g(\mathbf{x}^\star)<0,最佳解位於 K 的內部,稱為內部解 (interior solution),這時束縛條件是無效的 (inactive);(2) g(\mathbf{x}^\star)=0,最佳解落在 K 的邊界,稱為邊界解 (boundary solution),此時束縛條件是有效的 (active)。這兩種情況的最佳解具有不同的必要條件。

  1. 內部解:在束縛條件無效的情形下,g(\mathbf{x}) 不起作用,約束優化問題退化為無約束優化問題,因此駐點 \mathbf{x}^\star 滿足 \nabla f =\mathbf{0}\lambda=0
  2. 邊界解:在束縛條件有效的情形下,束縛不等式變成等式 g(\mathbf{x})=0,這與前述 Lagrange 乘數法的情況相同。我們可以證明駐點 \mathbf{x}^\star 發生於 \nabla f\in\hbox{span}\{\nabla g\} (證明見“ Lagrange 乘數法”),換句話說,存在 \lambda 使得 \nabla f=-\lambda\nabla g,但這裡 \lambda 的正負號是有其意義的。因為我們希望最小化 f,梯度 \nabla f (函數 f 在點 \mathbf{x} 的最陡上升方向) 應該指向可行域 K 的內部,但 \nabla g 指向 K 的外部 (即 g(\mathbf{x})>0 的區域),因此 \lambda\ge 0,稱為對偶可行性 (dual feasibility)[3]

不論是內部解或邊界解,\lambda g(\mathbf{x})=0 恆成立,稱為補鬆弛 (complementary slackness)。整合上述兩種情況,最佳解的必要條件包括 Lagrangian 函數 L(\mathbf{x},\lambda) 的定常方程式、原始可行性、對偶可行性,以及補鬆弛:

\displaystyle  \begin{aligned}  \nabla_{\mathbf{x}}L&=\nabla f+\lambda\nabla g=\mathbf{0}\\  g(\mathbf{x})&\le 0\\  \lambda&\ge 0\\  \lambda g(\mathbf{x})&=0.  \end{aligned}

這些條件合稱為 Karush-Kuhn-Tucker (KKT) 條件。如果我們要最大化 f(\mathbf{x}) 且受限於 g(\mathbf{x})\le 0,那麼對偶可行性要改成 \lambda\le 0

 
上面結果可推廣至多個束縛等式與束縛不等式的情況。考慮標準約束優化問題 (或稱非線性規劃):

\displaystyle  \begin{array}{lll}  \hbox{minimize}&f(\mathbf{x})\\  \hbox{subject to}&g_j(\mathbf{x})=0,&j=1,\ldots,m,\\  &h_k(\mathbf{x})\le 0,&k=1,\ldots,p.  \end{array}

定義 Lagrangian 函數

\displaystyle  L\left(\mathbf{x},\{\lambda_j\},\{\mu_k\}\right)=f(\mathbf{x})+\sum_{j=1}^m\lambda_jg_j(\mathbf{x})+\sum_{k=1}^p\mu_kh_k(\mathbf{x})

其中 \lambda_j 是對應 g_j(\mathbf{x})=0 的 Lagrange 乘數,\mu_k 是對應 h_k(\mathbf{x})\le 0 的 Lagrange 乘數 (或稱 KKT 乘數)。KKT 條件包括

\displaystyle  \begin{aligned}  \nabla_{\mathbf{x}}L&=\mathbf{0}\\  g_j(\mathbf{x})&=0,~~j=1,\ldots,m,\\  h_k(\mathbf{x})&\le 0,\\  \mu_k&\ge 0,\\  \mu_k h_k(\mathbf{x})&=0,~~k=1,\ldots,p.  \end{aligned}

 
看一個例子,考慮這個問題

\displaystyle  \begin{array}{ll}  \hbox{minimize}&x_1^2+x_2^2,\\  \hbox{subject to}&x_1+x_2=1\\  &x_2\le\alpha,\end{array}

其中 (x_1,x_2)\in\mathbb{R}^2\alpha 為實數。寫出 Lagrangigan 函數

\displaystyle  L(x_1,x_2,\lambda,\mu)=x_1^2+x_2^2+\lambda(1-x_1-x_2)+\mu(x_2-  \alpha)

KKT 方程組如下:

\displaystyle  \begin{aligned}  \frac{\partial L}{\partial x_i}&=0,~~i=1,2,\\  x_1+x_2&=1\\  x_2-\alpha&\le 0\\  \mu&\ge 0\\  \mu (x_2-\alpha)&=0.  \end{aligned}

求偏導可得 \frac{\partial L}{\partial x_1}=2x_1-\lambda=0\frac{\partial L}{\partial x_2}=2x_2-\lambda+\mu=0,分別解出 x_1=\frac{\lambda}{2}x_2=\frac{\lambda}{2}-\frac{\mu}{2}。代入束縛等式 x_1+x_2=\lambda-\frac{\mu}{2}=1\lambda=\frac{\mu}{2}+1。合併上面結果,

\displaystyle  x_1=\frac{\mu}{4}+\frac{1}{2},~~~~x_2=-\frac{\mu}{4}+\frac{1}{2}

最後再加入束縛不等式 -\frac{\mu}{4}+\frac{1}{2}\le\alpha\mu\ge 2-4\alpha。底下分開三種情況討論。

  1. \alpha>\frac{1}{2}:不難驗證 \mu=0>2-4\alpha 滿足所有的 KKT 條件,束縛不等式是無效的,x^\star_1=x^\star_2=\frac{1}{2} 是內部解,目標函數的極小值是 \frac{1}{2}
  2. \alpha=\frac{1}{2}:如同1,\mu=0=2-4\alpha 滿足所有的 KKT 條件,x^\star_1=x^\star_2=\frac{1}{2} 是邊界解,因為 x^\star_2=\alpha
  3. \alpha < \frac{1}{2}:這時束縛不等式是有效的,\mu=2-4\alpha>0,則 x^\star_1=1-\alphax^\star_2=\alpha,目標函數的極小值是 (1-\alpha)^2+\alpha^2

 
註解
[1] KKT 條件要合乎最佳解的必要條件須滿足某些規律 (regularity conditions),詳見維基百科:KKT conditions
[2] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[3] 對偶可行性此名來自於 Lagrange 對偶問題 (dual problem),在此從略。

廣告
本篇發表於 特別主題 並標籤為 , , 。將永久鏈結加入書籤。

3 Responses to Karush-Kuhn-Tucker (KKT) 條件

  1. 陈宇 說道:

    老師你好,
    你這裡的對偶可行性和滿足Slater條件的對偶問題等價有什麼聯繫嗎?

    • ccjou 說道:

      這我也不清楚。不過Slater’s condition說可行域必定有一個內點,對偶可行性則是一個條件的名稱。

  2. Fan 說道:

    謝謝老師簡潔清晰的文字!

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s