从代码学习数学优化算法 - 拉格朗日松弛 Python版

前言

在运筹学和组合优化的世界里，我们经常遇到一些“棘手”的问题，这些问题因为其内在的组合复杂性（例如整数变量、非线性约束等）而难以直接求解。拉格朗日松弛（Lagrangian Relaxation）是一种强大的技术，它通过将这些“复杂”约束暂时“松弛”掉，并将其以惩罚项的形式移入目标函数，从而将原问题转化为一个相对容易求解的子问题（拉格朗日松弛子问题）。

这个子问题的最优解为原问题提供了一个界限（对于最大化问题是上界，最小化问题是下界）。然后，通过迭代调整与被松弛约束相关的拉格朗日乘子，我们可以逐步逼近这个界限的最优值，这个过程就是求解拉格朗日对偶问题。

本篇博客将通过一个具体的0-1整数规划例子，结合 Python 代码实现，带您一步步了解拉格朗日松弛的基本原理、子问题的求解以及经典的次梯度优化方法来更新拉格朗日乘子。让我们从代码中学习，揭开拉格朗日松弛的神秘面纱！

完整代码：下载链接

1. 问题定义 (Problem Definition)

我们将考虑以下形式的优化问题：
最大化 $c^{T}x$
约束于：
$Ax\le b$ (复杂约束)
$Dx\le e$ (简单约束，例如 x i ∈ { 0 , 1 } x_i \in \{0,1\} xi​∈{ 0,1} 或 $x$ 属于某个单纯形)

我们感兴趣的是那些如果忽略 $Ax\le b$ 约束（或将其整合到目标函数中）就很容易解决的问题。例如，如果 $Dx\le e$ 表示 x i ∈ { 0 , 1 } x_i \in \{0,1\} xi​∈{ 0,1}，那么问题就很容易解决。

这里，我们考虑以下 0-1 整数规划问题（示例）：
最大化 $12x_1+8x_2+7x_3+6x_4+10x_5+5x_6$
约束于：
$5x_1+2x_2+3x_3+4x_4+x_5+2x_6\le 7$ (约束1)
$x_1+x_2\le 1$ (约束2)
$x_3+x_4\le 1$ (约束3)
$x_5+x_6\le 1$ (约束4)
x i ∈ { 0 , 1 } x_i \in \{0,1\} xi​∈{ 0,1} 对于 $i=1,...,6$

在这个问题中，我们可以将约束 (1) 视为“复杂”约束，而约束 (2)-(4) 以及二元变量约束可以被视为“简单”约束。请注意，这个问题足够小，可以用标准求解器轻松解决。然而，它可以用来说明拉格朗日松弛的过程。

2. 拉格朗日松弛 (Lagrangian Relaxation)

对于上述问题，我们将复杂约束 $Ax\le b$ 松弛掉。这意味着我们将它们从约束集合中移除，并将它们（以惩罚的形式）添加到目标函数中。为此，我们为每个被松弛的约束引入一个拉格朗日乘子 ${\lambda }_i\ge 0$。

由此产生的拉格朗日（松弛）子问题 $L(\lambda )$ 定义如下：
L ( λ ) = max ⁡ { c T x + λ T ( b − A x ) } L(\lambda) = \max \{c^T x + \lambda^T (b - Ax)\} L(λ)=max{ cTx+λT(b−Ax)}
约束于：
$Dx\le e$
x i ∈ { 0 , 1 } x_i \in \{0,1\} xi​∈{ 0,1}

对于任意给定的 $\lambda \ge 0$，$L(\lambda )$ 的最优值是原问题最优值的上界。

对于我们的示例问题，如果我们松弛约束 (1)，拉格朗日乘子 ${\lambda }_1$ (简写为 $\lambda$，因为只有一个) 必须是非负的。子问题 $L(\lambda )$ 变为：
$L(\lambda )=\max \{(12x_1+8x_2+7x_3+6x_4+10x_5+5x_6)+\lambda (7-(5x_1+2x_2+3x_3+4x_4+x_5+2x_6))\}$
约束于：
$x_1+x_2\le 1$