运筹学基础：拉格朗日松弛方法详解
运筹学基础：拉格朗日松弛方法详解
拉格朗日松弛是运筹学中一种重要的优化方法，主要用于解决带有复杂约束的整数规划问题。通过将难以处理的约束条件转化为目标函数的一部分，可以显著降低问题的求解难度。本文将详细介绍拉格朗日松弛的基本概念、算法流程及其在实际问题中的应用。
基本概念
原问题
考虑如下的整数规划问题：
$$
\begin{align}
\min \quad & c^Tx \
\text{s.t.} \quad & Dx \leq d \tag{1.1}\
& x \in X \tag{1.2}\
& X = {x\in Z^n|Ax\leq b} \tag{1.3}
\end{align}
$$
假设约束（1.1）是难处理的约束，约束（1.3）是容易处理的约束。
松弛问题、拉格朗日乘子、对偶函数
为了减小问题求解的难度，我们自然希望把难约束（1.1）转化到目标函数上去，因此我们定义乘子 $u = (u_1, u_2,...,u_m) \in R^+_m$，然后可得：
$$
\begin{align}
z(u) = \min\quad & c^Tx+u^T(Dx-d) \tag{1.4} \
\text{s.t.} \quad & x\in X \tag{1.5}
\end{align}
$$
我们把上面这个问题称之为松弛问题，$u$ 称为拉格朗日乘子，$z(u)$ 称为对偶函数。
3个注意的地方：
- $u$ 是一个向量，它与被松弛掉的约束的数量是一样的；
- 拉格朗日乘子的符号问题：
- 如果约束是 $\leq$，则拉格朗日乘子要 $\geq 0$，
- 如果约束是 $\geq$，则拉格朗日乘子要 $\leq 0$，
- 如果约束是 $=$，则拉格朗日乘子不受约束限制。
- 对偶函数的输入是拉格朗日乘子，输出是松弛问题的最优值。
对偶问题
我们最大化对偶函数可以得到对偶问题：
$$
\underset{\text{$u \in R^m_+$}}{\max} \quad z(u) \tag{1.6}
$$
其本质是在松弛问题的基础上，搜索能够使得 $z(u)$ 最大的那个 $u$。
三个问题之间的关系
若对偶定义：在原问题（$\min$）中，对偶问题最优解 $\leq$ 原问题最优解。即松弛问题是原问题的一个下界，对偶问题是原问题最大的下界。
为什么要用拉格朗日松弛法
- 拉格朗日松弛后得到的问题的下界要大于等于直接将01整数变量松弛为[0,1]连续变量的下界；
- 如果问题具有linked constraints，那么拉格朗日松弛后可以使问题能够被分解，进而可以降低问题的复杂度；linked constraints指的是将多类变量耦合在一起的约束。
- 采用拉格朗日松弛后我们会得到拉格朗日乘子，它反应了对偶的信息，可以做很多事情。
还不理解
算法流程
- 初始化拉格朗日乘子；
- 求解松弛问题；
- 采用次梯度法更新拉格朗日乘子，并判断是否满足停止条件，若满足则跳到2求解结束，否则跳到2继续。
核心问题
松弛哪个约束
一般来说，尽量松弛掉linked constraints。具体而言，松弛哪个约束需要考虑以下三点：
- 拉格朗日松弛后对偶问题的质量的好坏；
- 拉格朗日松弛的松弛问题后的子问题求解难易程度；
- 拉格朗日松弛对偶问题的求解难易程度。
松弛后分解的子问题的求解
松弛以后的问题分解大概如下图所示：
一般来说，我们希望松弛以后的问题最好不要是NP-hard。一般子问题规模较小，可以直接让求解器求解。
拉格朗日乘子怎么定
该问题等同于：怎么求解拉格朗日松弛问题的对偶问题，常用的方法是次梯度算法（还没有搞清楚，后面再补）。
参考资料
- 拉格朗日松弛求解整数规划浅析
- 整数规划的拉格朗日松弛
- 《运筹优化常用模型、算法及案例实战——Python+Java实现》