Intuition of KKT
finding supporting hyperplane[1]
设定
Lagrange multiplier本身适用于等式constraints，KKT multiplier适用于非等式，是Lagrange的一个泛化。
s.t.
KKT condition
可见之前的讨论[4]
KKT Qualification
即在什么情况下，原问题的极值点需要满足KKT condition
常用：
LCQ：等式与不等式约束都为仿射affine变换。
LICQ：对于激活[2] 的不等式约束，与等式约束，在极值处的gradient是线性无关的。（在向量空间中，对于一组向量，存在任意非全0的线性组合使其和为0，则为线性相关）
SC：Slater's condition，是convex，
都是仿射变换。
Solving KKT System
-
一般情况：
1、对于关于自变量梯度为0得到的方程组（行数跟自变量数量
一致，一般为
的表达式的解。
2、再将自变量的解带入（的方程组（行数跟限制条件数量一致，即关于
-
情况讨论：
由于，方程组可能有解，也可能无解，也可能有多个解。或者根本无法得到简洁的解析解。因此，通常而言对KKT system的求解并不是直接的，除非有解析解[3]，此时，很可能需要用一些数值解法来求解。
一个可参考的实际问题求解过程可以见[5]，By case，演绎推导。
我们的一些优化方法，都可以被解释为对KKT system的一种解法。 -
其他
如果当前问题比较难解。则通过对偶化等方式，可能能得到更简洁的解。
Refer
[1] https://en.wikipedia.org/wiki/Supporting_hyperplane
相关理论，https://en.wikipedia.org/wiki/Hyperplane_separation_theorem
[2]：只有当，即x在边界处时，才是激活的。即其项对应的kkt乘子
[3]求解思路：
Doc：A Karush-Kuhn-Tucker Example
The system of equations and inequalities corresponding to the KKT conditions is usually not solved directly, except in the few special cases where a [closed-form] solution can be derived analytically. In general, many optimization algorithms can be interpreted as methods for numerically solving the KKT system of equations and inequalities
[4]KKT conditions：
https://www.jianshu.com/p/1a733971b25e
KKT condition for convex：
sufficiency？：https://math.stackexchange.com/questions/2325637/sufficiency-of-kkt-conditions-when-the-objective-function-is-convex-on-the-inter
sufficient or necessary？https://math.stackexchange.com/questions/2513300/is-kkt-conditions-necessary-and-sufficient-for-any-convex-problems
Connection between KKT condition & EL equation：
https://math.stackexchange.com/questions/1898887/connection-between-euler-lagrange-equations-and-kkt
[5]求解过程
例：https://www.jianshu.com/writer#/notebooks/31109505/notes/87921110/preview
例&dual：https://math.stackexchange.com/questions/2829235/kkt-optimality-conditions-in-optimization-exercise
例：https://math.stackexchange.com/questions/3197212/solve-kkt-conditions-of-the-following-problem，（评论）
网友评论