拉格朗日松弛算法求解整数规划的基本原理

声明：

• 原文之前发表在本人的CSDN上，现搬运到博客里。
• 本文的目的是记录和分享学到的知识。作者已尽一切努力确保本文内容的准确性。作者在此声明不承担因本文中的错误或遗漏造成的任何损失所带来的责任，无论这些错误或遗漏是意外、疏忽或其他原因导致的。
• 转载请备注来源，欢迎点赞、收藏或指出本文不足。
• 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
• 本文链接：https://blog.csdn.net/weixin_45746917/article/details/125524606

本文由作者用心整理，希望对您有所帮助。如果您入门或困扰于该问题，请您静下心来阅读，准备纸笔推导，一定会有所收获。所有例子和引证均带有来源，可点超链接深入了解。

概述

  拉格朗日松弛是一种求解整数规划的、基于优化的启发式算法。该算法能提供较为优质的解，可证明解的质量（可得到优化上下界），但不保证最优性。拉格朗日松弛的应用十分广泛，例如无容量限制的设施选址问题（该问题为NP-hard问题）。
  拉格朗日松弛算法可追溯到Everett 1963年，Fisher 1973使用了该算法求解了调度问题。注意，该算法并不是拉格朗日提出的，是借鉴了拉格朗日乘子法的一些启示，由(Geoffrion 1974)命名。

• 松弛方法对于一个优化问题十分重要，因为这种方法为最优值提供了“上下界限”。

• 松弛就是把一个问题的约束变弱，这样可行域就大了，也能方便求解了。

• 最小化问题中，松弛问题的最优值是下界。最大化问题是上界。

• 松弛技术的精髓就是设计一个容易求解的松弛问题并得到一个优质的“界”。

链接: Everett 1963

链接: Fisher 1973

从拉格朗日乘子法开始

  微积分中，一类问题是求解一个函数的极大值或者极小值。当这个函数受限于另一个函数的时候，问题求解将变得困难。详见同济版《高等数学 下》（高等教育出版社）多元函数的极值及其求法——条件极值 拉格朗日乘数法。

维基百科的一个例子

  参见维基百科。
  求函数$f(x,y)$的极值，且要求满足条件$g(x,y)=c$。
  这里简单描述一下原理和证明过程，详细证明参见引用来源。假设$f(x,y)$的取值为$d_n$，注意$d_n$是随$x$和$y$的值变化的。只有$f(x,y)=d_n$和$g(x,y)=c$相切时，同时沿着有$f(x,y)=d_n$和$g(x,y)=c$的方向前进，在这种情况下，会出现极值。
  由于二者是相切关系，那么二者的梯度满足如下关系：（切线、法线、梯度的关系）

$$\nabla f(x,y) = -\lambda \nabla (g(x,y)-c)$$

于是，有

$$\nabla[f(x,y) + \lambda (g(x,y)-c)]=0\\$$

  这样，如果求出了$\lambda$的值，带到$F(x,y,\lambda)=f(x,y) + \lambda(g(x,y)-c)$中，就能求出无约束条件下的极值和对应的极值点。$F(x,y,\lambda)$和$f(x,y)$在极值点处相等。极值点处，$\nabla F(x,y,\lambda)=0$，且$\frac{\partial F}{\partial \lambda}=g(x,y)-c$，$g(x,y)-c=0$​，所以极值点处有$F(x,y,\lambda)=f(x,y)$。

同济版第7版《高等数学 下》的例子

  第九章p117给出了更详细的证明，这里直接给出结论：要找$z=f(x,y)$在附加条件$\phi (x,y)=0$下的可能极值点，可做拉格朗日函数:

$$L(x,y) = f(x,y) + \lambda \phi(x,y)$$

其中$\lambda$为参数，然后求$L$对$x,y,\lambda$的一阶偏导，并令其为0，将这个三个等式联立。方程组求解得到的解$(x,y)$就是$f(x,y)$可能的极值点。

整数规划拉格朗日松弛

