[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。

对于结合了等式约束 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，不等式约束变成等式约束。