Lagrange与KKT的简易解释

简易解释"/>

Lagrange与KKT的简易解释

本文将以梯度下降法的方式来解释Lagrange和KKT。

关键词：梯度下降法、等高线

基础定义

Lagrange

求解等式约束下的最优化问题

Lagrange函数： (1)

方程组的解是原问题的可能的最优解

KKT

求解不等式约束下的最优化问题

Lagrange函数： (2)

方程组，即KKT条件，的解是原问题的可能的最优解

解释

梯度的定义

，

等式约束

因为在最小化f(x)的同时必须要满足等式约束h(x)=0，即x的更新要满足，即必须要正交与h的梯度，而要想f(x)的取得最小则更新必须无法再减小f(x)的值，即要满足，即必须要正交与f的梯度，所以最小点处有、平行，即，当然还要满足约束h(x)=0。

不等式约束

不等式约束的情况比等式约束复杂些，分以下两种情况讨论：

最小点处于约束空间之内

此时，不等约束相当于没有约束，此时最小化f(x)，则有；当然，由于最小点可能有多个，仍需不等约束进行过滤，即最小点需满足

最小点不在约束空间之内

由于约束g(x)是个有上界的函数，约束下的最小点必然是在约束的上界处即g(x)=0处（由于此时f与g的梯度方向相反，所以有要求），即不等约束退化为等式约束，同等式约束的分析，即此时有

综合

综合上述两种情况，即有，即KKT条件。

KKT的证明

参考资料

1.

2.

3. .html