python學智能算法（三十））|SVM-KKT條件的數學理解

【1】引言

前序學習進程中，通過類比力的平衡對KKT條件進行了初步的理解。
今天我們更進一步，常使用數學語言進一步解釋KKT條件。

【2】帶約束的最小優化問題

首先定義一個即將求解的優化問題：
目標函數：最小化 $f(x)(x∈Rn)f(x)(x\in R^{n})$
約束條件：
不等式約束： $gi(x)≤0(i=1,2,,...,m)g_{i}(x)\leq0(i=1,2,,...,m)$ ，一共m個
等式約束： $h_{j}(x)=0(j=1,2,,...,p)$ ，一共p個
這個時候就仿照之前的拉格朗日函數構造方法，構造出適用的拉格朗日函數：
$L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1pμjhj(x)L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{p}\mu_{j}h_{j}(x)$
其中：
$λi≥0\lambda_{i}\geq0$ 是不等式約束 $gi≤0g_{i}\leq0$ 對應的拉格朗日乘子， $λi\lambda_{i}$ 嚴格非負；
$μj∈R\mu_{j}\in R$ 是等式約束 $h_{j}(x)=0$ 對應的拉格朗日乘子， $μj\mu_{j}$ 沒有符號限制。

【2.1】局部最優解

如果 $x^{*}$ 是上述問題的局部最優解，且滿足約束規范，則存在乘子 $λ?=(λ1?,...,λm?)\lambda^{*}=(\lambda_{1}^{*},...,\lambda_{m}^{*})$ 和 $μ?=(μ1?,...,μp?)\mu^{*}=(\mu_{1}^{*},...,\mu_{p}^{*})$ ，是的以下五個條件同時成立：

【2.1.1】梯度為零條件

拉格朗日函數在 $x^{*}$ 處滿足： $?xL(x?,λ?,μ?)=0\nabla_{x} L(x^{*},\lambda^{*},\mu^{*})=0$

具體展開來后：
$?f(x?)+∑i=1mλi??gi(x?)+∑j=1pμj??hj(x?)=0\nabla f(x^{*})+\sum_{i=1}^{m}\lambda_{i}^{*}\nabla g_{i}(x^{*})+\sum_{j=1}^{p}\mu_{j}^{*}\nabla h_{j}(x^{*})=0$
換句話說，目標函數的梯度與約束梯度的加權和相平衡。

【2.1.2】不等式約束可行性

所有不等式約束在 $x^{*}$ 處滿足： $gi(x?)≤0(i=1,2,...,m)g_{i}(x^{*})\leq0 (i=1,2,...,m)$ 也就是解必須嚴格落在不等式約束定義的可行域內。

【2.1.3】等式約束可行性

所有等式約束在 $x^{*}$ 處滿足： $h_{j}(x^{*})=0 (j=1,2,...,p)$ 也就是解必須嚴格落在等式約束定義的曲面上。

【2.1.4】拉格朗日乘子非負性

不等式約束對應的乘子非負： $λi?≥0(j=1,2,...,m)\lambda_{i}^{*}\geq0 (j=1,2,...,m)$
此時解釋起來有一個形象的理解，因為 $gi≤0g_{i}\leq0$ 嚴格成立，所以 $λi?≥0\lambda_{i}^{*}\geq0$ 就像在唱反調， $g_{i}$ 也就是解必須嚴格落在等式約束定義的曲面上。
不等式約束 $gi(x)≤0g_{i}(x)\leq0$ 定義了一個可行域，當最優解 $x^{*}$ 落在某個約束的邊界上，此時存在 $g_{i}(x^{*})=0$ ，若 $x$ 稍微偏離 $x^{*}$ 且試圖進入 $g_{i}(x)>0$ 的區域，也就是嘗試進入非可行域，約束就會阻止這種偏離，就像給 $x$ 施加了一個指向可行域內部的“推力”。
目標函數的梯度 $?f(x?)\nabla f(x^{*})$ 指向 $f (x)$ 增長最快的方向
，對于此處求最小化的目標，我們實際上是希望 $x$ 向 $??f(x)-\nabla f(x)$ 方向移動。如果定義梯度 $?f(x?)\nabla f(x^{*})$ 是拉力方向，則優化方向是拉力的反方向；
而約束函數 $g_{i}(x^{*})$ 的梯度指向 $g_{i}(x)$ 增長最快的方向，實際上指向了非可行域，所以 $??gi(x?)-\nabla g_{i}(x^{*})$ 才是指向可行域，而在 $λi?≥0\lambda_{i}^{*}\geq0$ 的前提下，可以保障 $?λi??gi(x?)-\lambda_{i}^{*}\nabla g_{i}(x^{*})$ 面向可行域，所以 $?λi??gi(x?)-\lambda_{i}^{*}\nabla g_{i}(x^{*})$ 是推力的方向。

【2.1.5】互補松弛條件

乘子與不等式約束的乘積為零：
$λi??gi(x?)=0(i=1,2,...,m)\lambda_{i}^{*}\cdot g_{i}(x^{*})=0 (i=1,2,...,m)$
實際上有兩種情況：
當約束不起作用， $gi(x)≤0g_{i}(x)\leq0$ ，此時必然有乘子為零即 $λi?=0\lambda _{i}^{*}=0$

當約束起作用， $g_{i}(x)=0$ ，此時必然有乘子大于零即 $λi?≥0\lambda _{i}^{*}\geq0$

【3】總結

從數學的角度重新粗糙解讀了KKT條件。

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

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