拉格朗日松弛課件

拉格朗日松弛算法---TheLagrangianRelaxationMethod1拉格朗日松弛算法---TheLagrangianROutline2Outline2引入拉格朗日松弛算法拉格朗日松弛是求解下界的一種方法拉格朗日松弛應(yīng)用于求解約束規(guī)劃問題目標(biāo)函數(shù)值增大最優(yōu)值上界下界gap3引入拉格朗日松弛算法拉格朗日松弛是求解下界的一種方法拉格朗

為什么拉格朗日松弛可以求得下界？基本原理將造成問題難的約束吸收到目標(biāo)函數(shù)中，并使得目標(biāo)函數(shù)仍保持線性，使得問題容易求解。拉格朗日松弛后變換為：IP的最優(yōu)解是LR的一個可行解，所以，原問題：拉格朗日乘子（非負）4為什么拉格朗日松弛可以求得下界？基本原理將造成問題基本原理g(x):原問題Defg(x):原問題的可行域f(x):松弛后的問題Deff(x):松弛問題的可行域5基本原理g(x):原問題f(x):松弛后的問題5用途為什么拉格朗日松弛popular?第一，對于線性整數(shù)規(guī)劃問題，將難約束吸收到目標(biāo)函數(shù)后，問題變得容易求解。第二，實際的計算結(jié)果證實拉格朗日松弛方法所給的下界相當(dāng)不錯，且計算時間可以接受。同時，可以進一步利用拉格朗日松弛的基本原理構(gòu)造基于拉格朗日松弛的啟發(fā)式算法。不一定是可行解，但是可以求得下界獲得可行解（上界）/最優(yōu)解（最優(yōu)值）為什么拉格朗日松弛popular？6用途為什么拉格朗日松弛popular?第一，對于線性整數(shù)Outline7Outline7如何應(yīng)用如何選取松弛的條件？原則：該條件去掉后使得問題容易求解。如何選擇最優(yōu)的拉格朗日乘子？原問題的拉格朗日松弛為：原問題的拉格朗日對偶為：最好的下界8如何應(yīng)用如何選取松弛的條件？原則：該條件去掉后使得問題容易求如何應(yīng)用—凹函數(shù)凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）9如何應(yīng)用—凹函數(shù)凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度如何應(yīng)用—梯度法梯度法：在某一點，沿梯度方向搜索，能找到函數(shù)的極值點。ABC步驟：任給一個初始出發(fā)點，設(shè)為X0，X0X1（2）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；（3）修改當(dāng)前參數(shù)X1=X0+d*y’（4）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；……重復(fù)（1）設(shè)定一個步長d；一元函數(shù)10如何應(yīng)用—梯度法梯度法：在某一點，沿梯度方向搜索，能找到函數(shù)如何應(yīng)用—次梯度法次梯度法：在某一點，沿次梯度方向搜索，能找到函數(shù)的極值點。為的一個可行解次梯度不唯一步驟：STEP1:STEP2:，

否則，步長：11如何應(yīng)用—次梯度法次梯度法：在某一點，沿次梯度方向搜索，能找如何應(yīng)用—步長為原問題的一個上界，可以由一個可行解的目標(biāo)值確定，也可以通過估計的方法得到?？呻St的變化逐步修正。原問題的下界，

在給定的若干步?jīng)]有變化時，則取其一半。

12如何應(yīng)用—步長為原問題的一個上界，可以由一個可行解的目標(biāo)值確如何應(yīng)用—停止原則（1）迭代次數(shù)不超過T。這是一種最為簡單的原則，但解的質(zhì)量無法保證。停止原則：（2）。這是最為理想的狀態(tài)，此時，達到拉格朗日對偶的最優(yōu)解。在實際計算中，由于問題的復(fù)雜性和計算機本身的計算誤差，這樣的結(jié)果難達到，常常用來代替。（3）可變時，這種情況表示已得到原問題的最優(yōu)解。最優(yōu)值為。（4）在規(guī)定的步數(shù)內(nèi)變化不超過一個給定的值。這時認為目標(biāo)值不可能再變化，因此，停止運算。13如何應(yīng)用—停止原則（1）迭代次數(shù)不超過T。這是一種最為簡單Outline14Outline14簡單例子15簡單例子15簡單例子16簡單例子16簡單例子

