拉格朗日松弛
拉格朗日（拉格朗日）松弛 / 对偶是整数规划、组合优化中常用的一种分解与定界技术：将一批“难”约束对偶化到目标里，在保留的“易”可行集上求子问题，并通过对乘子 的优化得到对原问题目标值的界。全文记号自成体系（(IP)、、拉格朗日对偶 (LD) 等）；公式旁编号 (12.x) 等仅便于本文内交叉指代。若需与经典专著对照，可参见 Wolsey (1998) 等。
适用于什么问题
当整数规划或混合整数规划可写成「一组相对 简单且结构化 的约束与非退化可行域 」加上一组「书写冗长或使模型难解 耦合约束」 时，常可把后者松弛进目标并转而重复求解 ，再配合乘子优化或其它迭代给出 原问题上界或下界（极大或极小情形而定）、或为分支定界供可行松弛。典型：设施选址 / 选址分配中与耦合有关的切割容量约束、旅行商 中的海量子回路不等式（在理论上可先松弛后对 迭代）、车辆路由中与装载耦合的大规模耦合不等式写不进紧凑 MILP 时的定性近似边界。不适用：难约束不可剥离且无法在去掉它们之后仍能高效求解子问题的情形；或子问题本身仍为 NP-hard 且没有比原来更简单时才慎用单独 LR。
1. 拉格朗日松弛介绍
1.1 原问题：易约束与难约束
考虑整数规划原问题。若把约束区分为相对容易与困难的两部分，可写为（极大化原问题，便于后文叙述）：
- 若只保留 与非负整数，问题往往容易（结构简单、可分解、或便于求解）。
- 一旦加入 ，问题可能变得极难（如 TSP 中大量子圈消除约束）。
若直接删去难约束 ，可行域过大，上界/下界很松，缺少对“违反难约束的惩罚”。
1.2 用可行集 写成的等价形式
令
并设 为 条相对复杂的约束。则原问题可写为：
1.3 拉格朗日松弛问题
对任意非负乘子向量 （），将 以惩罚项形式并入目标，得到拉格朗日松弛子问题：
记为 ，其中 为在乘子 下该子问题的最优值。直观上， 衡量“难约束的松弛量”：在可行时该项非负，乘上 对目标产生奖罚； 常被解释为影子价格 / 对偶变量 / 拉格朗日乘子（依上下文）。
2. 松弛性质与上界
2.1 拉格朗日松弛的定界
定理：对任意 ，问题 是原问题 (IP) 的松弛（relaxation）。
证明（满足松弛的两项常见条件）：
可行域
原 (IP) 的可行解满足 且 ，即位于 。而 仅要求 ，不再显式要求 ，故在 的取值范围上，松弛问题的可行域是原可行域的超集（或理解为：先放宽难约束、再以罚项在目标中体现）。目标值比较（对 (IP) 的任一可行解 ）
因 且 ，有 ，故即在同一 上，松弛问题的目标不低于原目标。
推论（定界，极大化原问题）：对任意 ， 的最优值 给原 (IP) 的最优值 一个上界：
为了得到尽量紧的上界，自然希望在 上最小化 。这就引出下一节的拉格朗日对偶。
3. 拉格朗日对偶问题
3.1 对偶 (LD) 的写法
为求“最好的”乘子，定义拉格朗日对偶问题：
等式难约束的情形：若难约束在模型中写为 ，则乘子不再限制符号，，对偶为
在一定条件下，求解 (LD) 可得到紧的上界，个别情形下还可由此恢复原 (IP) 的最优解（见下述最优性条件）。
3.2 最优性条件：何时 的解就是 (IP) 的解
设 ，并存在 满足：
- 是 的最优解；
- （原难约束可行）；
- 互补松弛：对所有 ，若 则 。
则 是原 (IP) 的最优解。
证明思路（要点）：由 (1) 有
由 (3) 得 ，故
由 (2) 得 对 (IP) 可行，故 。结合弱对偶/对偶界有 ，在适当条件下可推出 与最优性。
注：难约束全部为等式时 (3) 常自动更自然；若某 的最优解已经满足 (IP) 的全体约束，它往往也是 (IP) 的最优解之一。
4. 应用：无容量设施选址 (UFLP) 的拉格朗日松弛
4.1 集合、参数与变量
- ：潜在设施下标；：客户下标。
- ：开放设施 的固定费用；：将客户 全部分配到 时产生的收益（也可理解为“净收益”，即已扣除相应成本后的量，视建模习惯而定）。
- 决策： 是否开设施 ； 为客户 由 满足的需求比例；需求约束 保证每个客户恰好被完全满足（无容量时可用比例 全分给某一设施等解释）。
原 (IP)：
4.2 松弛 (12.3)：
对每条需求约束引入乘子 ，将 (12.3) 对偶到目标。目标中增加
整理得等价目标为（相当于将 (12.3) 的罚项展开后合并同类项）：
拉格朗日松弛（保留 (12.4)(12.5)）为：
4.3 按设施 分解
(12.9) 按 可分离为每个 一个子问题。总目标
其中
闭式解（对固定的 ）：
- 若 ，则 ，目标为 。
- 若 ，为最大化，在 且 下，可对每个 独立将 取到使 最大的 或 。在“若开设施 ，则对客户 要么全给 、要么不给”的{0,1} 指派解释下，得到
（若仍允许 为 上的连续分配，闭式需按该子问题结构另写；上式对应二元指派型 UFLP 子问题常见闭式。）
5. 数值算例
取 个客户、 个设施。
固定费（本例取下列数值，便于手算）：
收益矩阵 （）：
给定一组乘子 ，则
有效收益 的矩阵为：
设施 为例：第 2 列 中正分量为第 行的 与第 行的 。若 ，则子问题贡献
对所有 比较 后，可得到一组在 下最优的 。例如取 、、；、；其余为 时，总贡献与常数项相加得
即该 下松弛目标值为 （作为原问题目标的一个上界候选，仍需求解 (LD) 以改进 ）。
6. 拉格朗日对偶的加强（与凸包表述）
在 有限个极点 的假设下， 可写为在极点上的极大。对偶界可展开为
引入标量 上界 (12.16) 可写成线性规划（对 ）：
其对偶给出（在凸组合权重 下）的等价形式，并可几何解释为在 上与 的交上极大化 。常见结论可概括为：
与凸包等价的对偶界（常称 Lagrangian dual 的“凸包解释”）
。
即对偶界相当于在难约束与 的凸包 上作线性（实为连续）优化；在常见设定下，该界不弱于仅在 的线性松弛上作 LP 所得之界（具体依赖 的 -表述等）。有完美凸包多面体时：若 的凸包有显式线性不等式表示 ，则 可写为在 与 上极大 的联合问题。
对偶函数形状： 是凸的逐段线性函数； 即在其图像上求最小值。若仅有一个乘子分量，可想象为：若干条仿射直线（各对应某个极点 下的子问题值）的上包络，整体呈折线。下图为一维 的示意：细线为各分量的线性部分，粗线为 ，所求为 在大致最低点处取得。
7. 如何求解拉格朗日松弛（次梯度法）
7.1 极小化“极大族仿射”的凸函数
考虑逐段线性凸函数 的极小，一般可写为
拉格朗日对偶的求值
与 (12.28)–(12.29) 同构（ 是若干以 为自变量的仿射函数的逐点最大）。因此 (LD) 的求解与对一般的 的极小属同一类凸—非光滑优化。
7.2 与上包络的“线性化”（引入辅助标量 ）
在有限项 时，(12.28)–(12.29) 可等价写成在 与 上的线性目标与线性不等式，即上境图 (epigraph) 技巧：
与 §6 中 (12.17)–(12.18) 的写法为同一思想。对 在极点集 上取 时，可同样用 把“”变形成带 的凸约束；若 很大，在算法上往往不显式枚举全部不等式，而用次梯度或割平面逐步逼近。
7.3 次梯度的定义
对凸函数 ，称向量 是 在 处的一个次梯度（subgradient），若
当 在 处可微时，次梯度与梯度相同：。对 (12.31) 的 ，在固定 下求解子问题得最优解 时，有
可视为 在 处的一个次梯度（在 为逐点取极大的凸函数时，这是常用的取法）。
7.4 投影次梯度迭代（对偶乘子更新）
在 上投影次梯度更新（分量取非负）：
- 初始化：，。
- 当 时循环：
- 解 ，得最优解 ；
- 计算次梯度：；
- 取步长 （见下节）；
- 乘子更新（向非负正交象限投影）这里 为按分量取 ；
- 。
- 结束（常配合启发式可行化、对偶/原始界记录等工程技巧）。
该框架与 (12.30) 一致：在每一迭代用当前 的松弛值 与次梯度信息沿非光滑意义下的下降方向试探 。收敛性需对 的假设与步长规则作约束，经典非光滑优化中已有多种充分条件，此处不展开证明。
7.5 步长 的常用取法
递减步长
要求 且 （）。例：。几何衰减
，其中 ， 为初值参数。Polyak 型步长（若可估计最优对偶值的近似）
其中 为 的某估计（如分支定界中已知的最好原始可行解所对应目标值、或其与对偶界配合得到的对偶间隙相关标量，依实现而定；Polyak 原式依赖该估计的精度与符号约定。）
实现时还需数值截断、最大迭代数、对偶/原始隙监控与重启动等，以稳定 的搜索。
备忘
（可在此补：枝定界/分支中拉格朗日界的使用、与 Dantzig–Wolfe / Benders 的对比、Gurobi 中相应接口、bundle/割平面替代次梯度的情形等。）