图解数学：拉格朗日松弛方法的直观理解
图解数学：拉格朗日松弛方法的直观理解
拉格朗日松弛方法是运筹学和优化理论中的重要工具，用于解决带约束条件的优化问题。本文通过具体的数学例子和图解，深入浅出地介绍了拉格朗日松弛方法的基本原理和应用，帮助读者直观理解这一复杂概念。
一、一个简单例子
我们先来看一个简单的例子，下面数学规划问题没有约束条件：
$$
\min \quad f(x) = -x^2 + 8x - 10
$$
目标函数图像如下：
在无约束条件下，最大值点在(4, 6)。
下面加上约束条件：
$$
\begin{align*}
\min \quad & f(x) = -x^2 + 8x - 10 \
\text{s.t.} \quad & x - 5 \ge 0
\end{align*}
$$
这时图像如下：
最大值点变成了(5, 5)。显然，在约束条件下，目标函数最大值比无约束条件时变小了。
能否找到一个函数，在无约束条件下的自由极值与数学规划 (2) 相同？这是拉格朗日松弛方法要解决的问题。
二、构造拉格朗日松弛函数
拉格朗日松弛方法的基本思路是，把约束条件作为一个惩罚项与原有目标函数一起构造一个新的无约束目标函数。这个惩罚项的作用是，当约束条件不成立时(即x > 3时)，松弛函数的最大值
- 松弛函数要达成的目标
- 拉格朗日松弛函数的无约束最小值点要满足x - 5 ≥ 0；
- 拉格朗日松弛函数的无约束最小值要与原规划问题保持一致。
- 构造方法
构造下面的拉格朗日松弛函数，λ ≥ 0是待定参数：
$$
L(x, \lambda) = f(x) + \lambda(x - 5)
$$
添加的这个松驰项λ(x - 5)是单调增函数，它让f(x)最大值点向右方向移动，移动的幅度取决于λ。
当λ = 1时，函数图像变化如下。由于移动幅度偏小，导致L(x, λ)的最大值点没有移动到可行解区间，此时的取得的最大值是大于原问题实际最大值(5, 5)的。
当λ = 3时，图像如下：
此时移动幅度过大，也导致松弛函数的最大值比实际问题的最优解要大。
由此可见，我们只需要用λ表示松弛函数的最大值，然后看λ取什么值时，松弛函数的最大值去的最小值即可。求解方法如下：
由(2)、(3)可知：
$$
L(x, \lambda) = f(x) + \lambda(x - 5) = -x^2 + 8x - 10 + \lambda(x - 5)
$$
于是，
$$
\frac{\partial L}{\partial x} = -2x + 8 + \lambda
$$
所以,
$$
x = 4 + \frac{\lambda}{2}
$$
时，松弛函数取得最大值。带入(4)，最大值为：
$$
\max(L(x, \lambda)) = \frac{1}{4}\lambda^2 - \lambda + 6
$$
当
$$
\lambda = 2
$$
时，松弛函数的最大值取得最小值。此时，
$$
x = 5, y = 5
$$
三、最优解不在约束边界上的情形
- 问题
$$
\begin{align*}
\max\quad & f(x)=-x^{3}+3x+1\
s.t. \quad &x \ge 0
\end{align*}
$$
图像如下：
- 松弛函数
$$
L(x, \lambda) = -x^{3}+3x+1+\lambda x
$$
令λ = 0, 0.1, 0.2, 0.3, 0.4，函数图像变化如下：
我觉得λ无论如何变化，都不可能得到无约束条件的松弛函数。看样子拉格朗日松弛方法还需要继续认真学习！
3. 求解
首先，我们明确原问题是一个带约束的优化问题，即：
$$
\begin{align*}
\max \quad & f(x) = -x^3 + 3x + 1 \
s.t. \quad & x \geq 0
\end{align*}
$$
拉格朗日松弛方法通常用于处理约束优化问题，它将约束条件通过拉格朗日乘子加入到目标函数中，从而将有约束优化问题转化为无约束优化问题。
对于这个问题，我们可以定义拉格朗日函数L(x, λ)如下：
$$
L(x, \lambda) = f(x) - \lambda g(x) = -x^3 + 3x + 1 - \lambda (-x)
$$
其中，g(x) = -x是原问题的约束条件x ≥ 0的不等式形式（x ≥ 0等价于-x ≤ 0），λ是拉格朗日乘子，且λ ≥ 0。
现在，我们需要找到L(x, λ)的极值点。为此，我们对L(x, λ)求偏导，并令其为0：
$$
\frac{\partial L}{\partial x} = \frac{d}{dx}(-x^3 + 3x + 1) - \lambda \frac{d}{dx}(-x) = -3x^2 + 3 + \lambda = 0
$$
解这个方程，我们得到：
$$
x^2 = \frac{\lambda + 3}{3}
$$
由于λ ≥ 0，我们可以得出x的可能取值为非负数。
接下来，我们分析拉格朗日乘子的意义。在这个问题中，λ代表了对约束x ≥ 0的“重视程度”。如果λ = 0，则表示约束不起作用，即解在无约束条件下就是最优的。如果λ > 0，则表示约束是有效的，且λ越大，表示约束越重要。
现在，我们需要检查边界条件和可能的极值点来确定全局最大值。由于原函数f(x)是一个三次函数，且系数为负，因此它是一个倒开口的抛物线，在x = 1处有一个极大值点（可以通过求导得出）。同时，我们需要考虑约束条件x ≥ 0。
- 当x < 0时，不在可行域内，因此不考虑。
- 当x = 0时，f(x) = 1。
- 当x = 1时（这是无约束情况下的极值点），f(x) = 3。
- 当x > 1时，函数值将逐渐减小。
综上所述，全局最大值出现在x = 1处，此时f(x) = 3，且满足约束条件x ≥ 0。因此，原问题的最优解是x = 1，最大值为 3。
在这个特定问题中，拉格朗日松弛方法实际上并没有引入新的解，因为原问题的约束条件非常简单（x ≥ 0），且目标函数在可行域内只有一个极值点。然而，在更复杂的问题中，拉格朗日松弛方法可以帮助我们将约束优化问题转化为无约束优化问题，从而简化求解过程。