问题构建

  给定一个待求解的整数规划问题（$P$）：

$$\begin{aligned} Z=& \min c x \\ \text { s.t. } & A x=b \\ & D x \leq e \\ & x \geq 0 \text { and integral } \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{P}\right)$$

  我们松弛其整数约束，得到$LP$问题：

$$\begin{aligned} Z=& \min c x \\ \text { s.t. } & A x=b \\ & D x \leq e \\ & x \geq 0 \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{LP}\right)$$

  我们松弛第一个等于约束，得到一个松弛后的拉格朗日问题（$LR_u$）,其中$u=\{u_1,u_2,...u_m\}$是拉格朗日乘子。

$$\begin{aligned} Z_D(u)=& \min c x + u(Ax-b) \\ \text { s.t. } & D x \leq e \\ & x \geq 0 \text { and integral } \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{LR_u}\right)$$

  设$x^*$是$P$问题的最优解，此时，有：

$$Z_D(u)= {\rm{min}}\,cx + u(Ax-b)\le cx^*+u(Ax^*-b) = cx^* = Z$$

  这说明，$Z_D(u)$的值一定小于等于$Z$的值。不等号的来源是松弛，因为$LR_u$比$P$的约束更少，所以$LR_u$的最优解一定小于等于把$x^*$直接带入$LR_u$得到的目标函数值。由于在$P$中，$Ax^* =b$，所以$cx^*+u(Ax^*-b) = cx^* = Z$。
  如果$Ax=b$的约束变成了$Ax\le b$，则需要求$u\ge 0$，如果$Ax=b$的约束变成了$Ax\ge b$，则需要求$u\le 0$。
  总之，不管怎么样，$Z_D(u)\le Z$在一定条件下成立，即$Z_D(u)$小于等于原问题的最优目标函数值。

乘子$u$取值

拉格朗日对偶问题${D}$

   首先，应明确在$u$的特定取值下，$Z_D(u)$可以等于$Z$。此时，这个问题就变成了跟$u$相关的问题。如何给$u$取值，使得$Z_D(u)$尽可能取最大值以接近$Z$的问题，称作拉格朗日对偶问题$D$，即：

$$Z_D = \max _u Z_D(u) \tag{D}$$

该问题的决策变量是$u$，目标函数是最大化$Z_D(u)$的值。也就是说，求解原问题$P$的最小化目标函数值$Z$已经转换成求解拉格朗日对偶问题$D$的目标函数值$Z_D(u)$了。

   那么问题来了，拉格朗日对偶问题的形式很抽象，我们如何具象描述它呢？

拉格朗日对偶重构问题$\bar{D}$

   假设拉格朗日松弛$LR_u$的可行解集$X=\{x|Dx\le e ,x\ge 0 \text{ and integer}\}$是有限集，则我们可以令$X=\{x^t,t=1,...,T\}$。

这样，问题$D$可重构为$\bar{D}$：

$$\begin{aligned} Z_D&=\quad {\rm{max}}\,w\\ \text{s.t.}\quad w &\le cx^t + u(Ax^t-b),t=1,...,T\\ \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{\bar{D}}\right)$$

问：为什么可以这样重构?

*答：令$w=Z_D(u)$，问题$D$想求$Z_D(u)$关于$u$的最大值，所以$\bar{D}$的目标函数是求最大值。$Z_D(u)$是最小化$c x + u(Ax-b)$，那么$Z_D(u)$一定小于等于$LR_u$的任意一个可行解$x^t$带入该表达式的值，即

$$\min c x + u(Ax-b) = Z_D(u) = w \le cx^t + u(Ax^t-b)$$

当$x^t$是$LR_u$问题的最优解时等号成立。*

拉格朗日对偶重构问题的线性规划对偶$\bar{P}$

  这时，再求$\bar{D}$的线性规划对偶$\bar{P}$

