拉格朗日乘子法

拉格朗日乘子法及KKT条件

Posted by ZhY on April 27, 2017

拉格朗日乘子法

拉格朗日乘子法和KKT条件时求解约束优化问题的重要方法,在有等式的约束情况下使用拉格朗日乘子法,在有不等式约束情况下使用KKT条件

前提: 只有当目标函数为凸函数时,使用这两种方法才能保证求得的时最优解。

转换为

其中系数称为拉格朗日乘子。

为什么可以这样做呢?

首先来看一个二维的优化问题:

我们可以画图来辅助思考

其中绿线标出的时约束g(x,y)=c的轨迹,蓝线是f的等高线。箭头表示斜率。

从图上可以看出,在最优解处,f和g的斜率平行。

一旦求出的值,即可求出极值的对应点。

因为在到达极值的时候,为零。因此在到达极值时与相等。

因此,对中的,,求一节偏导,可求出的驻点。如果这个实际问题的最大或最小值存在,一般来说驻点唯一,因此若只求出一个驻点,则该驻点即为极值点。

例如

则我们可以将其化为拉格朗日函数 ,则:

上面三个式子联立可得

可以得出

KKT条件

KKT条件是解决不等式约束的方法。

转化为

应满足:

1)

2)

3) ,