拉格朗日松弛

拉格朗日松弛（Lagrangian relaxation）把一部分难处理的约束乘上价格后并入目标函数，保留其余结构来求解较容易的子问题。价格由乘子表示，松弛解可能违反原约束；但乘子的符号选得正确时，子问题最优值仍给出原问题的可靠界。它既是分解方法，也是整数优化中构造界的工具。

有两项可选服务，选择变量 $x_1,x_2\in \{0,1\}$，费用分别为三元、二元，至少选择一项。原问题 $$min\{3x_1+2x_2:x_1+x_2\ge 1\}$$ 的最优方案是只选第二项，费用二元。若删去覆盖约束，零选择就会被误认为最优；拉格朗日方法保留一个与缺口有关的费用来构造下界，但不要求这项费用足以使每个松弛解自动可行。

乘子符号与弱对偶

将约束写成 $1-x_1-x_2\le 0$。对 $\lambda \ge 0$，拉格朗日函数及其子问题值为 $$\begin{array}{cc}L(x,\lambda )& =3x_1+2x_2+\lambda (1-x_1-x_2),\\ g(\lambda )& =\underset{x_1,x_2\in \{0,1\}}{min}L(x,\lambda ).\end{array}$$ 若 $x$ 原本可行，约束项非正，故 $L(x,\lambda )\le 3x_1+2x_2$。再对所有二进制选择取最小，得到 $$g(\lambda )\le L(x,\lambda )\le 3x_1+2x_2.$$ 因此每个非负乘子产生一个下界；尽量增大下界，就是拉格朗日对偶问题。最大化原问题、反向不等式或等式约束会改变符号约定，不能只凭“加一个惩罚项”的直觉搬用此式。

松弛后的两个变量已可分开决定： $$g(\lambda )=\lambda +min(0,3-\lambda )+min(0,2-\lambda ).$$ 系数为负时取一、正时取零、零时两者都可以。于是 $$g(\lambda )=\{\begin{array}{cc}\lambda ,& 0\le \lambda \le 2,\\ 2,& 2\le \lambda \le 3,\\ 5-\lambda ,& \lambda \ge 3.\end{array}$$ 最好的下界是二，恰好与可行费用二相等，证实该方案最优。

绿色折线处处低于或等于原问题最优费用二；把乘子无限增大不会持续改善下界。

对偶凹性及解的恢复

一般最小化问题可写为 $min\{f(x):x\in X,g_i(x)\le 0\}$，其中 $X$ 可以是离散集合。保留 $X$、松弛其余约束，令 $$q(\lambda )=\underset{x\in X}{inf}\{f(x)+{\lambda }^{T}g(x)\}.$$ 假定相应下确界有意义，非负乘子仍给出下界。即使 $f$ 和 $X$ 并不凸，对偶函数也是凹的：对 $0\le t\le 1$，每个 $x$ 都有 $$\begin{array}{cc}L(x,t\lambda +(1-t)\mu )& =tL(x,\lambda )+(1-t)L(x,\mu )\\ & \ge tq(\lambda )+(1-t)q(\mu ).\end{array}$$ 左端取下确界即得凹性不等式。若有些乘子导致下确界为负无穷，需在有限值的有效域内理解这一步。凹性没有自动消除整数性造成的对偶间隙。

主例取 $\lambda =2$，全零选择也是松弛最优解，却不满足至少选一项。取 $\lambda =5/2$ 则唯一选择第二项，既可行又与下界相等。前者说明“对偶乘子最优”不等于“任取一个子问题最优解就是原问题解”；恢复可行方案往往还要做额外工作。若某个松弛最优解本身可行，且各约束乘子乘以其缺口总和为零，就有下界与其原费用相等，构成充分的最优证书。

一个严格间隙的反例

考虑更小的模型 $minx$，要求 $2x\ge 1$、$x\in \{0,1\}$。原最优值为一，而松弛覆盖约束所得 $$q(\lambda )=\lambda +min(0,1-2\lambda )$$ 在 $\lambda =1/2$ 达到最大二分之一。因此即使把所有乘子都试遍，仍无法把下界提高到一。此处不存在计算错误，而是该拉格朗日松弛本身的能力有限；应考虑加强保留结构、增加有效约束或结合分支方法。

可复算的子问题

代码对主例使用有理数计算，返回下界及一组子问题最优解。并列时取零，正好展示最优乘子处可能返回不可行解。

Python 3

from fractions import Fraction

def lagrangian_cover(multiplier):
    lam = Fraction(multiplier)
    if lam < 0:
        raise ValueError("nonnegative multiplier required")
    x = tuple(int(Fraction(cost)-lam < 0) for cost in (3,2))
    bound = lam + sum((Fraction(cost)-lam)*v
                      for cost,v in zip((3,2),x))
    return bound, x

print(lagrangian_cover(2))
print(lagrangian_cover(Fraction(5,2)))
print(lagrangian_cover(4))
# (Fraction(2, 1), (0, 0))
# (Fraction(2, 1), (0, 1))
# (Fraction(1, 1), (1, 1))

各变量独立选取较小项，是这段子问题代码的正确性依据。推广到 $n$ 个独立二进制变量时，一个乘子的子问题只需 $O(n)$ 次算术与 $O(n)$ 输出空间；这没有计入寻找最佳乘子的迭代成本，更不适用于所有子问题都可分的假设。

变式。 第二项费用改为五元后，只选第一项的原最优值为三，新的对偶函数为 $\lambda +min(0,3-\lambda )+min(0,5-\lambda )$，在 $[3,5]$ 上取最大值三。费用修改后须重算子问题系数，不能沿用原来的最优乘子区间。