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}$

為方便分析，假設 $f$ 與 $g$ 是連續可導函數 ( $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)。這兩種情況的最佳解具有不同的必要條件。

內部解：在束縛條件無效的情形下， $g(\mathbf{x})$ 不起作用，約束優化問題退化為無約束優化問題，因此駐點 $\mathbf{x}^\star$ 滿足 $\nabla f =\mathbf{0}$ 且 $\lambda=0$ 。
邊界解：在束縛條件有效的情形下，束縛不等式變成等式 $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$ 。底下分開三種情況討論。

$\alpha>\frac{1}{2}$ ：不難驗證 $\mu=0>2-4\alpha$ 滿足所有的 KKT 條件，束縛不等式是無效的， $x^\star_1=x^\star_2=\frac{1}{2}$ 是內部解，目標函數的極小值是 $\frac{1}{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$ 。
$\alpha < \frac{1}{2}$ ：這時束縛不等式是有效的， $\mu=2-4\alpha>0$ ，則 $x^\star_1=1-\alpha$ 且 $x^\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)，在此從略。

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

陈宇 says:

03/13/2017 at 4:57 pm

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

- ccjou says:
  
  03/13/2017 at 8:21 pm
  
  這我也不清楚。不過Slater’s condition說可行域必定有一個內點，對偶可行性則是一個條件的名稱。
  
Fan says:

08/31/2017 at 10:59 pm

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

Steven Li Chen says:

11/18/2018 at 12:00 am

老師您好,
有個疑惑: “梯度 \nabla f (函數 f 在點 \mathbf{x} 的最陡上升方向) 應該指向可行域 K 的內部”….
為何f指向K的內部呢? 梯度應該指向函數增長最快的方向, 但是題中未指明K的內部就是增長最快方向呀?

- 孙言 says:
  
  11/28/2020 at 11:46 pm
  
  因为X-star是f(x)的极小值点，那么说明可行域K中任何一个点都比X-star大，所以f在X-star处的梯度（指向增长最快的方向，当然是增长的方向）是指向K内部的（内部点比它大）
  
Pingback: Mathematics in Machine Learning – Math.py
周子傑 says:

04/06/2023 at 10:26 pm

老師，您好，請問一般來講subject to中的條件是binding和relaxed是什麽情況下才會出現？

	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨
	jeff85898 on 利用分塊矩陣證明 det(AB)=(det A)(det…