python学智能算法（三十））|SVM-KKT条件的数学理解
【1】引言
前序学习进程中，通过类比力的平衡对KKT条件进行了初步的理解。
今天我们更进一步，常使用数学语言进一步解释KKT条件。
【2】带约束的最小优化问题
首先定义一个即将求解的优化问题：
目标函数：最小化f(x)(x∈Rn)f(x)(x\in R^{n})f(x)(x∈Rn)
约束条件：
不等式约束：gi(x)≤0(i=1,2,,...,m)g_{i}(x)\leq0(i=1,2,,...,m)gi(x)≤0(i=1,2,,...,m)，一共m个
等式约束：hj(x)=0(j=1,2,,...,p)h_{j}(x)=0(j=1,2,,...,p)hj(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)L(x,λ,μ)=f(x)+i=1∑mλigi(x)+j=1∑pμjhj(x)
其中：
λi≥0\lambda_{i}\geq0λi≥0是不等式约束 gi≤0g_{i}\leq0gi≤0对应的拉格朗日乘子，λi\lambda_{i}λi严格非负；
μj∈R\mu_{j}\in Rμj∈R是等式约束hj(x)=0h_{j}(x)=0hj(x)=0对应的拉格朗日乘子，μj\mu_{j}μj没有符号限制。
【2.1】局部最优解
如果x∗x^{*}x∗是上述问题的局部最优解，且满足约束规范，则存在乘子λ∗=(λ1∗,...,λm∗)\lambda^{*}=(\lambda_{1}^{*},...,\lambda_{m}^{*})λ∗=(λ1∗,...,λm∗)和μ∗=(μ1∗,...,μp∗)\mu^{*}=(\mu_{1}^{*},...,\mu_{p}^{*})μ∗=(μ1∗,...,μp∗)，是的以下五个条件同时成立：
【2.1.1】梯度为零条件
拉格朗日函数在x∗x^{*}x∗处满足：∇xL(x∗,λ∗,μ∗)=0\nabla_{x} L(x^{*},\lambda^{*},\mu^{*})=0∇xL(x∗,λ∗,μ∗)=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∇f(x∗)+i=1∑mλi∗∇gi(x∗)+j=1∑pμj∗∇hj(x∗)=0
换句话说，目标函数的梯度与约束梯度的加权和相平衡。
【2.1.2】不等式约束可行性
所有不等式约束在x∗x^{*}x∗处满足：gi(x∗)≤0(i=1,2,...,m)g_{i}(x^{*})\leq0 (i=1,2,...,m)gi(x∗)≤0(i=1,2,...,m)也就是解必须严格落在不等式约束定义的可行域内。
【2.1.3】等式约束可行性
所有等式约束在x∗x^{*}x∗处满足：hj(x∗)=0(j=1,2,...,p)h_{j}(x^{*})=0 (j=1,2,...,p)hj(x∗)=0(j=1,2,...,p)也就是解必须严格落在等式约束定义的曲面上。
【2.1.4】拉格朗日乘子非负性
不等式约束对应的乘子非负：λi∗≥0(j=1,2,...,m)\lambda_{i}^{*}\geq0 (j=1,2,...,m)λi∗≥0(j=1,2,...,m)
此时解释起来有一个形象的理解，因为gi≤0g_{i}\leq0gi≤0严格成立，所以λi∗≥0\lambda_{i}^{*}\geq0λi∗≥0就像在唱反调，gig_{i}gi也就是解必须严格落在等式约束定义的曲面上。
不等式约束gi(x)≤0g_{i}(x)\leq0gi(x)≤0定义了一个可行域，当最优解x∗x^{*}x∗落在某个约束的边界上，此时存在gi(x∗)=0g_{i}(x^{*})=0gi(x∗)=0，若xxx稍微偏离x∗x^{*}x∗且试图进入gi(x)>0g_{i}(x)>0gi(x)>0的区域，也就是尝试进入非可行域，约束就会阻止这种偏离，就像给xxx施加了一个指向可行域内部的“推力”。
目标函数的梯度∇f(x∗)\nabla f(x^{*})∇f(x∗)指向f(x)f(x)f(x)增长最快的方向
，对于此处求最小化的目标，我们实际上是希望xxx向−∇f(x)-\nabla f(x)−∇f(x)方向移动。如果定义梯度∇f(x∗)\nabla f(x^{*})∇f(x∗)是拉力方向，则优化方向是拉力的反方向；
而约束函数gi(x∗)g_{i}(x^{*})gi(x∗)的梯度指向gi(x)g_{i}(x)gi(x)增长最快的方向，实际上指向了非可行域，所以−∇gi(x∗)-\nabla g_{i}(x^{*})−∇gi(x∗)才是指向可行域，而在λi∗≥0\lambda_{i}^{*}\geq0λi∗≥0的前提下，可以保障−λi∗∇gi(x∗)-\lambda_{i}^{*}\nabla g_{i}(x^{*})−λi∗∇gi(x∗)面向可行域，所以−λi∗∇gi(x∗)-\lambda_{i}^{*}\nabla g_{i}(x^{*})−λi∗∇gi(x∗)是推力的方向。
【2.1.5】互补松弛条件
乘子与不等式约束的乘积为零：
λi∗⋅gi(x∗)=0(i=1,2,...,m)\lambda_{i}^{*}\cdot g_{i}(x^{*})=0 (i=1,2,...,m)λi∗⋅gi(x∗)=0(i=1,2,...,m)
实际上有两种情况：
当约束不起作用，gi(x)≤0g_{i}(x)\leq0gi(x)≤0，此时必然有乘子为零即λi∗=0\lambda _{i}^{*}=0λi∗=0
当约束起作用，gi(x)=0g_{i}(x)=0gi(x)=0，此时必然有乘子大于零即λi∗≥0\lambda _{i}^{*}\geq0λi∗≥0
【3】总结
从数学的角度重新粗糙解读了KKT条件。