拉格朗日松弛算法ppt課件-文庫吧資料
2025-05-05 03:17本頁面
【正文】 12* DD? ??且 ,兩平面的法方向交角不超過 90度 . 當(dāng) 不是光滑點(diǎn)是 ,在 的鄰域內(nèi) ,當(dāng) 充分小時(shí) ,存在 ,使得 : *? m a x { * , 0 }is? ? ???? jI?( ) ( )T j T jLRz c x b Ax??? ? ?由 內(nèi)所有次梯度夾角不超過 90度 ,有 ( *)LRz ??( ) ( * ) ( * ) ( ) ( ) ( ) 0T j i jLR LRz z b Ax b Ax b Ax? ? ? ? ?? ? ? ? ? ? ? ?由上面的討論可得 次梯度優(yōu)化算法 如下 : STEP1: 仸選初始拉格朗日乘子 STEP2: 對 ,從 中仸選一個(gè)次梯度 ,若 則停 ,否則 重復(fù) STEP2. ,1t t? ?t? ()tg ?? ts0ts ? 1 m a x { , 0 } , : 1t t ts t t? ? ?? ? ? ? ?注 : 的選取 : ?10: , 0 , ( , 1981 ): , 0 1( ) ( ):|| ||ttttU P LPtt ta t Fi she rbz t z tcs??? ? ? ?????? ? ? ? ?? ? ????停止準(zhǔn)則： :: 0 ( ) , || ||: ( ) ( ): ( )t t tLRU P L PttLRaTb s z o r sc z t z tdz????? ? ? ??迭 代 次 數(shù) 上 限或 在 一 定 步 數(shù) 內(nèi) 變 化 不 超 過 某 給 定 值 拉格朗日啟發(fā)式算法 Step1: 拉格朗日次梯度法求 IP下界 Step2: 對所求解可行化 例 假設(shè)集合覆蓋問題 SC通過前面的松弛得到一個(gè)解 ,當(dāng)其不可行時(shí)即存在 i使得 12( , , )nx x x x?10nij jjax???一個(gè)可行化方法是求 k,滿足 1m i n { | 1 }k j i jjnc c a????重復(fù)以上步驟 ,直到所有行都被覆蓋 . 集合覆蓋問題的拉格朗日松弛算法 : Step1: 初始化 0 ,0t? ?Step2: 計(jì)算 ()tLRz ?Step3: 若所有行被覆蓋 ,stop。在什么條件下該解為 IP的一個(gè)最優(yōu)解？ 定理 的充要條件為： IP LDzz?* 0 ** ( ) 0 , ( * ) ( * , * )T LRx I Pb A x z z x?? ? ??? ? ?存 在 ， 為 可 行 解 ， 使 得 ：三、拉格朗日松弛的整數(shù)性 定義 若 LR的最優(yōu)解與其整數(shù)約束無關(guān)，則稱該問題具有整數(shù)性，即： ( ) m i n{ ( ) }..( ) ( ) m i n{ ( ) }..TTLRnTTLRLnz c x b AxBx dstxZLRL RL z c x b AxBx dstxR??????? ? ???? ? ???與 線 性 松 弛最 優(yōu) 解 相 同 。二、 LR最優(yōu)解和 LP最優(yōu)解的關(guān)系 ( ) ( )TIPx I P c x z?????????TLRn+對 于 給 定 的 0 ，z ( )=min{c x+ (bAx)}（ LR ） 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 C o n Qz c xs t A x b???推論 : 對于仸給 c,整數(shù)規(guī)劃問題 IP和拉 格 朗日對偶問題 LD的目標(biāo)值相等的充要條件為 : ( { | }) ( ) { | }nnCon Q x R A x b Con Q x R A x b??? ? ? ? ? ? ?證 : 顯然有 { | } ( ) { | }nnQ x R Ax b C on Q x R Ax 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 C o n Q x R A x b x C o 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. . . 224IPz x xxxxxxxstxxxZ?? ? ?? ? ???? ? ? ??? ??????? ? ? ?????第一個(gè)約束為復(fù)雜約束 ,其拉格朗日松弛后的模型 LR為 : 121212122( ) m in { ( 7 ) ( 2 2 ) 4 }5 2 02 2 7. . 2 5 .2 .34LRz x xxxxxs t xxxZ? ? ? ??? ? ? ? ? ?? ? ? ? ?????????? ? ??? ?? 4 3 2 1 1 2 3 4 l2 l1 l4 l
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1