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

1. 直观解释

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

$$
\begin{aligned}
\min \; & f(x, y) \\
\mathrm{s.t.} \; & h(x, y) \leq 0
\end{aligned} \tag{1}
$$

  令 $f(x, y) = x^2 + y^2$,$h(x, y) = x + y – 1$,此时的优化问题为

$$
\begin{aligned}
\min \; & x^2 + y^2 \\
\mathrm{s.t.} \; & x + y – 1 \leq 0
\end{aligned}
$$

图 1
图 1

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

$$
\nabla f = 0
$$

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

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

$$
\begin{aligned}
\min \; & x^2 + y^2 \\
\mathrm{s.t.} \; & x + y + 1 \leq 0
\end{aligned}
$$

图 2
图 2

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

$$
\begin{aligned}
\min \; & x^2 + y^2 \\
\mathrm{s.t.} \; & x + y + 1 = 0
\end{aligned}
$$

使用拉格朗日乘数,求解

$$
\begin{cases}
\nabla f + \mu \nabla g = \boldsymbol 0 \\
h(x, y) = 0
\end{cases}
$$

解得 $x = y = -0.5$,$f(-0.5, -0.5) = 0.5$。注意 $f$ 和 $h$ 在切点处的梯度方向相反,应有 $\mu = -\frac{\nabla f}{\nabla h} > 0$。实际上,通过上面的方程组可以解出 $\mu = 1$,此时 $\frac{\nabla f}{\nabla h} = -\mu = -1$。

2. KKT 条件

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

$$
\begin{aligned}
\min \; & f \\
\mathrm{s.t.} \; & g_i = 0, \;\; i = 1, 2, \dots, n \\
& h_i \leq 0, \;\; i = 1, 2, \dots, m
\end{aligned} \tag{2}
$$

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

$$
\begin{aligned}
\begin{cases}
\nabla f + \sum\limits_{i=1}^n \lambda_i \nabla g_i + \sum\limits_{j=1}^m \mu_j \nabla h_j = 0 \qquad & (i)\\
g_i = 0, \;\; i = 1, 2, \dots, n & (ii)\\
h_j \leq 0, \;\; j = 1, 2, \dots, m & (iii)\\
\mu_j \geq 0, \;\; j = 1, 2, \dots, m & (iv)\\
\mu_j h_j = 0, \;\; j = 1, 2, \dots, m & (v)
\end{cases}
\end{aligned} \tag{3}
$$

其中:

  • 条件 $(i)$ 是优化目标和约束条件的梯度的线性组合;
  • 条件 $(ii)$、$(iii)$ 是是约束条件本身;
  • 条件 $(iv)$ 结合条件 $(v)$ 存在两种情况:
    • 如果 $\mu_j = 0$,此时自然满足 $\mu_j h_j = 0$,$h_i$ 只需满足约束条件 $h_j \leq 0$ 即可;
    • 如果 $\mu_j > 0$,此时在极值点处,不等式约束和目标函数的梯度方向相反,由 $\mu_j h_j = 0$,则应有 $h_j = 0$,不等式约束变成等式约束。