带不等式约束的拉格朗日乘数法

在上一篇文章中，我们介绍了拉格朗日乘数法来寻找带有等式约束的函数的局部最小值或局部最大值。同样的方法也可以应用于带有不等式约束的问题。

在本教程中，您将学习如何应用拉格朗日乘数法，在存在不等式约束（可选地，以及等式约束）的情况下，寻找函数的局部最小值或最大值。

完成本教程后，您将了解：

• 如何找到带有等式约束的函数的局部最大值或最小值的点
• 带有等式约束的拉格朗日乘数法

让我们开始吧。

带不等式约束的拉格朗日乘数法
图片由Christine Roy提供，保留部分权利。

先决条件

在本教程中，我们假设您已经回顾了

• 函数的导数
• 多个变量的函数、偏导数和梯度向量
• 优化简介
• 梯度下降

以及

• 拉格朗日乘数法入门

您可以点击上面的链接回顾这些概念。

约束优化和拉格朗日函数

延续我们上一篇文章，约束优化问题通常可以表示为

$$
\begin{aligned}
\min && f(X) \\
\textrm{服从于} && g(X) &= 0 \\
&& h(X) &\ge 0 \\
&& k(X) &\le 0
\end{aligned}
$$

其中 $X$ 是标量或向量值。这里，$g(X)=0$ 是等式约束，而 $h(X)\ge 0$， $k(X)\le 0$ 是不等式约束。请注意，在优化问题中我们总是使用 $\ge$ 和 $\le$ 而不是 $\gt$ 和 $\lt$，因为前者在数学中定义了一个**闭集**，我们应该在该闭集中寻找 $X$ 的值。在优化问题中，每种类型的约束可以有多个。

等式约束易于处理，而不等式约束则不然。因此，一种简化处理的方法是引入**松弛变量**，将不等式转换为等式

$$
\begin{aligned}
\min && f(X) \\
\textrm{服从于} && g(X) &= 0 \\
&& h(X) – s^2 &= 0 \\
&& k(X) + t^2 &= 0
\end{aligned}
$$

当某个量为负时，加上一个特定的正数会使其等于零，反之亦然。这个量就是松弛变量；上面的 $s^2$ 和 $t^2$ 就是例子。我们特意使用 $s^2$ 和 $t^2$ 项来表示它们必须是非负的。

引入松弛变量后，我们可以使用拉格朗日乘数法来解决它，其中拉格朗日函数定义为

$$
L(X, \lambda, \theta, \phi) = f(X) – \lambda g(X) – \theta (h(X)-s^2) + \phi (k(X)+t^2)
$$

需要注意的是，对于问题的最优解 $X^*$，不等式约束要么等式成立（此时松弛变量为零），要么不成立。那些等式成立的不等式约束被称为活跃约束。否则，称为非活跃约束。从这个意义上讲，您可以认为等式约束总是活跃的。

互补松弛条件

我们需要知道约束是否活跃的原因是 Krush-Kuhn-Tucker (KKT) 条件。具体来说，KKT 条件描述了当 $X^*$ 是约束优化问题的最优解时会发生什么

1. 拉格朗日函数的梯度为零
2. 所有约束都得到满足
3. 不等式约束满足互补松弛条件

其中最重要的是互补松弛条件。我们知道带有等式约束的优化问题可以使用拉格朗日乘数法求解，即在最优解处拉格朗日函数的梯度为零，而互补松弛条件将其扩展到不等式约束的情况，即在最优解 $X^*$ 处，要么拉格朗日乘子为零，要么相应的不等式约束是活跃的。

互补松弛条件的使用旨在帮助我们探索解决优化问题时的不同情况。最好通过一个例子来解释。

例1：均值-方差投资组合优化

这是一个金融领域的例子。如果我们有1美元，并进行两种不同的投资，它们的收益被建模为二元高斯分布。我们应该如何分配每种投资的金额，以最小化总收益的方差？

这个优化问题，也被称为马科维茨均值-方差投资组合优化，其公式为

