Constrained Optimization - Solvi

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，（评论）