拉格朗日松弛课件.ppt

1、Page1拉格朗日松弛算法-The Lagrangian Relaxation MethodPage2OutlinePage3 引入拉格朗日松弛算法n 拉格朗日松弛是求解下界的一种方法n 拉格朗日松弛应用于求解 约束规划问题目标函数值增大最优值上界下界gapPage4n 为什么拉格朗日松弛可以求得下界？基本原理将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性，使得问题容易求解。拉格朗日松弛后变换为：IP的最优解是LR的一个可行解，所以，原问题：拉格朗日乘子（非负）Page5基本原理g(x):原问题Def g(x):原问题的可行域f(x):松弛后的问题Def f(x):松弛问题的可行

2、域Page6用途n 为什么拉格朗日松弛 popular?第一，对于线性整数规划问题，将难约束吸收到目标函数后，问题变得容易求解。第二，实际的计算结果证实拉格朗日松弛方法所给的下界相当不错，且计算时间可以接受。同时，可以进一步利用拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式算法。不一定是可行解，但是可以求得下界 获得可行解（上界）/最优解（最优值）为什么拉格朗日松弛 popular？Page7OutlinePage8如何应用n 如何选取松弛的条件？原则：该条件去掉后使得问题容易求解。n 如何选择最优的拉格朗日乘子？原问题的拉格朗日松弛为：原问题的拉格朗日对偶为：最好的下界Page9如何应用

3、凹函数凹函数（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）Page 10如何应用梯度法梯度法：在某一点，沿梯度方向搜索，能找到函数的极值点。ABC步骤：任给一个初始出发点，设为X0，X0X1（2）计算该点当前梯度（导数）y；（3）修改当前参数 X1=X0+d*y（4）计算该点当前梯度（导数）y；重复（1）设定一个步长d；一元函数Page 11如何应用次梯度法次梯度法：在某一点，沿次梯度方向搜索，能找到函数的极值点。为 的一个可行解次梯度不唯一步骤：STEP1:STEP2:，否则，步长：Page 12如何应用步长为原问题的一个上界，可以由一个可行解的目标值确定，也可以通过估计的方法得到

4、。可随t 的变化逐步修正。原问题的下界，在给定的若干步没有变化时，则取其一半。Page 13如何应用停止原则（1）迭代次数不超过 T。这是一种最为简单的原则，但解的质量无法保证。停止原则：（2）。这是最为理想的状态，此时，达到拉格朗日对偶的最优解。在实际计算中，由于问题的复杂性和计算机本身的计算误差，这样的结果难达到，常常用 来代替。（3）可变时，这种情况表示已得到原问题的最优解。最优值为 。（4）在规定的步数内变化不超过一个给定的值。这时认为目标值不可能再变化，因此，停止运算。Page 14OutlinePage 15简单例子Page 16简单例子Page 17简单例子 Starting w

5、ith ZUP=6,=2 and i=0 for i=1,2,3,迭代三次。求出每次迭代的下界和拉格朗日乘子。TX)(=0，0，0，0101312111=+=LBZTS）1，1，1（1=423061=-=TTT）4，4，4（0，）1，1，1（40，0，02=+)max(=原约束：Page 18简单例子1234643212+-=xxxxMinTX)(=1，1，1，1221234162-=+-=LBZTS）2，1，1（2-=3826）2（62=-=TTT）03434（0，）2，1，1（384，4，43,=-+)max(=Page 19简单例子38311383243213+3-=xxxxMinTX)

6、(=0，0，0，1323823=+3-=LBZTS）1，0（30=821263=-=TTT）03434（0，）1，0，0（80，34，344,=+)max(=Page 20OutlinePage 21实际问题中的应用原问题复杂约束：船舶必须在到港之后靠泊Page 22实际问题中的应用松弛后的问题Page 23实际问题中的应用松弛后的问题三维指派问题二维指派问题匈牙利法Page 24实际问题中的应用获得可行解的启发式算法停止准则1停止准则2Page 25实际问题中的应用将次梯度法扩展为拉格朗日松弛启发式算法。每更改一次拉格朗日乘子，求出一个下界，构造启发式算法修改不可行解，得到一个上界。目标函数值增大最优值上界下界gapPage 26OutlinePage 27难点探讨（1）松弛条件的选取。将复杂的约束条件松弛，复杂指的是该约束导致模型在多项式时间内不能求解。一个问题的计算时间 m(n)不大于问题大小 n 的多项式倍数。（2）拉格朗日松弛启发式算法的设计。松弛后获得的解不可行，需要修改，不同问题的修改方法不同。Page 28Thanks冯媛君2011.11.14Page 29Page 30