本文的閱讀等級:中級
在優化理論,Karush-Kuhn-Tucker (KKT) 條件是非線性規劃 (nonlinear programming) 最佳解的必要條件[1]。KKT 條件將 Lagrange 乘數法 (Lagrange multipliers) 所處理涉及束縛等式的約束優化問題推廣至不等式。在實際應用上,KKT 條件 (方程組) 一般不存在代數解,許多優化算法可供數值計算選用[2]。這篇短文從 Lagrange 乘數法推導 KKT 條件並舉一個簡單的例子說明解法。
給定一個目標函數 ,我們希望找到 ,在滿足束縛條件 的前提下,使得 有最小值。這個約束優化問題記為
為方便分析,假設 與 是連續可導函數 ( 函數)。Lagrange 乘數法是受限束縛等式的約束優化問題的典型解法 (見“ Lagrange 乘數法”)。定義 Lagrangian 函數
,
其中 稱為 Lagrange 乘數。Lagrange 乘數法將原本的約束優化問題轉換成等價的無約束優化問題
計算 對 與 的偏導數並設為零,可得最佳解的必要條件:
其中第一式為定常方程 (stationary equation),第二式為束縛條件。解開上面 個方程式可得 的駐點 (stationary point) 與 的值 (正負數皆可能)。
接下來我們將束縛等式 推廣為不等式 。考慮這個問題
束縛不等式 稱為原始可行性 (primal feasibility),據此我們定義可行域 (feasible region) 。假設 為滿足束縛條件的最佳解,分開兩種情況討論:(1) ,最佳解位於 的內部,稱為內部解 (interior solution),這時束縛條件是無效的 (inactive);(2) ,最佳解落在 的邊界,稱為邊界解 (boundary solution),此時束縛條件是有效的 (active)。這兩種情況的最佳解具有不同的必要條件。
- 內部解:在束縛條件無效的情形下, 不起作用,約束優化問題退化為無約束優化問題,因此駐點 滿足 且 。
- 邊界解:在束縛條件有效的情形下,束縛不等式變成等式 ,這與前述 Lagrange 乘數法的情況相同。我們可以證明駐點 發生於 (證明見“ Lagrange 乘數法”),換句話說,存在 使得 ,但這裡 的正負號是有其意義的。因為我們希望最小化 ,梯度 (函數 在點 的最陡上升方向) 應該指向可行域 的內部,但 指向 的外部 (即 的區域),因此 ,稱為對偶可行性 (dual feasibility)[3]。
不論是內部解或邊界解, 恆成立,稱為補鬆弛 (complementary slackness)。整合上述兩種情況,最佳解的必要條件包括 Lagrangian 函數 的定常方程式、原始可行性、對偶可行性,以及補鬆弛:
這些條件合稱為 Karush-Kuhn-Tucker (KKT) 條件。如果我們要最大化 且受限於 ,那麼對偶可行性要改成 。
上面結果可推廣至多個束縛等式與束縛不等式的情況。考慮標準約束優化問題 (或稱非線性規劃):
定義 Lagrangian 函數
,
其中 是對應 的 Lagrange 乘數, 是對應 的 Lagrange 乘數 (或稱 KKT 乘數)。KKT 條件包括
看一個例子,考慮這個問題
其中 , 為實數。寫出 Lagrangigan 函數
,
KKT 方程組如下:
求偏導可得 且 ,分別解出 且 。代入束縛等式 或 。合併上面結果,
。
最後再加入束縛不等式 或 。底下分開三種情況討論。
- :不難驗證 滿足所有的 KKT 條件,束縛不等式是無效的, 是內部解,目標函數的極小值是 。
- :如同1, 滿足所有的 KKT 條件, 是邊界解,因為 。
- :這時束縛不等式是有效的,,則 且 ,目標函數的極小值是 。
註解
[1] KKT 條件要合乎最佳解的必要條件須滿足某些規律 (regularity conditions),詳見維基百科:KKT conditions。
[2] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[3] 對偶可行性此名來自於 Lagrange 對偶問題 (dual problem),在此從略。
老師你好,
你這裡的對偶可行性和滿足Slater條件的對偶問題等價有什麼聯繫嗎?
這我也不清楚。不過Slater’s condition說可行域必定有一個內點,對偶可行性則是一個條件的名稱。
謝謝老師簡潔清晰的文字!
老師您好,
有個疑惑: “梯度 \nabla f (函數 f 在點 \mathbf{x} 的最陡上升方向) 應該指向可行域 K 的內部”….
為何f指向K的內部呢? 梯度應該指向函數增長最快的方向, 但是題中未指明K的內部就是增長最快方向呀?
因为X-star是f(x)的极小值点,那么说明可行域K中任何一个点都比X-star大,所以f在X-star处的梯度(指向增长最快的方向,当然是增长的方向)是指向K内部的(内部点比它大)
Pingback: Mathematics in Machine Learning – Math.py
老師,您好,請問一般來講subject to中的條件是binding和relaxed是什麽情況下才會出現?