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