松弛算法ppt課件-文庫吧資料
2025-05-07 00:02本頁面
【正文】 充分小時 ,存在 ,使得 : *? m a x { * , 0 }is? ? ???? jI?( ) ( )T j T jLRz c x b A x??? ? ?由 內(nèi)所有次梯度夾角不超過 90度 ,有 ( *)LRz ??( ) ( * ) ( * ) ( ) ( ) ( ) 0T j i jL R L Rz z b A x b A x b A x? ? ? ? ?? ? ? ? ? ? ? ?由上面的討論可得 次梯度優(yōu)化算法 如下 : STEP1: 仸選初始拉格朗日乘子 STEP2: 對 ,從 中仸選一個次梯度 ,若 則停 ,否則 重復(fù) STEP2. ,1t t? ?t? ()tg ?? ts0ts ? 1 m a x { , 0 } , : 1t t ts t t? ? ?? ? ? ? ?注 : 的選取 : ?10: , 0 , ( , 198 1 ): , 0 1( ) ( ):|| ||ttttU P L Ptt ta t Fis he rbz t z tcs??? ? ? ?????? ? ? ? ?? ? ????停止準則： :: 0 ( ) , | | | |: ( ) ( ): ( )t t tLRU P L PttLRaTb s z or sc z t z tdz????? ? ? ??迭 代 次 數(shù) 上 限或 在 一 定 步 數(shù) 內(nèi) 變 化 不 超 過 某 給 定 值 拉格朗日啟發(fā)式算法 Step1: 拉格朗日次梯度法求 IP下界 Step2: 對所求解可行化 例 假設(shè)集合覆蓋問題 SC通過前面的松弛得到一個解 ,當(dāng)其不可行時即存在 i使得 12( , , )nx x x x?10nij jjax???一個可行化方法是求 k,滿足 1m i n { | 1 }k j i jjnc c a????重復(fù)以上步驟 ,直到所有行都被覆蓋 . 集合覆蓋問題的拉格朗日松弛算法 : Step1: 初始化 0 ,0t? ?Step2: 計算 ()tLRz ?Step3: 若所有行被覆蓋 ,stop。二、 LR最優(yōu)解和 LP最優(yōu)解的關(guān)系 ( ) ( )TIPx I P c x z?????????TLRn+對 于 給 定 的 0 ，z ( ) = m i n { c x + ( b A x ) }（ LR ） s . t . B x dxZ的 最 優(yōu) 解 為 問 題 可 行 ， 并 不 能 有具體例見例 。 0 , .kLD k j jk K j JkkKkjk k kk K k K k Kkjz c T x rs t A x r bk K j J???? ? ??????? ? ???? ???????? ? ? ? ?????? ? ?即有 : ()m in..TLDx Co n Qz c xs t A x b???推論 : 對于仸給 c,整數(shù)規(guī)劃問題 IP和拉 格 朗日對偶問題 LD的目標值相等的充要條件為 : ( { | }) ( ) { | }nnCo n Q x R A x b Co n Q x R A x b??? ? ? ? ? ? ?證 : 顯然有 { | } ( ) { | }nnQ x R A x b Co n Q x R A x b??? ? ? ? ? ? ?( { | } ) ( ( ) { | } )( ) { | }nnnC o n Q x R A x b C o n C o n Q x R A x bC o n Q x R A x b???? ? ? ? ? ? ?? ? ? ?從而有 : 再由定理 : ( { | } ) ( ) { | }m in m innnTTI P L Dx Co n Q x R A x b x Co n Q x R A x bz c x z c x??? ? ? ? ? ? ? ?? ? ?若對仸何 c有 ,則問題得證 . IP LDzz?例 假設(shè)整數(shù)規(guī)劃問題 IP 12121212122m i n{ 7 2 }245 202 2 7. . 7. 2. 224IPz x xxxxxxxstxxxZ?? ? ?? ? ???? ? ? ??? ??????? ? ? ?????第一個約束為復(fù)雜約束 ,其拉格朗日松弛后的模型 LR為 : 121212122( ) m in{ ( 7 ) ( 2 2 ) 4 }5 202 2 7. . 2 .34LRz x xxxxxs t xxxZ? ? ? ??? ? ? ? ? ?? ? ? ? ?????????? ? ??? ?? 4 3 2 1 1 2 3 4 l2 l1 l4 l3 E D C B A 41( , )17 17 T.3圖解示意 下降方向 最優(yōu)解 (7,2) (3,4) 29 (,1) (4,0) 32 (8,0) (4,0) 32 ? ()LRz ?0??12??1??(7 , 2 2 ) T???? 12( ( ), ( ))Txx?? ( , *)LRzx?227 2 2( , )5 3 6 5 5 3 6 5T??? ? ? ???? ? ? ?單位化下降方向 : 227 2 2 1 2l im ( , ) ( , )5553 6 5 53 6 5TT???? ? ? ???? ? ??? ? ? ?最優(yōu)值只能在 (4,0)和 (3,4)兩點得到 ,過這兩點的直線方程 :y+x4= : 41( , )1 7 1 7 T227 2 2 4 1 1, ( , )917 1753 6 5 53 6 5T?? ?? ? ? ??? ? ? ?? ? ? ?綜合有 : 129 0119( ) ( ) 281 9928 89LR LD LRz z z?????? ? ? ? ???? ? ? ? ??? ? ? ???例 (繼 ) 例 { ( 2 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) , ( 3 , 4 ) , ( 4 , 0 ) }T T T T T T T TQ ?12121 ( { | 2 4 } )2 ( ) { | 2 4 }nnS C o n Q x R x xS C o n Q x R x x??? ? ? ? ? ?? ? ? ? ? ?4 3 2 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1