【数值优化】Karush-Kuhn-Tucker(KKT) Method

KKT or generalized Lagrange function(KKT或增广拉格朗日法)

增广拉格朗日法是为了解决带约束的优化问题而产生的
其为每个约束引入拉格朗日乘子$\lambda_i,\alpha_j$

$$L(x,\lambda,\alpha)=f(x)+\sum_i \lambda_ig^{(i)}(x)+\sum_j \alpha_jh^{(j)}(x)$$

其中$g$为等式约束,$h$为不等式约束

然后可以解决

• 约束最小化问题 $$\min_x\max_\lambda\max_{\alpha,\alpha\ge0}f(x)+\sum_i \lambda_ig^{(i)}(x)+\sum_j \alpha_jh^{(j)}(x)$$
• 约束最大化问题 $$\min_x\max_\lambda\max_{\alpha,\alpha\ge0}-f(x)+\sum_i \lambda_ig^{(i)}(x)+\sum_j \alpha_jh^{(j)}(x)$$

根据KKT条件

• 1.梯度为0
• 2.约束条件: 不等式乘子非负,且各约束条件满足
• 3.乘子互补$\alpha \odot h(x)=0$.也就是要么不等式约束乘子为0，要么不等式约束条件为0