[ML Notes] 拉格朗日函数：不等式约束

4 years ago

source link: https://blog.nex3z.com/2021/03/14/ml-notes-%e6%8b%89%e6%a0%bc%e6%9c%97%e6%97%a5%e5%87%bd%e6%95%b0%ef%bc%9a%e4%b8%8d%e7%ad%89%e5%bc%8f%e7%ba%a6%e6%9d%9f/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

[ML Notes] 拉格朗日函数：不等式约束

Author: nex3z 2021-03-14

Contents [show]

1. 直观解释

以二元函数为例，要寻找 f(x,y) 在约束条件 h(x,y)≤0 下的极值，即

minf(x,y)s.t.h(x,y)≤0

令 f(x,y)=x2+y2，h(x,y)=x+y–1，此时的优化问题为

minx2+y2s.t.x+y–1≤0

图 1

如图 1 所示，f(x,y) 在原点取得最小值，而此时约束条件 h(x,y)≤0 包含了原点，因此该约束不生效，只需求解

解得 x=y=0，f(0,0)=0。

优化目标 f(x,y) 不变，令 h(x,y)=x+y+1，此时的优化问题为

minx2+y2s.t.x+y+1≤0

图 2

如图 2 所示，此时 f(x,y) 在其与 h(x,y) 相切处取得极值，约束条件 h(x,y)≤0 相当于 h(x,y)=0，即

minx2+y2s.t.x+y+1=0

使用拉格朗日乘数，求解

{∇f+μ∇g=0h(x,y)=0

解得 x=y=−0.5，f(−0.5,−0.5)=0.5。注意 f 和 h 在切点处的梯度方向相反，应有 μ=−∇f∇h>0。实际上，通过上面的方程组可以解出 μ=1，此时 ∇f∇h=−μ=−1。

2. KKT 条件

对于结合了等式约束 g 和不等式约束 h 的优化问题

minfs.t.gi=0,i=1,2,…,nhi≤0,i=1,2,…,m

综合以上两种情况，可以通过如下方程组，即 KKT 条件（Karush-Kuhn-Tucker condition）来求解

{∇f+n∑i=1λi∇gi+m∑j=1μj∇hj=0(i)gi=0,i=1,2,…,n(ii)hj≤0,j=1,2,…,m(iii)μj≥0,j=1,2,…,m(iv)μjhj=0,j=1,2,…,m(v)

条件 (i) 是优化目标和约束条件的梯度的线性组合；
条件 (ii)、(iii) 是是约束条件本身；
条件 (iv) 结合条件 (v) 存在两种情况：
- 如果 μj=0，此时自然满足 μjhj=0，hi 只需满足约束条件 hj≤0 即可；
- 如果 μj>0，此时在极值点处，不等式约束和目标函数的梯度方向相反，由 μjhj=0，则应有 hj=0，不等式约束变成等式约束。

Recommend