支持向量机预备知识（一）kkt条件

一、kkt条件
kkt条件是用来解决不等值约束条件下，求解极值的最优解的问题。
1、无约束优化问题最优性条件

若 min f(x) 可微，则其最优解的一阶必要条件为：

2、 有约束优化问题最优性条件
下面考虑如下带约束的优化问题

其中 $f,h_i,g_i$f,hi​,gi​可微且一阶导数连续，存在非负实数 和实数$\mu_i和\lambda_i$μi​和λi​，若$x*$x∗为局部最优解则以下条件成立：

其中最后一个条件$\mu_i*g_i(x*)=0$μi​∗gi​(x∗)=0代表$\mu_i和gi(x*)$μi​和gi(x∗)必有一个为0。当$\mu_i$μi​等于0时，约束条件不起作用，当$\mu_i$μi​不等于0但$g_i(x*)=0$gi​(x∗)=0代表约束条件起约束作用。
貌似这是一般情况下我们熟知的KKT条件，事实上，上面陈述的KKT条件并不完全正确（严谨），还缺少一个regularity条件。
2、regularity条件。

我的理解：解集之间相互线性独立的意思，解集之间相互没有交集。如$y>=x^2和y>=0$y>=x2和y>=0的解集就有交集（0，0）。
3. 缺少regularity条件KKT还是最优解的必要条件吗？
若满足regularity条件，KKT就是最优解的必要条件。所谓必要条件的意思是满足KKT条件的不一定是最优解（例如鞍点就满足KKT，但鞍点就不是最优解），但是如果不满足KKT条件就一定不是最优解，缺少了regularity条件，KKT条件就并非最优解的必要条件。
3、fritz条件

即我们要求利用kkt条件求出来的解为最小解，那么必须先验证fritz条件。若满足fritz条件，那么等式成立。
4、例子

即我们利用frizo条件，看$\mu_0的$μ0​的情况判断，子集是否有交集，如果$\mu_0$μ0​等于0，证明后面的集合优化有交集，如果$\mu_0$μ0​小于0，说明后面的kkt条件需要做调整，比如这个例子中我们如果要求最小解，λ3是可能是负数，当是负数时证明和我们要求的目标函数的目标相反，我们要求最小，但是优化条件却求最大，所以我们要λ3为正数，但是λ1就为负，即利用friza条件我们算出，我们知道目标函数和限制条件2有矛盾，所以舍弃目标函数2的约束。所以也证明我们的解集中有非独立解。