【正文】 信息與通信工程學(xué)院 莊伯金 54 作業(yè) (1) ? P116 ? P116 信息與通信工程學(xué)院 莊伯金 55 作業(yè) (2) ? P121 ? P122 (1)(2) 信息與通信工程學(xué)院 莊伯金 56 凸優(yōu)化理論與應(yīng)用 第三章 凸優(yōu)化 信息與通信工程學(xué)院 莊伯金 57 優(yōu)化問題的基本形式 ? 優(yōu)化問題的基本描述： 0m inim iz e ( ) , su b je c t to ( ) 0 , 1 , .. ., ( ) 0 , 1 , ...,niif x xf x i mh x j p?????R優(yōu)化變量 nx?R( ) 0ifx ?不等式約束 等式約束 ( ) 0ihx ? .0mp??無約束優(yōu)化 信息與通信工程學(xué)院 莊伯金 58 優(yōu)化問題的基本形式 最優(yōu)化值 * 0inf { ( ) | ( ) 0 , 1 , .. ., , ( ) 0 , 1 , .. ., }iip f x f x i m h x i p? ? ? ? ?**0 ()p f x?最優(yōu)化解 優(yōu)化問題的域 01d o m d o mpmiiiiD f h???? 可行點 (解 ) (feasible) 滿足約束條件 xD? 可行域 (可解集 ) 所有可行點的集合 信息與通信工程學(xué)院 莊伯金 59 局部最優(yōu)問題 ? 局部最優(yōu)問題 02m in im iz e ( ) , su b je c t to ( ) 0 , 1 , .. ., ( ) 0 , 1 , ..., , 0niif x xf x i mh x j px z R R?????? ? ?R信息與通信工程學(xué)院 莊伯金 60 優(yōu)化問題的等價形式 (1) ? 定理：若 0 0 0m inim iz e ( ) ( ) , su bje c t to ( ) ( ) 0 , 1 , ... , ( ) ( ) 0 , 1 , ...,ni i iiif x f x xf x f x i mh x h x i p????? ? ?? ? ?R0 , 0 , . . . , , 0 , 1 , . . . ,iii m i p??? ? ? ? 則原優(yōu)化問題與以下優(yōu)化問題等價 信息與通信工程學(xué)院 莊伯金 61 優(yōu)化問題的等價形式 (2) ? 定理：設(shè) 為一一對應(yīng)，且 00m inim iz e ( ) ( ( ) ) , su b je c t to ( ) ( ( ) ) 0 , 1 , ... , ( ) ( ( ) ) 0 , 1 , ...,niiiif z f z zf z f z i mh z h z i p?????? ? ?? ? ?R: nn? ?RR 則原優(yōu)化問題與以下優(yōu)化問題等價 ( d o m )D ???信息與通信工程學(xué)院 莊伯金 62 優(yōu)化問題的等價形式 (3) ? 定理：設(shè) 為嚴(yán)格單調(diào)增函數(shù)； 滿足 當(dāng)且僅當(dāng) ； 滿足 當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價 0m in im iz e ( ( ) ) , s u b je c t to ( ( ) ) 0 , 1 , . . . ,nif z xf z i m?????R: kn? ?RR ( ) 0 , 1 , . . . ,ih x j p??()xz??信息與通信工程學(xué)院 莊伯金 65 可分離變量優(yōu)化問題 ? 性質(zhì)： ,in f ( , ) in f ( )x y xf x y f x? 其中 ( ) in f ( , )yf x f x y? 可以分離變量 ? 定理：優(yōu)化問題 0 1 21122m in im iz e ( , ) , s u b je c t to ( ) 0 , 1 , . . . , ( ) 0 , 1 , ...,niif x x xf x i mf x i m?????R12,xx信息與通信工程學(xué)院 莊伯金 66 優(yōu)化問題的上半圖形式 0m in im iz e s u b je c t to ( ) 0 , ( ) 0 , 1 , ..., ( ) 0 , 1 , ...,iitf x tf x i mh x j p??????信息與通信工程學(xué)院 莊伯金 67 凸優(yōu)化問題的基本形式 ? 凸優(yōu)化問題的基本描述： 0m inim iz e ( ) , su b je c t to ( ) 0 , 1 , .. ., ( ) 0 , 1 , ...,niif x xf x i mh x j p?????R 為仿射函數(shù) ()ihx 為凸函數(shù) ()ifx 若 為準(zhǔn)凸函數(shù)，則優(yōu)化問題稱為準(zhǔn)凸優(yōu)化問題。 信息與通信工程學(xué)院 莊伯金 68 凸優(yōu)化問題的例 ? 例： 220 1 221 1 221 1 2m i n i m i z e ( )s u b j e c t t o ( ) / ( 1 ) 0 ( ) ( ) 0f x x xf x x xh x x x??? ? ?? ? ? 等價于凸優(yōu)化問題 220 1 2111 1 2m inim iz e ( )su b je c t to ( ) 0 ( ) 0f x x xf x xh x x x????? ? ?信息與通信工程學(xué)院 莊伯金 69 凸優(yōu)化問題的局部最優(yōu)解 ? 定理：凸優(yōu)化問題的局部最優(yōu)解均是全局最優(yōu)解。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。 1 ( ) , .. ., ( )mf x f x? 準(zhǔn)凸優(yōu)化問題的基本描述 0()fx0m inim iz e ( ) , su b je c t to ( ) 0 , 1 , .. ., ( ) 0 , 1 , ...,niif x xf x i mh x j p?????R? 注：準(zhǔn)凸優(yōu)化問題的局部最優(yōu)解不一定是全局最優(yōu)解。否則 。給定 ul*p? ?,lu0? ?? LOOP： ? 令 ? 求解可行解問題； ? 若可解，則令 ，否則令 ? 若 ，則結(jié)束，否則 goto LOOP。 ,iic a b? 例： 為確定的常數(shù)， 為變量，其范圍滿足 ,icb ia2{ | 1 }i i i ia a P u u?? ? ? ? SOCP形式 2m in im iz e s u b je c t to TTTi i icxa x P x b??信息與通信工程學(xué)院 莊伯金 92 幾何規(guī)劃 (Geometric programming) ? 單項式與多項式 11() naa nf x c x x? ???111() k n kKaaknkf x c x x?? ????? 幾何規(guī)劃的基本描述 0m inim iz e ( )su b je c t to ( ) 1 , 1 , ..., ( ) 1 , 1 , ..., iiniifxf x i mh x i pf h D R???????為多項式， 為單項式,信息與通信工程學(xué)院 莊伯金 93 幾何規(guī)劃的凸形式轉(zhuǎn)換 ? 令 lo giiyx?? 幾何規(guī)劃的凸形式 0000 11m inim iz e ( ) l o g ( )su b je c t to ( ) l o g ( ) 0 , 1 , .. ., ( ) 0 , 1 , ...,TkkTiik ikK a y bkK a y bi kTi i if y ef y e i mh y g y h i p?????? ? ?? ? ? ???信息與通信工程學(xué)院 莊伯金 94 廣義不等式約束 ? 廣義不等式約束的優(yōu)化問題 0m inim iz e ( )su b je c t t o ( ) 0 , 1 , .. ., iiKfxf x i mA x b???? SOCP的描述 12m inim iz e su b je c t to ( , ) 0 , 1 , .. ., {( , ) | }iiTTi i i i KkicxA x b c x d i mF x gK y t R y t?? ? ? ? ??? ? ?信息與通信工程學(xué)院 莊伯金 95 凸優(yōu)化理論與應(yīng)用 第四章 對偶問題 信息與通信工程學(xué)院 莊伯金 96 優(yōu)化問題的拉格朗日函數(shù) ? 設(shè)優(yōu)化問題： 0m inim iz e ( ) , su b je c t to ( ) 0 , 1 , .. ., ( ) 0 , 1 , ...,niif x xf x i mh x j p?????R? 拉格朗日 (Lagrangian)函數(shù)： 011( , , ) ( ) ( ) ( )pmi i i iiiL x f x f x h x? ? ? ???? ? ???? 對固定的 ，拉格朗日函數(shù) 為關(guān)于 和 的 仿射函數(shù) 。 ? 對 和 ，若原最優(yōu)化問題有最優(yōu)值 ，則 0??? ?? *p( , ) *gp?? ?信息與通信工程學(xué)院 莊伯金 98 對偶函數(shù)的例 ? Leastsquares solution of linear equations ? Standard form LP ? Twoway partitioning problem 信息與通信工程學(xué)院 莊伯金 99 Leastsquares solution of linear equations ? 原問題： m i ni m i z e , subj e c t t o Tnx x xAx b??R? 拉格朗日函數(shù)： ( , ) ( )TTL x x x A x b??? ? ?? 拉格朗日對偶函數(shù)： 1()4T T Tg A A b? ? ? ?? ? ?信息與通信工程學(xué)院 莊伯金 100 Standard form LP ? 原問題： m in im iz e s u b je c t to 0TcxA x bx??? 拉格朗日函數(shù)： ( , , ) ( ) ( )T T TT T TL x c x x A x bb c A x? ?