最优化问题及KKT条件的几何理解

以二维空间$R^2$举例,从简单的无约束优化(0梯度条件),到等式约束优化(拉格朗日条件),再到不等式约束优化(KKT条件)解析优化问题解法的几何意义。

无约束优化问题

$\min f(x)$,其中,$x=(x_1,x_2)$

此时,对于$f(x)$的局部极小值点(红点)处梯度必然为0.因此优化问题可以转化为求解梯度为0的点。

带等式约束的优化问题

$\min f(x)$,其中,$x=(x_1,x_2)$

$s.t. h(x)=0$

与无约束问题不同,此时极小值点被限制在曲线$h(x)=0$上,我们因此将$\{x|h(x)=0\}$成为可行域,解只能在这个可行域里面取。如下图所示,曲线$h(x)=0$(黑色实线)便是可行域,现在要求在可行域上面的极小点。可以想象从无约束问题的极小点(黑点)靠等高线向外扩展,当扩展等高线第一次接触可行域时候(相切,梯度方向相反)的交点便是可行域的极小点。所以,相切,梯度方向相反,是取得极小值点的必要条件。

补充:能够碰到极大极小值点的必要条件是:梯度场与切空间垂直,也就是梯度场不能够有任何流形切空间上的分量,否则在切空间方向有分量,在流形上沿分量方向走,函数值会增加,沿反方向走,函数值会减少,不可能为局部极小或者极大值点。

两条曲线相切,梯度方向相反,即梯度差一个任意的常数乘子(取为$-\lambda$):$\nabla f(x)=-\lambda \nabla h(x)$,调整后即可得到拉格朗日条件$\nabla (f(x)+\lambda h(x))=0$.

如此,带等式约束的优化问题转化为了无约束的优化问题,只需要对拉格朗日条件解方程组即可。这里$\lambda$便是拉格朗日乘子,有多少个等式约束就有多少个拉格朗日乘子。

带不等式约束的优化问题

只有一个不等式起作用时

$\min f(x)$

$s.t. h(x)\le0$

当只有一个不等式起作用时,如下图所示,可行域变成了阴影部分,最小值点还是切点,跟等式约束条件完全一样,只需要把不等号当做等号去求解即可。

两个及以上不等式起作用时

$\min f(x)$

$s.t.$

$g_1(x)\le0$

$g_2(x)\le0$

如下图,当$f(x)$等高线慢慢扩大时,等高线与可行域(阴影部分)第一次相遇的点是个顶点,2个不等式同时起作用。满足最小值点从原来黑点的位置(切点)移动到了红点的位置,现在跟哪条约束函数都不相切了。这时候就需要用到KKt条件了。这里的条件是指:某一个点它如果是最小值点的话,就必须满足这个条件(在含不等式约束的优化问题里)。这是个必要条件,前面说的也全部是必要条件

这个问题的解$x^*$应满足的KKT(卡罗需-库恩-塔克)条件为:

$1. \mu_1\ge0, \mu_2\ge0;$

$2. \nabla f(x^¥)+\mu_1\nabla g_1(x^¥)+\mu_2\nabla g_2(x^¥)=0;$

$3. \mu_1g_1(x^¥)+\mu_2g_2(x^¥)=0$

其中,$\mu$叫做KKT乘子,有多少个不等式约束就有多少个KKT乘子。加上本问题中的约束不封,就是完整版的KKT条件。对于有等式的情况:把其中一个不等式约束换成等式,可行域变成了半条曲线,最小值还是小红点,情况是一样的。

接下来看看KKT条件的几何意义。上图中绿色箭头为两条曲线的负梯度方向,红色箭头为等高线的梯度方向。如果这个顶点为满足约束的最小值点,那么该点处等高线梯度(红色箭头)一定在两个绿色箭头之间($-\nabla g(x)$方向(绿色箭头)一定指向$g(x)$减小方向,即$g(x)\lt0$一边)

$\mu_1\ge0,\mu_2\ge0$(红色箭头一定在绿色箭头之间)的解释:若三个向量的位置如下图所示,即$-\nabla f(x)$落在$\nabla g_1,\nabla g_2$所形成的锥形区域外侧。此时,作等高线(等值线)在点$x^k$处的切平面,可以发现:沿着与扶梯度$-\nabla f(x)$成锐角方向移动,只要能在红色阴影(阴影左界为当前等高线)取值,$f(x)$总能减小,而红色阴影区域为可行域,因此既可以建系哦啊目标函数值,又不破坏约束条件,所以当前$x^k$不是最优点。

有些不等式约束不起作用时

如下面这个优化问题:

$\min f(x)$

$s.t.$

$g_1(x)\le0$

$g_2(x)\le0$

$g_3(x)\le0$

如下图$g_3(x)\le0$是不起作用的

对于最小值点$x^*$,三个不等式约束的不同在于:

$g_1(x^¥)=0$(起作用)

$g_2(x^¥)=0$(起作用)

$g_3(x^¥)\lt0$(不起作用,最小值点不在$g_3(x)=0$上)

此时KKT条件1,2变为:

$1. \mu_1\ge0, \mu_2\ge0, \mu_3\ge0, $

$2. \nabla f(x^¥)+\mu_1\nabla g_1(x^¥)+\mu_2\nabla g_2(x^¥)+\mu_3\nabla g_3(x^¥)=0$

条件2中的$\mu_3\nabla g_3(x^¥)$让我们很苦恼,$g_3(x¥)$约束根本不起作用,要是能令$\mu_3=0$就好了。加上条件3:

$3. \mu_1g_1(x^¥)+\mu_2g_2(x^¥)+\mu_3g_3(x^¥)=0$

恰好能使$\mu_3=0​$。由于$g_1(x^¥)=0, g_2(x^¥)=0​$,所以前两项等于0,第三项$g_3(x^¥)\lt0​$,在条件3的作用下使得$\mu_3=0​$。正好满足哟啊求。如果再多几项不起作用的不等式约束,条件2都能在条件3的作用下实现:目标函数$f(x)​$的梯度$\nabla f(x)​$被起作用的不等式约束函数$g(x)​$的负梯度$-\nabla g(x)​$线性标出且系数$\mu​$全部非负(红色箭头被绿色箭头夹在中间)。这样,优化问题的求解就变成了对所有KKT条件解方程组。

如果再定义一个拉格朗日函数:

$L(x,\mu)=f(x)+\mu_1g_1(x)+\mu_2g_2(x)+…$

令它对$x$的偏导为0,就是KKT条件中的条件2了。

注意:以上所有都是局部极小值的点必要条件。据此求得的解不一定是局部极小值点(更别提全局),原因是上图中所画的等高线也许根本就不闭合,也急速实说我们一直想靠近的等高线和中间的黑点可能压根就是个鞍点或者近似鞍点。

0%