最优化笔记:有约束优化,拉格朗日乘子的意义,KKT条件

发布于:2021-10-21 18:17:48



有约束优化,拉格朗日乘子的意义,KKT条件
拉格朗日乘子法的引入KKT条件多个约束条件的情况



拉格朗日乘子法的引入

一个典型的带约束条件优化问题:





m


i



n


x



f


(


x


)



min_xf(x)


minx?f(x)




s


.


t


.


g


(


x


)


=


0



s.t. g(x)=0


s.t.g(x)=0





x



x


x为二维变量为例,设:




f


(


x


,


y


)


=


d



f(x,y)=d


f(x,y)=d,




g


(


x


,


y


)


=


c



g(x,y)=c


g(x,y)=c,如下图:

由图中可以看得出来,椭圆形的




f


(


x


,


y


)



f(x,y)


f(x,y)符合约束条件的最小值在椭圆与红色曲线的切线处,在切线相交处两边的法向量刚好互为相反,即:

由此引入拉格朗日函数:


KKT条件

以上是




g


(


x


,


y


)


=


0



g(x,y)=0


g(x,y)=0的条件,下面是




g


(


x


,


y


)


<


=


0



g(x,y)<=0


g(x,y)<=0的情况,
在不等式情况下,要求




λ


g


(



x


?



,



y


?



)


=


0



lambda g(x^*,y^*)=0


λg(x?,y?)=0的约束,此即KKT条件。


下图阴影部分即




g


(


x


,


y


)


<


0



g(x,y)<0


g(x,y)<0的情况,依据等式




λ


g


(



x


?



,



y


?



)


=


0



lambda g(x^*,y^*)=0


λg(x?,y?)=0,当




g


(


x


,


y


)


<


0



g(x,y)<0


g(x,y)<0时得




λ


=


0



lambda=0


λ=0意味着约束条件不起作用,此时的优化问题等同于无约束优化。
而在




g


(


x


,


y


)


=


0



g(x,y)=0


g(x,y)=0时,一般情况下




λ



lambda


λ不等于0,此时




x


,


y



x,y


x,y的值落在曲线边界上,意味着约束条件起作用。
KKT的本质意义是帮助我们去理解哪些约束条件是真正起作用的。



多个约束条件的情况

最小化




f


(


x


)



f(x)


f(x),多个约束条件





g


i



(


x


)


>


=


0



g_i(x)>=0


gi?(x)>=0

此时拉格朗日函数写作:






x



x


x求导得方程:





?


f


(


x


)


=







i


=


1



N




λ


i



?



g


i



(


x


)




abla f(x)=sum_{i=1}^Nlambda_i
abla g_i(x)


?f(x)=i=1∑N?λi??gi?(x)




K


K


T












λ


i



?



g


i



(


x


)


=


0



KKT条件:lambda_i
abla g_i(x) =0


KKT条件:λi??gi?(x)=0

相关推荐

最新更新

猜你喜欢