拉格朗日松弛算法ppt課件(存儲版)
【正文】 不為零 ,如在例 , ,在 達(dá)到拉格朗日對偶問題的最優(yōu)值 ,其最優(yōu)解為 (4,0)。 11m in(). .0 1 , 1 , 2 ,nmLS C j j ijijz d xLS Cs t x j n???? ????? ? ? ????定理 若 LR具有整數(shù)性，則 ? 整數(shù)規(guī)劃問題和它的拉格朗日松弛分別為 ? 按定理 ? 定理 ? 在例 ? 例 （續(xù)例 ）繼續(xù)例 ，將式（ ）中的約束 四、 拉格朗日分解 1m inm in m in{ ( ) }.... ..,( ) m in{ }( 5 .3 .8 )..TIPT TTIPnnnTTLRnz c xz c x c x x yA x bA x bA x bxys t B y ds t B x d stB y dx y ZxZx y Zz c x x zandA x bstxZ????????? ?? ?? ?????? ????? ? ? ? ??? ?? ? ? ???? ? ? ??? ? ? ??????? ?? ??????2( ) m in{ }( 5 .3 .9 )..TLRnyB y dstyZ???????1212( ) ( )m a x ( ) ( )LR LR I PLD LR LRz z zz z z?????????有 ：其 對 偶 形 式 ：? 例 拉格朗日松弛算法 次梯度算法（ subgradient optimization） 定義： （ 凹函數(shù)） 函數(shù) 滿足以下條件稱為凹函數(shù) 1: mg R R?( ( 1 ) ) ( ) ( 1 ) ( ) , mg x y g x g y x y R? ? ? ?? ? ? ? ? ? ?定理 若 LR的可行解集合 Q為有限個實(shí)數(shù)點(diǎn)集，則以下函數(shù)為凹函數(shù) ( ) m in{ ( ) | }TTLRz c x b A x x Q??? ? ? ?定理 函數(shù)為凹函數(shù)的充要條件為： 1* , ( , ) ,( * ) ( ) ( * )mTmTmx R s s sg x g x s x x x R? ? ? ?? ? ? ? ?使 得 ：證明 必要性：設(shè) 為凹函數(shù)，則 ()gx?? 1 1 2 21 1 2 2 1 2 1 21 2 1 2 1 2( , ) | ( ) ( , ) , ( , )( , ) ( 1 ) ( , ) ( ( 1 ) , ( 1 ) ) :( ( 1 ) ) ( ) ( 1 ) ( ) ( 1 )H x z z g x a n d x z x z Hx z x z x x z zg x x g x g x z z? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? ?有 :滿 足H為凸集 , 為邊界點(diǎn) ,所以存在過 和法方向 的支撐超平面 滿足 : ( *, ( *))x g x ( *, ( *))x g xs ?( * ) ( ) ( * )Tmg x g x s x x x R? ? ? ? ?充分性 : 1 2 1 2, , 0 1 , * ( 1 )x x x x x? ? ?? ? ? ? ? ? 有 ：1 1 2 21 2 1 212( * ) ( ) ( * ) , ( * ) ( ) ( * )( * ) ( ( 1 ) * ) ( ) ( 1 ) ( )( * ) ( ) ( 1 ) ( )TTTg x g x s x x g x g x s x xg x s x x x g x g xg x g x g x? ? ? ???? ? ? ? ? ?? ? ? ? ? ? ?? ? ?則 有 ：即 ：A B C 3S4S?()LRz ?()LRz ? 函 數(shù) 示 意 圖定義 若 為凹函數(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ù)點(diǎn)組成 ,其極點(diǎn)為 有 : ()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? ? ? ?????? ? ? ? ?? ? ? ? ? ???注 : 若 不是最大值點(diǎn) ,則相交的兩個同目標(biāo)值的平面 滿足 *?1122: ( ) ( ): ( ) ( )T
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1