KKT条件详解
主要参考这篇文章和这个知乎回答。
KKT最优化条件是Karush[1939]，以及Kuhn和Tucker[1951]先后独立发表出來的。这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视，因此许多情况下只记载成库恩塔克条件（Kuhn-Tucker conditions)
它是非线性规划领域的重要成果，是判断某点是极值点的必要条件。对于凸规划，KKT条件就是充要条件了，只要满足则一定是极值点，且一定得到的是全局最优解（凸问题）。
KKT条件的引入推广了拉格朗日乘子法，拉格朗日乘数法原本只是解决等式约束下的优化问题，本科的高数里就讲了（我竟读研了才学懂，惭愧），而引入KKT条件的拉格朗日乘子法可用于更普遍的有不等式约束的情况。
（一）问题模型
“等式约束+不等式约束” 优化问题是最复杂也最常见的一种模型。问题建模为：
min f x ) s . t . h k x ) = 0 , g j x ) ≤ 0 j = 1 , 2 … , n ; k = 1 , 2 … , l min fx) quad s.t.h_kx)=0quad,quad g_jx)leq0quad j=1,2ldots,n;k=1,2ldots,lminfx)s.t.hkx)=0,gjx)≤0j=1,2…,n;k=1,2…,l
思路是要把问题转化为无约束的简单优化问题，分为两步：
先把不等式约束条件转化为等式约束条件。 how？→ o→ 引入 松弛变量，即KKT乘子
再把等式约束转化为无约束优化问题。 how? → o→ 引入拉格朗日乘子
（二）一点铺垫
后面要用这个结论：
实质上，KKT条件描述的是：这个点已经是可行域（满足所有约束条件的n维空间）的边界了，再走一点就不满足约束条件了。显然，最优解一定在可行域的边界上的，以初中学的线性规划作为简单的例子，
这张图的紫色区域就是四个不等式约束限定的可行域，如果求z=x+2y的最大值，结果当然是红星点取得最大值，总之极值点应该在可行域的边界，这在自变量多的高维可行域空间也是如此，只是不好画图直观去看了。
（三）KKT到底是什么
KKT条件就是说：
如果一个点x ∗ x^*x∗是满足所有约束的极值点，那么
{ ∇ f x ∗ ) + ∑ k λ k ∇ h k x ∗ ) + ∑ j μ j ∇ g j x ∗ ) = 0 1 ) μ j ≥ 0 2 ) μ j g j x ∗ ) = 0 3 ) g j x ∗ ) ≤ 0 4 ) left{
∇fx∗)+∑kλk∇hkx∗)+∑jμj∇gjx∗)μjμjgjx∗)gjx∗)=≥=≤01)02)03)04)∇fx∗)+∑kλk∇hkx∗)+∑jμj∇gjx∗)=01)μj≥02)μjgjx∗)=03)gjx∗)≤04)
ight.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧∇fx∗)+k∑λk∇hkx∗)+j∑μj∇gjx∗)μjμ