---

前言

在運籌學和組合優化的世界里，我們經常遇到一些“棘手”的問題，這些問題因為其內在的組合復雜性（例如整數變量、非線性約束等）而難以直接求解。拉格朗日松弛（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$