$$\begin{aligned} Z_{D}=& \min \sum_{t=1}^{T} \lambda_{t} c x^{t} \\ \text { s.t. } & \sum_{t=1}^{T} \lambda_{t} A x^{t}=b \\ & \sum_{t=1}^{T} \lambda_{t}=1 \\ & \lambda_{t} \geq 0, t=1, \ldots, T \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{\bar{P}}\right)$$

  对偶推导：从$\bar{P}$向$\bar{D}$推导，把$b$分解成凸组合；从$\bar{D}$向$\bar{P}$推导，把$w$看成$1w+0u$，其中$w$和$u$是无约束的决策变量。

  虽然$\bar{P}$和$LP$不是等价问题，即$\bar{P}$并不是原问题$P$的线性松弛版本，但是当$\lambda_t$是整数（0或1）时，$\bar{P}$等价于$P$。理由如下：$x^t$是$LR_u$的可行解，一定满足约束$Dx\le e$。既然满足了这个约束，在所有的可行解中，也肯定存在一个$x^t$满足$Ax^t=b$，那么令对应的$\lambda _t$等于1即可。（满足条件a的所有解中，一定有一个解同时满足a和b，子集关系）

拉格朗日对偶重构问题$\bar{D}$的意义

  问题$\bar{D}$表明，$Z_D(u)$是一系列线性函数的下限值。为了方便理解，假设$x$的变量数只有一个，$T=4$表示对于问题$LR_u$仅有4个可行解。那么，$Z_D(u)$随$u$变化的图像如图所示：

  在这个图中，$x^t$是已知的，是常数，那么得到了四个关于$u$的线性函数。取这些函数在$u$不同取值的最小值，即为函数$Z_D(u)$，如图中加粗线条所示。

  我们发现，$Z_D(u)$是连续的，是凹函数（参照国际定义）。这样找最大值就很简单，比如，我们使用爬山算法，但是我们不能求导，因为最优点处不可导。

  既然不可导，那就用次梯度法。

次梯度法

次梯度概念

   满足如下公式的 $y$ 值为 $Z_D(u)$ 在 $\bar{u}$ 处的次梯度。

$$y(u-\bar{u}) \ge Z_D(u) - Z_D(u), \forall u$$

次梯度性质

• 向量$Ax^t-b$在$x^t$求解 $LR_u$ 对应位置的次梯度。其余的次梯度都是这些“基础”次梯度的凸组合。
• 当且仅当$u^*$和$\lambda^*$是可行的且满足互补松弛定理时，$u^*$是$\bar{D}$的最优解且$\lambda^*$是$\bar{P}$的最优解，这等价于当且仅当$Z_D(u)$ 在 $u^*$ 处的次梯度为0时，$u^*$是$D$的最优解。（说白了就是$Z_D(u)$取到了关于$u$的最大值）

次梯度法更新乘子

   给定一个初始的乘子值 $u^0$，后续乘子第$k$次迭代的值为$u^k$，迭代公式如下：

$$u^{k+1} = u^{k} + t_k(Ax^k-b)$$

其中$x^k$是$(LR_{u^k})$的最优解，$t_k$是一个正数，称为迭代步长。

Goffin (1977)表明：

当$t_k→0$且$\sum_{i=0}^kt_i=0$时，$Z_D(u^k)→Z_D$。

   常用的迭代步长公式为：

$$t_k = \frac{\lambda_k(Z^*-Z_D(u^k))} {||Ax^k-b||^2}$$

其中，$\lambda_k$是一个$(0,2]$之间的标量，$Z^*$是$Z_D$的上界，且使用启发式修改为$P$的可行解。通常，$\lambda_k$的初始值设置为2，当一定迭代次数后，$Z_D(u)$的值仍未增加，$\lambda_k$的值减半。

   注意，这是一个经验性的方法，并不一定能满足最优收敛。

总结

上述的内容只是一个方法论，我们想求解一个问题，还是面临很多的困难的。具体的问题需要具体的分析，包含但不限于松弛哪个约束、获取上界的启发式方法、算法参数的调整等。具体的例子，可参考本人的硕士毕设（在github仓库中）使用拉格朗日松弛求解了一个选址问题。