什么是KKT 条件（Karush-Kuhn-Tucker 条件）
KKT 条件（Karush-Kuhn-Tucker 条件）是优化理论中的一组须要条件，适用于求解带有等式和不等式约束的非线性规划问题。当目的函数和约束条件是凸的时，KKT 条件也是找到最优解的充分条件。在支持向量机（SVM）的优化中，KKT 条件起到了紧张作用，它资助我们通过对偶问题找到原始问题的最优解。KKT 条件是对经典的拉格朗日乘子法的扩展，用于处置惩罚带有不等式约束的优化问题。它为优化问题提供了一组条件，当满意这些条件时，可以找到最优解。
1. KKT 条件的定义
对于一个优化问题：
min x f ( x ) \min_{x} f(x) xminf(x)
subject to g i ( x ) ≤ 0 , i = 1 , 2 , … , m \text{subject to} \quad g_i(x) \leq 0, \quad i = 1, 2, \dots, m subject togi(x)≤0,i=1,2,…,m
h j ( x ) = 0 , j = 1 , 2 , … , p h_j(x) = 0, \quad j = 1, 2, \dots, p hj(x)=0,j=1,2,…,p
其中：
[*] f ( x ) f(x) f(x) 是目的函数，我们希望最小化它。
[*] g i ( x ) ≤ 0 g_i(x) \leq 0 gi(x)≤0 是不等式约束条件。
[*] h j ( x ) = 0 h_j(x) = 0 hj(x)=0 是等式约束条件。
为了利用 KKT 条件，我们引入拉格朗日函数：
L ( x , λ , μ ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 p μ j h j ( 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) L(x,λ,μ)=f(x)+i=1∑mλigi(x)+j=1∑pμjhj(x)
其中：
[*] λ i ≥ 0 \lambda_i \geq 0 λi≥0 是对应于不等式约束的拉格朗日乘子。
[*] μ j \mu_j μj 是对应于等式约束的拉格朗日乘子。
KKT 条件包含以下几个部门：
2. KKT 条件的四个部门
1. 站点条件（Stationarity Condition）
这是对拉格朗日函数关于优化变量 x x x 的一阶导数必须为 0 的条件。即：
∂ L ( x , λ , μ ) ∂ x = 0 \frac{\partial L(x, \lambda, \mu)}{\partial x} = 0 ∂x∂L(x,λ,μ)=0
这个条件表示，在最优解处，拉格朗日函数对 x x x 的梯度为 0。这与经典的无约束优化中的一阶导数为零的极值条件类似，只不外现在是处置惩罚带有约束的环境。
2. 可行性条件（Primal Feasibility Condition）
这表示原始问题中的约束条件必须被满意：
g i ( x ) ≤ 0 , h j ( x ) = 0 g_i(x) \leq 0, \quad h_j(x) = 0 gi(x)≤0,hj(x)=0
这意味着在最优解处，全部的不等式约束和等式约束都必须建立。该条件确保最优解是可行解。
3. 对偶可行性条件（Dual Feasibility Condition）
拉格朗日乘子 λ i \lambda_i λi 必须为非负：
λ i ≥ 0 , i = 1 , 2 , … , m \lambda_i \geq 0, \quad i = 1, 2, \dots, m λi≥0,i=1,2,…,m
这个条件确保了不等式约束的拉格朗日乘子不能为负值。
4. 互补松弛条件（Complementary Slackness Condition）
互补松弛条件形貌了约束的松弛性，即如果不等式约束 g i ( x ) g_i(x) gi(x) 不紧（即 g i ( x ) < 0 g_i(x) < 0 gi(x)<0），那么对应的拉格朗日乘子 λ i \lambda_i λi 必须为 0。如果 g i ( x ) = 0 g_i(x) = 0 gi(x)=0（即约束被严格满意），则 λ i \lambda_i λi 可以为正值：
λ i g i ( x ) = 0 , i = 1 , 2 , … , m \lambda_i g_i(x) = 0, \quad i = 1, 2, \dots, m λigi(x)=0,i=1,2,…,m
这个条件确保了，当某个不等式约束不活泼时（即约束没有被牢牢满意），对应的拉格朗日乘子 λ i \lambda_i λi 也是零；而当约束被严格满意时（约束成为有效的约束），相应的拉格朗日乘子 λ i \lambda_i λi 则可以为正值。
3. KKT 条件的物理和几何表明
站点条件：
这相当于在拉格朗日函数构造的拉格朗日乘子空间中寻找梯度为零的点，确保在最长处上不存在沿任何方向的降落空间。
可行性条件：
优化问题的解必须满意全部的约束条件，这意味着解在约束空间内。
对偶可行性条件：
对不等式约束的拉格朗日乘子必须为非负。这是由于拉格朗日乘子代表了约束对目的函数的影响，如果一个约束黑白活泼的，那么它对目的函数的影相应该为零或正。
互补松弛条件：
互补松弛条件反映了约束对优化问题的影响。如果一个约束是松弛的（即不被严格满意），它对优化问题的影响是零。如果约束被牢牢满意，它就会影响目的函数，体现为拉格朗日乘子的非零值。
4. KKT 条件在支持向量机（SVM）中的应用
在支持向量机中，KKT 条件用于判断哪些数据点是支持向量。SVM 的优化问题可以通过拉格朗日对偶性转化为一个对偶问题，这个对偶问题满意 KKT 条件。
具体到 SVM 中，KKT 条件可以表明如下：
[*]站点条件：这是对 w \mathbf{w} w 和 b b b 求偏导数，确保在最优解处， w \mathbf{w} w 和 b b b 满意最优性条件。公式 9-25 和 9-26 就是这部门的条件。
[*]可行性条件：对于 SVM，全部数据点必须满意 y i ( w T x i + b ) ≥ 1 y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 yi(wTxi+b)≥1。这意味着全部数据点必须被正确分类，或者在某些环境下（软间隔支持向量机）允许肯定的误分类。
[*]对偶可行性条件：拉格朗日乘子 α i ≥ 0 \alpha_i \geq 0 αi≥0。只有那些 α i > 0 \alpha_i > 0 αi>0 的点（即支持向量）对分类器有贡献。
[*]互补松弛条件：如果某个点严格满意 y i ( w T x i + b ) > 1 y_i (\mathbf{w}^T \mathbf{x}_i + b) > 1 yi(wTxi+b)>1，那么对应的拉格朗日乘子 α i \alpha_i αi 必须为 0。这意味着这些点不是支持向量，只是远离超平面的点，不影响分类超平面的定义。
5. 总结
KKT 条件黑白线性规划中解决带有约束的优化问题的一个紧张工具，广泛应用于呆板学习（如支持向量机）等领域。它联合了站点条件、可行性条件、对偶可行性和互补松弛条件，确保找到的解既是可行解，又是最优解。
在支持向量机中，KKT 条件资助我们判断哪些点是支持向量，并且通过拉格朗日乘子法和对偶问题推导出最终的分类超平面。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]