KKT 條件總結

KKT 條件（Karush-Kuhn-Tucker Conditions）是優化問題中的一組必要條件，用于求解帶有約束的非線性規劃問題。它是對拉格朗日乘數法的推廣，適用于包含不等式約束的優化問題。

1. KKT 條件的適用場景

KKT 條件適用于以下優化問題：

• 目標函數和約束函數是連續可微的。
• 問題形式為：
  \[\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, 2, \dots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, 2, \dots, p \end{aligned} \]
  其中：
  • \(f(\mathbf{x})\) 是目標函數。
  • \(g_i(\mathbf{x})\) 是不等式約束。
  • \(h_j(\mathbf{x})\) 是等式約束。

2. KKT 條件的內容

KKT 條件包括以下五部分：

(1) 原始可行性（Primal Feasibility）

解 \(\mathbf{x}^*\) 必須滿足原始問題的約束條件：

(2) 對偶可行性（Dual Feasibility）

拉格朗日乘數必須滿足非負性：

(3) 互補松弛性（Complementary Slackness）

對于每個不等式約束，拉格朗日乘數 \(\lambda_i\) 和約束函數 \(g_i(\mathbf{x}^*)\) 必須滿足：

這意味著：

• 如果 \(g_i(\mathbf{x}^*) < 0\)（約束不起作用），則 \(\lambda_i = 0\)。
• 如果 \(\lambda_i > 0\)，則 \(g_i(\mathbf{x}^*) = 0\)（約束起作用）。

(4) 梯度條件（Stationarity）

目標函數和約束函數的梯度滿足：

其中：

• \(\lambda_i\) 是不等式約束的拉格朗日乘數。
• \(\mu_j\) 是等式約束的拉格朗日乘數。

(5) 正則性條件（Regularity Conditions）

約束函數在解 \(\mathbf{x}^*\) 處滿足某些正則性條件（如線性獨立性約束規范，LICQ），以確保 KKT 條件成立。

3. KKT 條件的意義

• KKT 條件是優化問題的必要條件，即如果 \(\mathbf{x}^*\) 是局部最優解，則它必須滿足 KKT 條件。
• 對于凸優化問題，KKT 條件也是充分條件，即滿足 KKT 條件的解一定是全局最優解。

4. KKT 條件的應用

KKT 條件廣泛應用于以下領域：

• 非線性規劃（NLP）。
• 支持向量機（SVM）的優化問題。
• 經濟學中的約束優化問題。
• 工程中的最優控制問題。

5. KKT 條件的示例

考慮以下優化問題：

其 KKT 條件為：

1. 原始可行性：\(x - 1 \leq 0\)。
2. 對偶可行性：\(\lambda \geq 0\)。
3. 互補松弛性：\(\lambda \cdot (x - 1) = 0\)。
4. 梯度條件：\(2x + \lambda = 0\)。

解得：

• 如果約束起作用（\(x = 1\)），則 \(\lambda = -2\)，不滿足對偶可行性。
• 如果約束不起作用（\(\lambda = 0\)），則 \(x = 0\)，滿足所有 KKT 條件。

因此，最優解為 \(x^* = 0\)。

6. 總結

KKT 條件是優化理論中的重要工具，它將約束優化問題轉化為一組方程和不等式，為求解復雜優化問題提供了理論基礎。在實際應用中，KKT 條件常用于設計優化算法和驗證最優解。

以上內容由AI總結生成
參考：
[1] Karush-Kuhn-Tucker (KKT)條件
[2] 什么是KKT 條件（Karush-Kuhn-Tucker 條件）_kkt條件-CSDN博客