$$
\begin{aligned}
\min && f(w_1, w_2) &= w_1^2\sigma_1^2+w_2^2\sigma_2^2+2w_1w_2\sigma_{12} \\
\textrm{服从于} && w_1+w_2 &= 1 \\
&& w_1 &\ge 0 \\
&& w_1 &\le 1
\end{aligned}
$$

其中最后两个约束将每项投资的权重限制在0到1美元之间。假设 $\sigma_1^2=0.25$， $\sigma_2^2=0.10$， $\sigma_{12} = 0.15$。那么拉格朗日函数定义为

$$
\begin{aligned}
L(w_1,w_2,\lambda,\theta,\phi) =& 0.25w_1^2+0.1w_2^2+0.3w_1w_2 \\
&- \lambda(w_1+w_2-1) \\
&- \theta(w_1-s^2) – \phi(w_1-1+t^2)
\end{aligned}
$$

我们得到梯度

$$
\begin{aligned}
\frac{\partial L}{\partial w_1} &= 0.5w_1+0.3w_2-\lambda-\theta-\phi \\
\frac{\partial L}{\partial w_2} &= 0.2w_2+0.3w_1-\lambda \\
\frac{\partial L}{\partial\lambda} &= 1-w_1-w_2 \\
\frac{\partial L}{\partial\theta} &= s^2-w_1 \\
\frac{\partial L}{\partial\phi} &= 1-w_1-t^2
\end{aligned}
$$

从这一点开始，必须考虑互补松弛条件。我们有两个松弛变量 $s$ 和 $t$，以及相应的拉格朗日乘子 $\theta$ 和 $\phi$。现在我们必须考虑松弛变量是否为零（相应的非等式约束是否活跃）或者拉格朗日乘子是否为零（约束是否不活跃）。有四种可能的情况

1. $\theta=\phi=0$ 且 $s^2>0$， $t^2>0$
2. $\theta\ne 0$ 但 $\phi=0$，且 $s^2=0$， $t^2>0$
3. $\theta=0$ 但 $\phi\ne 0$，且 $s^2>0$， $t^2=0$
4. $\theta\ne 0$ 且 $\phi\ne 0$，且 $s^2=t^2=0$

对于情况1，使用 $\partial L/\partial\lambda=0$、$\partial L/\partial w_1=0$ 和 $\partial L/\partial w_2=0$ 我们得到

$$
\begin{align}
w_2 &= 1-w_1 \\
0.5w_1 + 0.3w_2 &= \lambda \\
0.3w_1 + 0.2w_2 &= \lambda
\end{align}
$$

我们得到 $w_1=-1$， $w_2=2$， $\lambda=0.1$。但是，根据 $\partial L/\partial\theta=0$，我们得到 $s^2=-1$，这无法找到解（$s^2$ 不能为负）。因此，这种情况不可行。

对于情况2，根据 $\partial L/\partial\theta=0$ 我们得到 $w_1=0$。因此，从 $\partial L/\partial\lambda=0$ 我们知道 $w_2=1$。再从 $\partial L/\partial w_2=0$ 我们得到 $\lambda=0.2$，从 $\partial L/\partial w_1$ 我们得到 $\phi=0.1$。在这种情况下，目标函数是 0.1

对于情况3，根据 $\partial L/\partial\phi=0$ 我们得到 $w_1=1$。因此，从 $\partial L/\partial\lambda=0$ 我们知道 $w_2=0$。再从 $\partial L/\partial w_2=0$ 我们得到 $\lambda=0.3$，从 $\partial L/\partial w_1$ 我们得到 $\theta=0.2$。在这种情况下，目标函数是 0.25

对于情况4，我们从 $\partial L/\partial\theta=0$ 得到 $w_1=0$，但从 $\partial L/\partial\phi=0$ 得到 $w_1=1$。因此，这种情况是不可行的。

比较情况2和情况3的目标函数，我们发现情况2的值更低。因此，我们选择情况2作为优化问题的解，最优解在 $w_1=0, w_2=1$ 处达到。

作为练习，您可以尝试将 $\sigma_{12}=-0.15$ 代入上述问题。结果将是当 $w_1=\frac{5}{13}$ 时达到 0.0038，此时两个不等式约束均为非活跃状态。

例2：注水算法