StartingwithZUP=6,β=2andi=0fori=1,2,3,迭代三次。求出每次迭代的下界和拉格朗日乘子。

原約束：17簡單例子StartingwithZUP=6,β=2簡單例子18簡單例子18簡單例子19簡單例子19Outline20Outline20實際問題中的應(yīng)用—原問題復(fù)雜約束：船舶必須在到港之后靠泊21實際問題中的應(yīng)用—原問題復(fù)雜約束：船舶必須在到港之后靠泊21實際問題中的應(yīng)用—松弛后的問題22實際問題中的應(yīng)用—松弛后的問題22實際問題中的應(yīng)用—松弛后的問題三維指派問題二維指派問題匈牙利法23實際問題中的應(yīng)用—松弛后的問題三維指派問題二維指派問題匈牙利實際問題中的應(yīng)用獲得可行解的啟發(fā)式算法停止準則1停止準則224實際問題中的應(yīng)用獲得可行解的啟發(fā)式算法停止準則1停止準則22實際問題中的應(yīng)用將次梯度法擴展為拉格朗日松弛啟發(fā)式算法。每更改一次拉格朗日乘子，求出一個下界，構(gòu)造啟發(fā)式算法修改不可行解，得到一個上界。目標(biāo)函數(shù)值增大最優(yōu)值上界下界gap25實際問題中的應(yīng)用將次梯度法擴展為拉格朗日松弛啟發(fā)式算法。目標(biāo)Outline26Outline26難點探討（1）松弛條件的選取。將復(fù)雜的約束條件松弛，復(fù)雜指的是該約束導(dǎo)致模型在多項式時間內(nèi)不能求解。一個問題的計算時間m(n)不大于問題大小n的多項式倍數(shù)。（2）拉格朗日松弛啟發(fā)式算法的設(shè)計。松弛后獲得的解不可行，需要修改，不同問題的修改方法不同。27難點探討（1）松弛條件的選取。將復(fù)雜的約束條件松弛，復(fù)雜指的Thanks馮媛君2011.11.1428Thanks馮媛君2829293030拉格朗日松弛算法---TheLagrangianRelaxationMethod31拉格朗日松弛算法---TheLagrangianROutline32Outline2引入拉格朗日松弛算法拉格朗日松弛是求解下界的一種方法拉格朗日松弛應(yīng)用于求解約束規(guī)劃問題目標(biāo)函數(shù)值增大最優(yōu)值上界下界gap33引入拉格朗日松弛算法拉格朗日松弛是求解下界的一種方法拉格朗

