【基礎還得練】 KKT 條件

優秀教程-真正理解拉格朗日乘子法和 KKT 條件： link
優秀教程-最優化(6)：一般約束優化問題的最優性理論： link

KKT條件（Karush-Kuhn-Tucker條件）是非線性規劃中的一組必要條件，在某些情況下也是最優解的充分條件。它是對拉格朗日乘數法的推廣，適用于有約束的優化問題。以下是詳細公式和解釋：

問題形式

考慮如下非線性優化問題：

$\text{minimize } f(x), \quad x \in \mathbb{R}^n$

約束條件：

等式約束：
$h_i(x) = 0, \quad i = 1, \ldots, m$
不等式約束：
$g_j(x) \leq 0, \quad j = 1, \ldots, p$

這里：

$f (x)$ 是目標函數；
$h_i(x)$ 是等式約束函數；
$g_j(x)$ 是不等式約束函數。

KKT條件

KKT條件包括以下幾個部分：

1. 可行性條件

變量 $x^*$ 必須滿足約束條件：
$h_i(x^*) = 0, \quad i = 1, \ldots, m$
$g_j(x^*) \leq 0, \quad j = 1, \ldots, p$

2. 拉格朗日函數

定義拉格朗日函數：
$\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \sum_{j=1}^p \mu_j g_j(x)$
其中：

$\lambda_i$ 是等式約束的拉格朗日乘數；
$\mu_j$ 是不等式約束的拉格朗日乘數（ $\mu_j \geq 0$ ）。

3. 一階必要條件（梯度條件）

在最優解處，拉格朗日函數對 $x$ 的梯度為零：
$\nabla_x \mathcal{L}(x^*, \lambda^*, \mu^*) = \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^p \mu_j^* \nabla g_j(x^*) = 0$

4. 互補松弛條件

對于每個不等式約束：
$\mu_j^* g_j(x^*) = 0, \quad j = 1, \ldots, p$
這表示如果某個不等式約束 $g_j(x)$ 未達到邊界（即 $g_j(x^*) < 0$ ），那么對應的拉格朗日乘數 $\mu_j^*$ 必須為 0；反之，如果 $g_j(x^*) = 0$ ，那么 $\mu_j^* \geq 0$ 。

5. 拉格朗日乘數非負性

對于不等式約束，拉格朗日乘數必須非負：
$\mu_j^* \geq 0, \quad j = 1, \ldots, p$

總結公式

KKT條件可以總結為如下形式：
$\begin{aligned} &\text{(1) 可行性條件: } & h_i(x^*) &= 0, & g_j(x^*) &\leq 0 \\ &\text{(2) 梯度條件: } & \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^p \mu_j^* \nabla g_j(x^*) &= 0 \\ &\text{(3) 互補松弛: } & \mu_j^* g_j(x^*) &= 0 \\ &\text{(4) 非負性: } & \mu_j^* &\geq 0 \end{aligned}$

適用條件

KKT條件成立需要一定的假設，例如約束的正則性（滿足線性獨立約束限定條件或Slater條件）。當這些假設成立時：

如果 $f (x)$ 、 $h_i(x)$ 、 $g_j(x)$ 是凸函數，KKT條件是充分條件。
對一般優化問題，KKT條件是必要條件。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/64272.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/64272.shtml
英文地址，請注明出處：http://en.pswp.cn/web/64272.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！