这是一个来自通信工程的例子。如果我们有一个信道（例如，无线带宽），其中噪声功率为 $N$，信号功率为 $S$，则信道容量（以每秒比特数表示）与 $\log_2(1+S/N)$ 成比例。如果我们有 $k$ 个相似的信道，每个信道都有自己的噪声和信号水平，则所有信道的总容量是 $\sum_i \log_2(1+S_i/N_i)$。

假设我们使用一个只能提供1瓦功率的电池，并且这个功率必须分配给 $k$ 个信道（表示为 $p_1,\cdots,p_k$）。每个信道可能有不同的衰减，所以在末端，信号功率会因每个信道的增益 $g_i$ 而折扣。那么，通过使用这 $k$ 个信道可以实现的最大总容量被表述为一个优化问题

$$
\begin{aligned}
\max && f(p_1,\cdots,p_k) &= \sum_{i=1}^k \log_2\left(1+\frac{g_ip_i}{n_i}\right) \\
\textrm{服从于} && \sum_{i=1}^k p_i &= 1 \\
&& p_1,\cdots,p_k &\ge 0 \\
\end{aligned}
$$

为了方便求导，我们注意到 $\log_2x=\log x/\log 2$ 和 $\log(1+g_ip_i/n_i)=\log(n_i+g_ip_i)-\log(n_i)$，因此目标函数可以替换为

$$
f(p_1,\cdots,p_k) = \sum_{i=1}^k \log(n_i+g_ip_i)
$$

假设我们有 $k=3$ 个信道，它们的噪声水平分别为 1.0, 0.9, 1.0，信道增益分别为 0.9, 0.8, 0.7，那么优化问题是

$$
\begin{aligned}
\max && f(p_1,p_2,p_k) &= \log(1+0.9p_1) + \log(0.9+0.8p_2) + \log(1+0.7p_3)\\
\textrm{服从于} && p_1+p_2+p_3 &= 1 \\
&& p_1,p_2,p_3 &\ge 0
\end{aligned}
$$

这里我们有三个不等式约束。拉格朗日函数定义为

$$
\begin{aligned}
& L(p_1,p_2,p_3,\lambda,\theta_1,\theta_2,\theta_3) \\
=\ & \log(1+0.9p_1) + \log(0.9+0.8p_2) + \log(1+0.7p_3) \\
& – \lambda(p_1+p_2+p_3-1) \\
& – \theta_1(p_1-s_1^2) – \theta_2(p_2-s_2^2) – \theta_3(p_3-s_3^2)
\end{aligned}
$$

因此梯度为

$$
\begin{aligned}
\frac{\partial L}{\partial p_1} & = \frac{0.9}{1+0.9p_1}-\lambda-\theta_1 \\
\frac{\partial L}{\partial p_2} & = \frac{0.8}{0.9+0.8p_2}-\lambda-\theta_2 \\
\frac{\partial L}{\partial p_3} & = \frac{0.7}{1+0.7p_3}-\lambda-\theta_3 \\
\frac{\partial L}{\partial\lambda} &= 1-p_1-p_2-p_3 \\
\frac{\partial L}{\partial\theta_1} &= s_1^2-p_1 \\
\frac{\partial L}{\partial\theta_2} &= s_2^2-p_2 \\
\frac{\partial L}{\partial\theta_3} &= s_3^2-p_3 \\
\end{aligned}
$$

但现在我们有3个松弛变量，必须考虑8种情况

1. $\theta_1=\theta_2=\theta_3=0$，因此 $s_1^2,s_2^2,s_3^2$ 均不为零
2. $\theta_1=\theta_2=0$ 但 $\theta_3\ne 0$，因此只有 $s_3^2=0$
3. $\theta_1=\theta_3=0$ 但 $\theta_2\ne 0$，因此只有 $s_2^2=0$
4. $\theta_2=\theta_3=0$ 但 $\theta_1\ne 0$，因此只有 $s_1^2=0$
5. $\theta_1=0$ 但 $\theta_2,\theta_3$ 非零，因此只有 $s_2^2=s_3^2=0$
6. $\theta_2=0$ 但 $\theta_1,\theta_3$ 非零，因此只有 $s_1^2=s_3^2=0$
7. $\theta_3=0$ 但 $\theta_1,\theta_2$ 非零，因此只有 $s_1^2=s_2^2=0$
8. 所有 $\theta_1,\theta_2,\theta_3$ 都非零，因此 $s_1^2=s_2^2=s_3^2=0$

