拉格朗日松弛 (I) - 理论与算法
目录
- 背景
- 拉格朗日松弛——理论
- 拉格朗日松弛——算法
- 次梯度优化算法
- 拉格朗日松弛启发式算法
- 参考资料
背景
Marshall L.Fisher在1981年发表在《Management Science》上的《The Lagrangian Relaxation Method for Solving Integer Programming Problems》1在2004年被评为“《Management Science》首个50年中十大最具影响力的主题之一”。
在中国知网中，以“拉格朗日松弛”作为关键词在“篇关摘”选项下检索，并对结果进行计量可视化分析可得到如下的图表。
从发文量这一指标可以看到，近10年涉及这一方法的论文显著增多。
从主要主题分布、次要主题分布中可以看到，在理论层面，该方法与动态规划、整数规划、凸优化和启发式算法等知识都有较为紧密的联系。在应用层面，该方法在机组组合、资源分配、调度、供应链和设施选址等领域都有应用。
拉格朗日松弛——理论
理论和算法部分内容参考资料2进行介绍，主要介绍拉格朗日松弛的思想、重要结论和拉格朗日松弛算法，结论的证明和更多内容可参考该书。除此之外，本文也吸纳了网上其他相关资料，帮助读者理解。
松弛的意思即为放松约束，对于一个标准化为求最小值的优化问题，放松约束会使得有可能得到目标函数值更小的解，换言之，松弛可以求得原问题的一个下界，这为评价其他算法的有效性提供了一种途径，也为原问题的求解提供了更多信息。
该方法常用在整数规划和混合整数规划中。
松弛方法主要有以下四种：线性规划松弛（将整数约束松弛至实数约束）、对偶规划松弛（求解对偶规划，根据弱对偶定理，求 max \text{max} max 的对偶问题提供了求 min \text{min} min 的原问题的一个下界）、代理松弛（通过组合多个约束减少约束的数量，如相加）和拉格朗日松弛。本篇博文介绍拉格朗日松弛。
拉格朗日松弛方法的基本原理：将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性，使得变换后的问题可以在多项式时间求解或者尽管不能在多项式时间求解但由于规模较小而可以快速求解3，从而为原问题的求解提供帮助。
如上图4所示（细线红框中应为 “ ≥ \ge ≥” 和 “ ≤ \le ≤” ，粗线红框中应为“lower”，“lower bound”表示下界），假设一个问题的约束可以分为两部分，即图中的 A A A 和 D D D（ D 1 D_1 D1、 D 2 D_2 D2、 D 3 D_3 D3），它们的区别是 D D D 只和某一部分变量有关，而 A A A 和所有变量都有关，则 A A A 就是上面所说的“造成问题难的约束”（也称复杂约束）。拉格朗日松弛就是将这个复杂约束放到了目标函数中。关于 λ \lambda λ 为什么要求非负，可参见5。下图6可以帮助理解。
进一步地，已知拉格朗日松弛后的目标函数值
z
L
R
z_{LR}
zLR 是原问题目标函数值
z
z
z 的一个下界，由于需要尽可能地接近原问题的目标函数值，故可以对松弛后的问题
z
L
R
z_{LR}
zLR 关于
λ
λ
λ 求最大值（构成对偶问题，Dual Problem），得到的是所有下界中的最佳值
z
L
D
z_{LD}
zLD（下图4红框中应为
z
L
D
z_{LD}
zLD ）。
拉格朗日松弛的用途如下6。
以上是拉格朗日松弛的基础理论，下面介绍一些常见的变形。
首先是等式约束的松弛。这里和“线性规划对偶问题中等式约束对应的对偶变量没有符号限制”以及“库恩-塔克条件（KKT条件）中等式约束对应的系数没有符号限制”的原理完全相同，等式约束松弛对应的系数也没有符号限制（两个非负的系数相减得到一个没有符号限制的系数）。
其次是拉格朗日分解。回顾上述问题4，不妨设
n
=
3
n=3
n=3 ，与下面的示意图保持一致。
则将松弛后的问题目标函数中的
x
x
x 按照
x
1
x_1
x1、
x
2
x_2
x2 和
x
3
x_3
x3 分解可以等价变换为如下的问题。
z
L
R
(
λ
)
=
minimize
c
1
T
x
1
+
c
2
T
x
2
+
c
3
T
x
3
+
λ
T
(
A
1
x
1
+
A
2
x
2
+
A
3
x
3
−
b
)
subject to
D
1
T
x
1
≤
e
1
D
2
T
x
2
≤
e
2
D
3
T
x
3
≤
e
3
x
1
,
x
2
,
x
3
∈
Z
+
n
\begin{array}{ll} z_{LR}(\lambda)=\text{minimize} & c_1^T x_1 +c_2^T x_2+c_3^T x_3+\lambda^T(A_1x_1+A_2x_2+A_3x_3-b) \\ \text{subject to} & D_1^T x_1 \le e_1 \\ & D_2^T x_2 \le e_2 \\ & D_3^T x_3 \le e_3 \\ & x_1, x_2, x_3 \in \Bbb{Z^n_+} \end{array}
zLR(λ)=minimizesubject toc1Tx1+c2Tx2+c3Tx3+λT(A1x1+A2x2+A3x3−b)D1Tx1≤e1D2Tx2≤e2D3Tx3≤e3x1,x2,x3∈Z+n进一步可将上述问题按照按照
x
1
x_1
x1、
x
2
x_2
x2 和
x
3
x_3
x3 分解为三个子问题，由于目标函数和约束都是关于
x
1
x_1
x1、
x
2
x_2
x2 和
x
3
x_3
x3 可分的，故这一步是等价变换。
子问题一：
上一篇：
853.限制边数的最短路线
下一篇：
UE4 笔记_修改用户界面并添加新功能
z
L
R
1
(
λ
)
=
minimize
c
1
T
x
1
+
λ
T
(
A
1
x
1
−
b
)
subject to
D
1
T
x
1
≤
e
1
x
1
∈
Z
+
n
\begin{array}{ll} z_{LR1}(\lambda)=\text{minimize} & c_1^T x_1+\lambda^T(A_1x_1-b) \\ \text{subject to} & D_1^T x_1 \le e_1 \\ & x _1\in \Bbb{Z^n_+} \end{array}
zLR1(λ)=minimizesubject toc1Tx1+λT(A1x1−b)D