【正文】 ? ?? ? ?? ? ? ?? ? ? ? ?? 拉格朗日對(duì)偶函數(shù)： 0( , ) TTb A cgo t h e r w i s e? ? ??? ? ? ? ? ??? ???信息與通信工程學(xué)院 莊伯金 101 Twoway partitioning problem ? 原問題： 2m in im iz e ,s u b je c t to 1 , 1 , .. .,Tnix W x W Sx i n???? 拉格朗日函數(shù)： 21( , ) ( 1 ) ( d i a g ( ) ) 1nTiiiTTL x x W x xx W x?????? ? ?? ? ??? 拉格朗日對(duì)偶函數(shù)： 1 d i a g ( ) 0() T Wgo t h e r w i s e??? ? ? ? ??? ???信息與通信工程學(xué)院 莊伯金 102 對(duì)偶函數(shù)與共軛函數(shù) ? 共軛函數(shù) dom* ( ) s u p ( ( ) )Txff y y x f x???? 共軛函數(shù)與對(duì)偶函數(shù)存在密切聯(lián)系 ? 具有線性不等式約束和線性等式約束的優(yōu)化問題： 0m in im iz e ( )s u b je c t to fxA x bC x d?? 對(duì)偶函數(shù)： *0( , ) ( )T T T Tg b d f A C? ? ? ? ? ?? ? ? ? ? ?信息與通信工程學(xué)院 莊伯金 103 Equality constrained norm minimization ? 問題描述： m i n i m i z e s u b j e c t t o xA x b?* *001() yfyo th e r w is e???? ??? 共軛函數(shù)： ? 對(duì)偶函數(shù)： * *01( ) ( )TTTT bAg b f Ao th e r w is e??? ? ?? ? ? ??? ? ? ? ? ?????信息與通信工程學(xué)院 莊伯金 104 Entropy maximization ? 原始問題： n1m in im iz e l o g , s u b je c t to 1 1niiiTx x D RA x bx?? ????? 共軛函數(shù)： 1*0 1() im yif y e??? ?? 對(duì)偶函數(shù) ： *01111( , ) ( 1 ) TiTiTTm aTim aTig b f Abeb e e????? ? ? ? ? ?????? ? ??????? ? ? ? ? ?? ? ? ?? ? ? ???信息與通信工程學(xué)院 莊伯金 105 Minimum volume covering ellipsoid ? 原始問題： 1m in im iz e l o g d e t , s u b je c t to 1 , 1 , . . . ,nTiiX D Sa X a i m??????11l o g d e t( ) 1 0() mm T T Ti i i i i iiia a n a ago th e r w is e? ? ????? ???? ???????? 對(duì)偶函數(shù)： ? 共軛函數(shù)： *10 ( ) l og de t( )f Y Y n?? ? ?信息與通信工程學(xué)院 莊伯金 106 拉格朗日對(duì)偶問題 ? 拉格朗日對(duì)偶問題的描述： m a x i m i z e ( , )s u b j e c t t o 0g ??? ?0( , )g????? ??? 對(duì)偶可行域 *d? 最優(yōu)值 ? 最優(yōu)解 ( *, *)??信息與通信工程學(xué)院 莊伯金 107 LP問題的對(duì)偶問題 ? 標(biāo)準(zhǔn) LP問題 m in im iz e s u b je c t to 0TcxA x bx??? 對(duì)偶函數(shù) 0( , ) TTb A cgo t h e r w i s e? ? ??? ? ? ? ? ?? ????? 對(duì)偶問題 m i n i m i z e ( , )s u b j e c t t o 0g ??? ?m in im iz e ( , )s u b je c t to 0 0TgAc?????? ? ??? 等價(jià)描述 信息與通信工程學(xué)院 莊伯金 108 弱對(duì)偶性 ? 定理（弱對(duì)偶性） ：設(shè)原始問題的最優(yōu)值為 ，對(duì)偶問題的最優(yōu)值為 ，則 成立。 信息與通信工程學(xué)院 莊伯金 109 強(qiáng)對(duì)偶性 ? 強(qiáng)對(duì)偶性并不是總是成立的。若 成立，則稱原始問題和對(duì)偶問題之間具有 強(qiáng)對(duì)偶性 。 ? Slater定理：若凸優(yōu)化問題存在嚴(yán)格可行解，即存在 ，滿足 則優(yōu)化問題具有強(qiáng)對(duì)偶性。 r e l in txD?( ) 0 , 1 , ..., ,if x i mA x b???信息與通信工程學(xué)院 莊伯金 110 強(qiáng)對(duì)偶性 存在 ，滿足 r e l in txD?? 弱化的 Slater條件：若不等式約束條件的前 個(gè)為線性不等式約束條件，則 Slater條件可以弱化為： ( ) 0 , 1 , . . . , ,( ) 0 , 1 , . . . , ,iif x i kf x i k mA x b??? ? ??k信息與通信工程學(xué)院 莊伯金 111 Leastsquares solution of linear equations ? 原問題： m i ni m i z e , subj e c t t o Tnx x xAx b??R? 對(duì)偶問題： 1m a x i m i z e ( )4T T Tg A A b? ? ? ?? ? ?? 具有強(qiáng)對(duì)偶性 信息與通信工程學(xué)院 莊伯金 112 Lagrange dual of QCQP 0 0 0m in im iz e ( 1 / 2 )s u b je c t to ( 1 / 2 ) 0TTTTi i ix P x q x rx P x q x r??? ? ?? QCQP： ? 拉格朗日函數(shù)： 0 0 01 1 11( , ) ( ) ( ) ( )2( ) + ( ) + ( ) +TTm m mi i i i i ii i iL x x P x q x rP P P q q q r r r? ? ? ?? ? ? ? ? ?? ? ?? ? ?? ? ?? ? ?? 對(duì)偶函數(shù)： 11( ) i n f ( , ) ( ) ( ) ( ) ( )2Txg L x q P q r? ? ? ? ? ??? ? ? ?信息與通信工程學(xué)院 莊伯金 113 Lagrange dual of QCQP 11m a x i m i z e ( ) ( ) ( ) ( )2s u b j e c t t o 0Tq P q r? ? ? ??????? 對(duì)偶問題 ： ? Slater條件：存在 ，滿足 x( 1 / 2) 0 , 1 , ...,TTi i ix P x q x r i m? ? ? ?信息與通信工程學(xué)院 莊伯金 114 Entropy maximization ? 原始問題： n1m in im iz e l o g , s u b je c t to 1 1niiiTx x D RA x bx?? ????? 對(duì)偶函數(shù)： 11( , ) TinaTig b e e ??? ? ? ? ????? ? ? ? ?11m a x im iz e s u b je c t to 0TinaTib e e ?????????? ? ???? 對(duì)偶問題 ： 信息與通信工程學(xué)院 莊伯金 115 Entropy maximization ? 弱化的 Slater條件：存在 ，滿足 11TAx bx??0x信息與通信工程學(xué)院 莊伯金 116 Minimum volume covering ellipsoid ? 原始問題： 1m in im iz e l o g d e t , s u b je c t to 1 , 1 , . . . ,nTiiX D Sa X a i m??????? 對(duì)偶函數(shù)： 11l o g d e t( ) 1 0()mm T T Ti i i i i iiia a n a ago th e r w is e? ? ?? ??? ???????????? 對(duì)偶問題： 1m a xi m ize l og de t( ) 1subj e c t to 0m TTiiii a a n????????信息與通信工程學(xué)院 莊伯金 117 Minimum volume covering ellipsoid ? 弱化的 Slater條件總成立，因此該優(yōu)化問題具有強(qiáng)對(duì)偶性。設(shè) 為原始優(yōu)化問題的最優(yōu)解， 為對(duì)偶問題的最優(yōu)解，且兩者具有強(qiáng)對(duì)偶性，則 滿足如下條件： *x**( , )??00( ) , .. ., ( ) , ( ) , .. ., ( )mpf x f x h x h x****** * * * *0111 . ( ) 0 , 1 , .. .,2 . ( ) 0 , 1 , .. .,3 . 0 , 1 , .. .,4 . ( ) 0 , 1 , .. .,5 . ( ) ( ) ( ) 0iiiiipmi i i iiif x i mh x i pimf x i mf x f x h x??????????????? ? ? ? ? ???* * *( , , )x ??KKT條件為必要條件！ 信息與通信工程學(xué)院 莊伯金 121 凸優(yōu)化問題的 KKT條件 可微。 ? 設(shè)原始問題為凸優(yōu)化問題中，函數(shù) ( , )??00( ) , .. ., ( ) , ( ) , .. ., ( )mpf x f x h x h x( , , )x ?? x信息與通信工程學(xué)院 莊伯金 122 例 ? 原始凸優(yōu)化問題 m in im iz e l o g ( )s u b je c t to 0 1 1iiiTxxx?????? KKT條件 * * **** * *0 , 1 1 , 0 ,0 , 1 , .. ., ,1 /( ) 0 , 1 , .. .,Tiii i ixxx i nx i n??? ? ?? ? ???? ? ? ? ? ?信息與通信工程學(xué)院 莊伯金 123 例 其中 *1m a x { 0 , 1 / } 1nii?????? 解得 ****1 / 1 /0 1 /iiiix ? ? ? ???? ??? ???信息與通信工程學(xué)院 莊伯金 124 凸優(yōu)化問題的對(duì)偶求解 存在唯一解