我们可以立即判断情况8是不可行的，因为从 $\partial L/\partial\theta_i=0$ 我们可以得到 $p_1=p_2=p_3=0$，但这无法满足 $\partial L/\partial\lambda=0$。

对于情况1，我们有
$$
\frac{0.9}{1+0.9p_1}=\frac{0.8}{0.9+0.8p_2}=\frac{0.7}{1+0.7p_3}=\lambda
$$
从 $\partial L/\partial p_1=\partial L/\partial p_2=\partial L/\partial p_3=0$ 得到。结合从 $\partial L/\partial\lambda=0$ 得到的 $p_3=1-p_1-p_2$，我们发现解为 $p_1=0.444$， $p_2=0.430$， $p_3=0.126$，目标函数 $f(p_1,p_2,p_3)=0.639$。

对于情况2，从 $\partial L/\partial\theta_3=0$ 我们得到 $p_3=0$。此外，使用从 $\partial L/\partial\lambda=0$ 得到的 $p_2=1-p_1$，以及
$$
\frac{0.9}{1+0.9p_1}=\frac{0.8}{0.9+0.8p_2}=\lambda
$$
从 $\partial L/\partial p_1=\partial L/\partial p_2=0$，我们可以解出 $p_1=0.507$ 和 $p_2=0.493$。目标函数 $f(p_1,p_2,p_3)=0.634$。

同样在情况3中，$p_2=0$，我们解得 $p_1=0.659$ 和 $p_3=0.341$，目标函数 $f(p_1,p_2,p_3)=0.574$。

在情况4中，我们有 $p_1=0$， $p_2=0.652$， $p_3=0.348$，目标函数 $f(p_1,p_2,p_3)=0.570$。

情况5我们有 $p_2=p_3=0$，因此 $p_3=1$。所以目标函数 $f(p_1,p_2,p_3)=0.0.536$。

同样，在情况6和情况7中，我们分别有 $p_2=1$ 和 $p_1=1$。目标函数分别达到 0.531 和 0.425。

比较所有这些情况，我们发现在情况1中目标函数达到了最大值。因此，这个优化问题的解是
$p_1=0.444$, $p_2=0.430$, $p_3=0.126$，且 $f(p_1,p_2,p_3)=0.639$。

扩展和进一步阅读

虽然在上述例子中，我们将松弛变量引入了拉格朗日函数，但有些书籍可能更倾向于不添加松弛变量，而是将不等式约束的拉格朗日乘子限制为正。在这种情况下，您可能会看到拉格朗日函数写为

$$
L(X, \lambda, \theta, \phi) = f(X) – \lambda g(X) – \theta h(X) + \phi k(X)
$$

但要求 $\theta\ge 0;\phi\ge 0$。

拉格朗日函数也适用于对偶方法来寻找最大值或最小值。如果目标函数或约束是非线性的，这种方法尤其有用，因为在这种情况下可能不容易找到解。

一些涵盖此主题的书籍有

• 凸优化，作者：Stephen Boyd 和 Lieven Vandenberghe，2004年
• 《深度学习》第四章，作者：Ian Goodfellow 等人，2016年

总结

在本教程中，您学习了如何将拉格朗日乘数法应用于不等式约束。具体来说，您学到了

• 存在不等式约束时的拉格朗日乘数和拉格朗日函数
• 如何使用KKT条件解决给定不等式约束的优化问题

掌握机器学习微积分！

通过微积分概念变得更聪明

...通过更好地理解微积分的符号和术语

在我的新电子书中探索如何实现
机器学习微积分

它提供**自学教程**，并附有关于以下内容的**完整工作代码**：
微分、梯度、拉格朗日乘子法、雅可比矩阵等等...

将恰到好处的微积分知识带到
您的机器学习项目

查看内容