拉格朗日松弛算法ppt課件-資料下載頁
2025-04-29 03:17本頁面
【正文】 若 為凹函數(shù) ,在 向量滿足 : 1( ) : mg x R R? * mxR? msR?( * ) ( * ) ( )Tmg x s x x g x x R? ? ? ? ?則稱 為 在 的一個次梯度 ,所有的次梯度集合記為 : ()gxs( *)gx?*x定理 若 為凹函數(shù) , 為 的充要條件為 ()gx *x m a x { ( ) | }mg x x R?0 ( *)gx??定理 設(shè) LR的可行解集合 Q由有限個整數(shù)點組成 ,其極點為 有 : ()kx k K?( * ) m i n { * ( ) }TTLR kKz c x b A x???? ? ?*{ | ( * ) ( ) },{ | , 1 , 0 } ( * )T i T iLRiiii i i LRiII i z c x b A xi I s b A xs s s z???? ? ? ??? ? ? ???? ? ? ? ???*LR記 ：則 對 任 意 為 z ( ) 的 次 梯 度且 ：證明 : **( ) ( * ) ( ) ( )( ) [ ( ) ]( ) ( * )i T T i T iT i T i T i T iLR LRs b A x b A xc x b A x c x b A xzz? ? ? ?????? ? ? ? ?? ? ? ? ? ???注 : 若 不是最大值點 ,則相交的兩個同目標值的平面 滿足 *?1122: ( ) ( ): ( ) ( )T i T iT j T jc x b A x Dc x b A x D? ? ?? ? ?? ? ?? ? ?12* DD? ??且 ,兩平面的法方向交角不超過 90度 . 當 不是光滑點是 ,在 的鄰域內(nèi) ,當 充分小時 ,存在 ,使得 : *? 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: 對 ,從 中仸選一個次梯度 ,若 則停 ,否則 重復(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??? ? ? ?????? ? ? ? ?? ? ????停止準則： :: 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通過前面的松弛得到一個解 ,當其不可行時即存在 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。 or 記 表示第 i行沒有被覆蓋 ,在沒有被覆蓋的行中仸選一行 k,計算 1is ?m in{ | 1 , 1 },k j k j kd a s? ? ? ? 其 中1mtj j ljld c a???? ?Step4 : 1 1 , 2tkkti tiikt t st e pik????? ? ???? ? ?????返 回例 對集合覆蓋問題 1 2 3 41314234m i n 2 3 4 51. . 11{ 0 , 1 } , 1 , 2 , 3 , 4jx x x xxxs t x xx x xxj? ? ?????? ? ???假設(shè) : (1 .5 , 1 .6 , 2 .3 ) T? ?1 2 3 4( ) m in { 1 . 1 0 . 8 0 . 3 1 . 2 } 5 . 3LRz x x x x? ? ? ? ? ? ?()LRz ? 最優(yōu)解為 : ( 1 , 0 , 0 , 0 , ) , ( ) 4 . 2LRxz ???第三行沒有被覆蓋 ,在可覆蓋第三行中選費用最小的列 m i n { 0 . 8 , 0 . 3 ,1 . 2 } 0 . 3? ?? 代 替1231 .5 01 .6 02 .2 0 .3????? ? ? ? ??? ? ? ? ????? ? ? ? ??? ? ? ? ?? ? ? ???1 2 4( ) m i n{ 1. 1 0. 5 0. 9 } 5. 6 4. 5LRz x x xLR? ? ? ? ? ? ?1 3 2 4最 優(yōu) 解 為 :x =x =1 ,x =x
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1