【文章內(nèi)容簡(jiǎn)介】 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)化問題等價(jià) 信息與通信工程學(xué)院 莊伯金 61 優(yōu)化問題的等價(jià)形式 (2) ? 定理：設(shè) 為一一對(duì)應(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)化問題等價(jià) ( d o m )D ???信息與通信工程學(xué)院 莊伯金 62 優(yōu)化問題的等價(jià)形式 (3) ? 定理：設(shè) 為嚴(yán)格單調(diào)增函數(shù)； 滿足 當(dāng)且僅當(dāng) ； 滿足 當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià) 0 0 0m i nim i z e ( ) ( ( ) ) , sub j e c t to ( ) ( ( ) ) 0 , 1 , ... , ( ) ( ( ) ) 0 , i 1 , ...,ni i ii i if z f z zf z f z i mh z h z p?????? ? ?? ? ?R0 :? ?RR 1 , ..., m??( ) 0i u? ? 0u? 1 , ..., p?? ( ) 0i u? ?0u?信息與通信工程學(xué)院 莊伯金 63 優(yōu)化問題的等價(jià)形式 (4) ? 定理：原優(yōu)化問題與以下優(yōu)化問題等價(jià) 0m inim iz e ( ) , su b je c t to ( ) 0 , 1 , ..., 0 ( ) 0 , 1 , ...,niiiif x xf x s i msh x j p?? ? ????R? 稱為松弛變量 s信息與通信工程學(xué)院 莊伯金 64 優(yōu)化問題的等價(jià)形式 (5) ? 定理：設(shè) 滿足等式 成立，當(dāng)且僅當(dāng) 。則原優(yōu)化問題與以下優(yōu)化問題等價(jià) 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 可分離變量?jī)?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)化問題。 0()fx 性質(zhì)：凸優(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??? ? ?? ? ? 等價(jià)于凸優(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)解。 信息與通信工程學(xué)院 莊伯金 70 凸優(yōu)化問題最優(yōu)解的微分條件 ? 定理：設(shè) 為凸優(yōu)化問題的可行域， 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。 0()fx0 ( ) ( ) 0 ,Tf x y x y X? ? ? ?X x? 定理：非約束凸優(yōu)化問題中，若 可微。則 為最優(yōu)解當(dāng)且僅當(dāng) 成立。 0()fxx0 ( ) 0fx??信息與通信工程學(xué)院 莊伯金 71 凸優(yōu)化問題的等價(jià)形式 則 為最優(yōu)解當(dāng)且僅當(dāng) ，且存在向量 滿足 ? 定理：設(shè)凸優(yōu)化問題僅有等式約束 x0 ( ) 0Tf x A v? ? ?0m inim iz e ( ) , su b je c t to nf x xA x b??RxX? v信息與通信工程學(xué)院 莊伯金 72 凸優(yōu)化問題的等價(jià)形式 則 為最優(yōu)解當(dāng)且僅當(dāng) ，且 ? 定理：設(shè)凸優(yōu)化問題 x0 ( ) 0Tf x x??0m inim iz e ( ) , su b je c t to 0nf x xx??RxX?信息與通信工程學(xué)院 莊伯金 73 凸優(yōu)化問題的等價(jià)形式 0m in im iz e ( ) , s u b je c t to ( ) 0 , 1 , . . . , niTf x xf x i mA x b????R 等價(jià)于 ? 定理：設(shè)凸優(yōu)化問題 000m in im iz e ( ) , s u b je c t to ( ) 0 , 1 , . . . ,nif F z x xf F z x i m??? ? ?R 其中 0 TA x b x Fz x? ? ? ?信息與通信工程學(xué)院 莊伯金 74 凸優(yōu)化問題的等價(jià)形式 0m i n i m i z e ( ) , s u b j e c t t o , 1 , . . . ,nTiif x xa x b i m???R 等價(jià)于 ? 定理：設(shè)凸優(yōu)化問題 0m i ni m i z e ( ) , subj e c t t o , 1 , ..., 0 , 1 , ...,nTi i iif x xa x s b i ms i m?? ? ???R信息與通信工程學(xué)院 莊伯金 75 準(zhǔn)凸優(yōu)化問題 為準(zhǔn)凸函數(shù)， 為凸函數(shù)。 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)解。 信息與通信工程學(xué)院 莊伯金 76 準(zhǔn)凸優(yōu)化問題的上半圖形式 ? 設(shè) 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，即 0()fx()t x?0 ( ) ( ) 0tf x t x?? ? ? 則準(zhǔn)凸優(yōu)化問題的可行解問題為 f i nd subj e c t to ( ) 0 , ( ) 0 , 1 , ..., tixxf x i mAx b? ????? 設(shè) 為準(zhǔn)凸優(yōu)化問題的最優(yōu)解，若上述問題可解，則 。否則 。 *p*pt? *pt?信息與通信工程學(xué)院 莊伯金 77 準(zhǔn)凸優(yōu)化問題二分法求解 ? 給定一個(gè)足夠小的 和足夠大的 ，使得區(qū)間 能包含最優(yōu)解 。給定 ul*p? ?,lu0? ?? LOOP： ? 令 ? 求解可行解問題； ? 若可解，則令 ，否則令 ? 若 ，則結(jié)束，否則 goto LOOP。 ( ) / 2t l u??ut? lt?ul ???信息與通信工程學(xué)院 莊伯金 78 線性規(guī)劃 (linear program,LP) ? LP問題的一般描述 m in im iz e s u b je c t to Tc x dG x hA x b???,m n p nGA ????RR信息與通信工程學(xué)院 莊伯金 79 LP問題的幾種類型 ? 標(biāo)準(zhǔn) LP問題 m in im iz e s u b je c t to 0TcxA x bx??? 不等式形式 LP問題 m i ni m i z e su bj e c t t o Tc x dAx b??信息與通信工程學(xué)院 莊伯金 80 標(biāo)準(zhǔn) LP問題的轉(zhuǎn)換 m inim iz e su bje c t to 0 , 0 , 0TTc x c x bG x G x s hA x A x bx x s??????????? ? ???? ? ?信息與通信工程學(xué)院 莊伯金 81 LP問題的例 ? Chebyshev center of a polyhedron ? Piecewiselinear minimization ? Linearfractional programming 信息與通信工程學(xué)院 莊伯金 82 Chebyshev center of a polyhedron { | }nP x R A x b? ? ?? 多面體 ? Chebyshev center：到多面體邊界距離最大的內(nèi)點(diǎn)（最深的點(diǎn)） 2( , ) { | }ccB x r x u u r? ? ?? 問題描述 m