為什么拉格朗日松弛可以求得下界？基本原理將造成問題難的約束吸收到目標(biāo)函數(shù)中，并使得目標(biāo)函數(shù)仍保持線性，使得問題容易求解。拉格朗日松弛后變換為：IP的最優(yōu)解是LR的一個可行解，所以，原問題：拉格朗日乘子（非負）34為什么拉格朗日松弛可以求得下界？基本原理將造成問題基本原理g(x):原問題Defg(x):原問題的可行域f(x):松弛后的問題Deff(x):松弛問題的可行域35基本原理g(x):原問題f(x):松弛后的問題5用途為什么拉格朗日松弛popular?第一，對于線性整數(shù)規(guī)劃問題，將難約束吸收到目標(biāo)函數(shù)后，問題變得容易求解。第二，實際的計算結(jié)果證實拉格朗日松弛方法所給的下界相當(dāng)不錯，且計算時間可以接受。同時，可以進一步利用拉格朗日松弛的基本原理構(gòu)造基于拉格朗日松弛的啟發(fā)式算法。不一定是可行解，但是可以求得下界獲得可行解（上界）/最優(yōu)解（最優(yōu)值）為什么拉格朗日松弛popular？36用途為什么拉格朗日松弛popular?第一，對于線性整數(shù)Outline37Outline7如何應(yīng)用如何選取松弛的條件？原則：該條件去掉后使得問題容易求解。如何選擇最優(yōu)的拉格朗日乘子？原問題的拉格朗日松弛為：原問題的拉格朗日對偶為：最好的下界38如何應(yīng)用如何選取松弛的條件？原則：該條件去掉后使得問題容易求如何應(yīng)用—凹函數(shù)凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）39如何應(yīng)用—凹函數(shù)凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度如何應(yīng)用—梯度法梯度法：在某一點，沿梯度方向搜索，能找到函數(shù)的極值點。ABC步驟：任給一個初始出發(fā)點，設(shè)為X0，X0X1（2）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；（3）修改當(dāng)前參數(shù)X1=X0+d*y’（4）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；……重復(fù)（1）設(shè)定一個步長d；一元函數(shù)40如何應(yīng)用—梯度法梯度法：在某一點，沿梯度方向搜索，能找到函數(shù)如何應(yīng)用—次梯度法次梯度法：在某一點，沿次梯度方向搜索，能找到函數(shù)的極值點。為的一個可行解次梯度不唯一步驟：STEP1:STEP2:，

否則，步長：41如何應(yīng)用—次梯度法次梯度法：在某一點，沿次梯度方向搜索，能找如何應(yīng)用—步長為原問題的一個上界，可以由一個可行解的目標(biāo)值確定，也可以通過估計的方法得到?？呻St的變化逐步修正。原問題的下界，

在給定的若干步?jīng)]有變化時，則取其一半。

42如何應(yīng)用—步長為原問題的一個上界，可以由一個可行解的目標(biāo)值確如何應(yīng)用—停止原則（1）迭代次數(shù)不超過T。這是一種最為簡單的原則，但解的質(zhì)量無法保證。停止原則：（2）。這是最為理想的狀態(tài)，此時，達到拉格朗日對偶的最優(yōu)解。在實際計算中，由于問題的復(fù)雜性和計算機本身的計算誤差，這樣的結(jié)果難達到，常常用來代替。（3）可變時，這種情況表示已得到原問題的最優(yōu)解。最優(yōu)值為。（4）在規(guī)定的步數(shù)內(nèi)變化不超過一個給定的值。這時認為目標(biāo)值不可能再變化，因此，停止運算。43如何應(yīng)用—停止原則（1）迭代次數(shù)不超過T。這是一種最為簡單Outline44Outline14簡單例子45簡單例子15簡單例子46簡單例子16簡單例子

StartingwithZUP=6,β=2andi=0fori=1,2,3,迭代三次。求出每次迭代的下界和拉格朗日乘子。

原約束：47簡單例子StartingwithZUP=6,β=2簡單例子48簡單例子18簡單例子49簡單例子19Outline50Outline20實際問題中的應(yīng)用—原問題復(fù)雜約束：船舶必須在到港之后靠泊51實際問題中的應(yīng)用—原問題復(fù)雜約束：船舶必須在到港之后靠泊21實際問題中的應(yīng)用—松弛后的問題52實際問題中的應(yīng)用—松弛后的問題22實際問題中的應(yīng)用—松弛后的問題三維指派問題二維指派問題匈牙利法53實際問題中的應(yīng)用—松弛后的問題三維指派問題二維指派問題匈牙利實際問題中的應(yīng)用獲得可行解的啟發(fā)式算法停止準則1停止準則254實際問題中的應(yīng)用獲得可行解的啟發(fā)式算法停止準則1停止準則22實際問題中的應(yīng)用將次梯度法擴展為拉格朗日松弛啟發(fā)式算法。每更改一次拉格朗日乘子，求出一個下界，構(gòu)造啟發(fā)式算法修改不可行解，得到一個上界。目標(biāo)函數(shù)值增大最優(yōu)值上界下界gap55實際問題中的應(yīng)