拉格朗日松弛

Page1拉格朗日松弛算法---TheLagrangianRelaxationMethodPageOutline21.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨Page引入拉格朗日松弛算法3拉格朗日松弛是求解下界的一种方法拉格朗日松弛应用于求解约束规划问题目标函数值增大最优值上界下界gapPage为什么拉格朗日松弛可以求得下界？基本原理4将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性，使得问题容易求解。拉格朗日松弛后变换为：IP的最优解是LR的一个可行解，所以，原问题：拉格朗日乘子（非负）Page基本原理5g(x):原问题Defg(x):原问题的可行域f(x):松弛后的问题Deff(x):松弛问题的可行域Page用途6为什么拉格朗日松弛popular?第一，对于线性整数规划问题，将难约束吸收到目标函数后，问题变得容易求解。第二，实际的计算结果证实拉格朗日松弛方法所给的下界相当不错，且计算时间可以接受。同时，可以进一步利用拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式算法。不一定是可行解，但是可以求得下界获得可行解（上界）/最优解（最优值）为什么拉格朗日松弛popular？PageOutline71.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨Page如何应用8如何选取松弛的条件？原则：该条件去掉后使得问题容易求解。如何选择最优的拉格朗日乘子？原问题的拉格朗日松弛为：原问题的拉格朗日对偶为：最好的下界Page如何应用—凹函数9凹函数（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）Page如何应用—梯度法10梯度法：在某一点，沿梯度方向搜索，能找到函数的极值点。ABC步骤：任给一个初始出发点，设为X0，X0X1（2）计算该点当前梯度（导数）y’；（3）修改当前参数X1=X0+d*y’（4）计算该点当前梯度（导数）y’；……重复（1）设定一个步长d；一元函数Page如何应用—次梯度法11次梯度法：在某一点，沿次梯度方向搜索，能找到函数的极值点。为的一个可行解次梯度不唯一步骤：STEP1:STEP2:，否则，步长：Page如何应用—步长12为原问题的一个上界，可以由一个可行解的目标值确定，也可以通过估计的方法得到。可随t的变化逐步修正。原问题的下界，在给定的若干步没有变化时，则取其一半。欧式范数（2-范数），∥𝑆∥=(𝑠𝑖2𝑛𝑖=1)12Page如何应用—停止原则13（1）迭代次数不超过T。这是一种最为简单的原则，但解的质量无法保证。停止原则：（2）。这是最为理想的状态，此时，达到拉格朗日对偶的最优解。在实际计算中，由于问题的复杂性和计算机本身的计算误差，这样的结果难达到，常常用来代替。（3）可变时，这种情况表示已得到原问题的最优解。最优值为。（4）在规定的步数内变化不超过一个给定的值。这时认为目标值不可能再变化，因此，停止运算。PageOutline141.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨Page简单例子15Page简单例子16Page简单例子17StartingwithZUP=6,β=2andi=0fori=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简单例子181234643212+----=xxxxMinTX)(=1，1，1，1221234162-=+----=LBZTS）2，1，1（2---=3826）2（62=×--=TTT）03434（0，）2，1，1（384，4，43,,=}---×+)max{(=Page简单例子1938311383243213++++3-=xxxxMinTX)(=0，0，0，1323823=+3-=LBZTS）1，，0（30=821263=×-=TTT）03434（0，）1，0，0（80，34，344,,=}×+)max{(=PageOutline201.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨Page实际问题中的应用—原问题21复杂约束：船舶必须在到港之后靠泊Page实际问题中的应用—松弛后的问题22Page实际问题中的应用—松弛后的问题23三维指派问题二维指派问题匈牙利法Page24实际问题中的应用获得可行解的启发式算法停止准则1停止准则2Page实际问题中的应用25将次梯度法扩展为拉格朗日松弛启发式算法。每更改一次拉格朗日乘子，求出一个下界，构造启发式算法修改不可行解，得到一个上界。目标函数值增大最优值上界下界gapPageOutline261.基本原理及用途2.如何应用3.简单例子4.在实际问题中的应用5.难点探讨Page难点探讨27（1）松弛条件的选取。将复杂的约束条件松弛，复杂指的是该约束导致模型在多项式时间内不能求解。一个问题的计算时间m(n)不大于问题大小n的多项式倍数。（2）拉格朗日松弛启发式算法的设计。松弛后获得的解不可行，需要修改，不同问题的修改方法不同。Page28Thanks冯媛君2011.11.14Page29Page30Page31