拉格朗日松弛

1、Page1 拉格朗日松弛算法 - The Lagrangian Relaxation Method Page Outline 2 1. 基本原理及用途 2. 如何应用 3. 简单例子 4. 在实际问题中的应用 5. 难点探讨 Page 引入拉格朗日松弛算法 3 n 拉格朗日松弛是求解下界的一种方法 n 拉格朗日松弛应用于求解 约束规划问题 目标函数值增大最优值 上界 下界 gap Page n 为什么拉格朗日松弛可以求得下界？ 基本原理 4 将造成问题难的约束吸收到目标函数中， 并使得目标函数仍保持线性， 使得问题容易求解。 拉格朗日松弛后变换为： IP的最优解是LR的一个可 行解，所以， 原

2、问题： 拉格朗日乘子（非负） Page 基本原理 5 g(x): 原问题 Def g(x):原问题的可行域 f(x): 松弛后的问题 Def f(x): 松弛问题的可行域 Page 用途 6 n 为什么拉格朗日松弛 popular ? 第一，对于线性整数规划问题，将难约束吸收到目标函数 后，问题变得容易求解。 第二，实际的计算结果证实拉格朗日松弛方法所给的下界 相当不错，且计算时间可以接受。同时，可以进一步利用 拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式 算法。 不一定是可行解， 但是可以求得下界 获得可行解（上界）/最优解（最优值） 为什么拉格朗日松弛 popular ？ Page

3、Outline 7 1. 基本原理及用途 2. 如何应用 3. 简单例子 4. 在实际问题中的应用 5. 难点探讨 Page 如何应用 8 n 如何选取松弛的条件？ 原则：该条件去掉后使得问题容易求解。 n 如何选择最优的拉格朗日乘子？ 原问题的拉格朗日松弛为： 原问题的拉格朗日对偶为： 最好的下界 Page 如何应用凹函数 9 凹函数（向上凸的） 梯度法 光滑的（可微） 次梯度法 非光滑（不可微） Page 如何应用梯度法 10 梯度法：在某一点，沿梯度方向搜索，能找到函数的极值点。 A B C 步骤：任给一个初始出发点，设为X0， X0X1 （2）计算该点当前梯度（导数） y； （3）修改

4、当前参数 X1=X0+d* y （4）计算该点当前梯度（导数） y； 重复 （1）设定一个步长d； 一元函数 Page 如何应用次梯度法 11 次梯度法：在某一点，沿次梯度方向搜索，能找到函数的极值点。 为 的一个可行解 次梯度不唯一 步骤： STEP1: STEP2: ， 否则， 步长： Page 如何应用步长 12 为原问题的一个上界，可以 由一个可行解的目标值确定， 也可以通过估计的方法得到。 可随t 的变化逐步修正。 原问题的下界， 在给定的若干步 没有变化时，则取其一半。 Page 如何应用停止原则 13 （1）迭代次数不超过 T。这是一种最为简单的原则，但解的质量无法保证。 停止原

5、则： （2） 。这是最为理想的状态，此时， 达到拉格朗日对偶的最优解。 在实际计算中，由于问题的复杂性和计算机本身的计算误差，这样的结果 难达到，常常用 来代替。 （3） 可变时，这种情况表示已得到原问 题的最优解。最优值为 。 （4） 在规定的步数内变化不超过一个给定的值。这时 认为目标值不可能再变化，因此，停止运算。 Page Outline 14 1. 基本原理及用途 2. 如何应用 3. 简单例子 4. 在实际问题中的应用 5. 难点探讨 Page 简单例子 15 Page 简单例子 16 Page 简单例子 17 Starting with ZUP=6,=2 and i=0 for

6、i=1,2,3, 迭代三次。 求出每次迭代的下界和拉格朗日乘子。 T X)(=0，0，0，0 1 0 1 3 1 2 1 1 1 =+= LB Z T S）1 ，1 ，1（ 1 = 42 3 06 1 = - = TTT ）4，4，4（0，）1 ，1 ，1（40，0，0 2 = +)max(= 原约束： Page 简单例子 18 12346 43212 +-=xxxxMin T X)(=1 ，1 ，1 ，1 2 2123416 2 -=+-= LB Z T S）2，1，1（ 2 -= 3 8 2 6 ）2（6 2 = - = TTT ）0 3 4 3 4 （0，）2，1，1（ 3 8 4，4，

7、4 3 ,= -+)max(= Page 简单例子 19 3 8 3 11 3 8 3 2 43213 + 3 -=xxxxMin T X)(=0，0，0，1 3 2 3 82 3 =+ 3 -= LB Z T S）1 ，0（ 3 0= 82 1 26 3 = - = TTT ）0 3 4 3 4 （0，）1 ，0，0（80， 3 4 ， 3 4 4 ,= +)max(= Page Outline 20 1. 基本原理及用途 2. 如何应用 3. 简单例子 4. 在实际问题中的应用 5. 难点探讨 Page 实际问题中的应用原问题 21 复杂约束： 船舶必须在到港之后靠泊 Page 实际问题中

8、的应用松弛后的问题 22 Page 实际问题中的应用松弛后的问题 23 三维指派问题 二维指派问题 匈牙利法 Page 24 实际问题中的应用 获得可行解的启发式算法 停止准则1 停止准则2 Page 实际问题中的应用 25 将次梯度法扩展为拉格朗日松弛启发式算法。 每更改一次拉格朗日乘子，求出一个下界，构造启发式算法 修改不可行解，得到一个上界。 目标函数值增大最优值 上界 下界 gap Page Outline 26 1. 基本原理及用途 2. 如何应用 3. 简单例子 4. 在实际问题中的应用 5. 难点探讨 Page 难点探讨 27 （1）松弛条件的选取。将复杂的约束条件松弛，复杂指的是该约束导致 模型在多项式时间内不能求解。 一个问题的计算