【正文】 ? 定理：設(shè)凸優(yōu)化問(wèn)題 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)化問(wèn)題 為準(zhǔn)凸函數(shù)， 為凸函數(shù)。 0()fx0 ( ) ( ) 0 ,Tf x y x y X? ? ? ?X x? 定理：非約束凸優(yōu)化問(wèn)題中，若 可微。 信息與通信工程學(xué)院 莊伯金 70 凸優(yōu)化問(wèn)題最優(yōu)解的微分條件 ? 定理：設(shè) 為凸優(yōu)化問(wèn)題的可行域， 可微。 0()fx 性質(zhì)：凸優(yōu)化問(wèn)題的可行域是凸集。則原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(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)化問(wèn)題的等價(jià)形式 (4) ? 定理：原優(yōu)化問(wèn)題與以下優(yōu)化問(wèn)題等價(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)化問(wèn)題的等價(jià)形式 (5) ? 定理：設(shè) 滿足等式 成立，當(dāng)且僅當(dāng) 。 ( , ) : nmf x y ??R R R( ) ( , )g x f x y dy? ?信息與通信工程學(xué)院 莊伯金 53 廣義不等式下的凸性 ? 廣義單調(diào)性的定義：設(shè) 為真錐，函數(shù) 稱為 單調(diào)增，若函數(shù) 滿足： nK ? R : nf ?RRK? ()fx( ) ( )Kx y f x f y? ? ?? 廣義凸函數(shù)的定義：設(shè) 為真錐，函數(shù) 稱為 凸，若函數(shù) 滿足對(duì) mK ? R : nmf ?RRK? ()fx , d o m , 0 1x y f ?? ? ? ?( ( 1 ) ) ( ) ( 1 ) ( ) .Kf x y f x f y? ? ? ?? ? ? ? ? 均有 ? 定理 (對(duì)偶等價(jià) )： 函數(shù) 為 凸函數(shù)，當(dāng)且僅當(dāng)對(duì)所有 ， 為凸函數(shù)。 ? 推論：函數(shù) 對(duì)每一個(gè) 在 上對(duì)數(shù)凸，則函數(shù) 也是對(duì)數(shù)凸函數(shù)。 ? 定理：函數(shù) 二階可微，則 為對(duì)數(shù)凸函數(shù)當(dāng)且僅當(dāng) 2( ) ( ) ( ) ( ) Tf x f x f x f x? ? ? ?()fx ()fx? 性質(zhì)：對(duì)數(shù)凸性對(duì)函數(shù)加運(yùn)算保持封閉。 ()fx信息與通信工程學(xué)院 莊伯金 48 ? 最小值函數(shù) ? 非負(fù)權(quán)值函數(shù)的最大值函數(shù) 保持準(zhǔn)凸性的算子 ? 復(fù)合函數(shù) 信息與通信工程學(xué)院 莊伯金 49 準(zhǔn)凸函數(shù)的凸函數(shù)族表示 ? 若 為準(zhǔn)凸函數(shù)，根據(jù) 的任意 下水平集，我們可以構(gòu)造一個(gè)凸函數(shù)族 ，使得 ()fx ()fx t()t x?( ) ( ) 0tf x t x?? ? ?? 性質(zhì)：若 為準(zhǔn)凸函數(shù) 的凸函數(shù)族表示，對(duì)每一個(gè) ，若 ，則有 ( ) ( ) .stxx???()fx()t x?domxf? st?信息與通信工程學(xué)院 莊伯金 50 對(duì)數(shù)凸函數(shù) 為凸集 為凸函數(shù)。 f? 定義：集合 信息與通信工程學(xué)院 莊伯金 41 Jensen不等式 ? 為凸函數(shù)，則有： 1 1 1 1( . . . ) ( ) . . . ( )n n n nf x x f x f x? ? ? ?? ? ? ? ?f10 1 , . . . 1 .in? ? ?? ? ? ? ?其中? Jensen不等式的另外形式： ( ( ) ) ( ) ( ) .SSf p x x d x p x f x d x???信息與通信工程學(xué)院 莊伯金 42 保持函數(shù)凸性的算子 ? 凸函數(shù)的逐點(diǎn)最大值 1( ) m a x ( ( ) , . . . , ( ) )nf x f x f x?? 凸函數(shù)與仿射變換的復(fù)合 ( ) ( )g x f A x b??( ) s u p ( , )yf x g x y??A11( ) ( ) . . . ( )nnf x f x f x??? ? ?? 凸函數(shù)的非負(fù)加權(quán)和 信息與通信工程學(xué)院 莊伯金 43 保持函數(shù)凸性的算子 ? 復(fù)合運(yùn)算 : , :( ) ( ( ) )nghf x h g x???R R R Rf? 最小值算子 ( ) i n f ( , )yCg x f x y??? 凸函數(shù)的透視算子 ( , ) ( / )g x t tf x t?信息與通信工程學(xué)院 莊伯金 44 共軛函數(shù) (conjugate function) ? 定義：設(shè)函數(shù) ，其共軛函數(shù) ，定義為 :nf ?RR*dom( ) s u p ( ( ) ) .Txff y y x f x???* : nf ?RR? 共軛函數(shù)的例 共軛函數(shù)具有凸性！ () Tf x a x b??() xf x e?( ) l o gf x x x?信息與通信工程學(xué)院 莊伯金 45 共軛函數(shù)的性質(zhì) ? Fenchel’s inequality *( ) ( ) .Tf x f y y x??? 性質(zhì)：若 為凸函數(shù)，且 的上半圖是閉集，則有 ()fx ()fx** .ff?? 性質(zhì)：設(shè) 為凸函數(shù)，且可微，對(duì)于 ，若 ()fx nzR?()y f z?? 則 * ( ) ( ) ( )Tf y z f z f z? ? ?信息與通信工程學(xué)院 莊伯金 46 準(zhǔn)凸函數(shù) (quasiconvex function) ? 準(zhǔn)凸函數(shù)的例 ? 定義：設(shè)函數(shù) ，若函數(shù)的定義域和任意下水平集 { | ( ) , d o m }S x f x x f? ?? ? ?: nf ?nRR 則稱函數(shù) 為準(zhǔn)凸函數(shù)。 f ?? 定義：集合 信息與通信工程學(xué)院 莊伯金 40 函數(shù)上半圖 (epigraph) ? 定理：函數(shù) 為凸函數(shù) 當(dāng)且僅當(dāng) 的上半圖為凸集。 ? 任一下水平集均為凸集的函數(shù) 不一定 為凸函數(shù)。 K* { | 0 , }TK y x y x K? ? ? ?? 對(duì)偶錐的性質(zhì)： *****1..3.KKKKKKK是閉凸集；2 若 非中空，則 有端點(diǎn)；若 的閉包有端點(diǎn)，則 非中空；4. 是 的閉凸包；真錐的對(duì)偶錐仍然是真錐！ 信息與通信工程學(xué)院 莊伯金 30 對(duì)偶廣義不等式 ? 廣義不等式與對(duì)偶等價(jià)性質(zhì) **, f o r a l l 0 。 ? 定理：若一個(gè)閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。若存在 ，滿足對(duì)任意 ，都有 成立，則稱超平面 為集合 在點(diǎn) 處的支撐超平面。 xS? yS?Kyx? x Syx?信息與通信工程學(xué)院 莊伯金 27 分割超平面 (separating hyperplane) ? 定理：設(shè) 和 為兩不相交凸集，則存在超平面將 和 分離。4. , 05. , .KKKK K KKKKKx y x yxxx y u v x u y vx y x yx y u x u y? ? ???? ? ? ?????足夠小信息與通信工程學(xué)院 莊伯金 26 最值和極值 ? 最小元的定義：設(shè) ，對(duì) ，都有 成立，則稱 為 的最小元。2. 。5. , 0 。3. , 。K具有內(nèi)點(diǎn) K內(nèi)不含直線 信息與通信工程學(xué)院 莊伯金 23 廣義不等式 ? 真錐 下的 偏序關(guān)系 ： KKx y y x K? ? ? ?in tKx y y x K? ? ?? 例： ? 逐項(xiàng)不等式 ? 矩陣不等式 廣義不等式 嚴(yán)格廣義不等式 信息與通信工程學(xué)院 莊伯金 24 廣義不等式的性質(zhì) 1. 。| | ,x x xt x t x tx y x y? ? ???? ? ?當(dāng) 且 僅 當(dāng)；R。 1 2 1 2 1 1 2 2, , , 0 , .x x C x x C? ? ? ?? ? ? ? ?則有? 錐包的定義：集合 C內(nèi)點(diǎn)的所有錐組合。 1 2 1 2, , [0 , 1 ] , ( 1 )x x C x x C? ? ?? ? ? ? ? ?則111, ... , , [ 0 , 1 ] 1 ,kk i iikiiix x CxC?????? ? ? ????且 則信息與通信工程學(xué)院 莊伯金 13 凸集 ? 凸包的定義：包含集合 C的最小的凸集。 a f f { | , 1 }i i i iC x x C??? ? ???? 仿射維數(shù)：仿射包的維數(shù)。 信息與通信工程學(xué)院 莊伯金 7 凸優(yōu)化理論與應(yīng)用 第一章 凸集 信息與通信工程學(xué)院 莊伯金 8 仿射集 (Affine sets) ? 直線的表示： 12( 1 ) , .y x x? ? ?? ? ? ? R.? 線段的表示： 12( 1 ) , [ 0 , 1 ] .y x x? ? ?? ? ? ?信息與通信工程學(xué)院 莊伯金 9 仿射集 (Affine sets) ? 仿射集的定義：過(guò)集合 C內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合 C為仿射集。信息與通信工程學(xué)院 莊伯金 1 凸優(yōu)化理論與應(yīng)用 莊 伯 金 信息與通信工程學(xué)院 莊伯金 2 優(yōu)化理論概述 ? 什么是優(yōu)化問(wèn)題？ 0m in im iz e ( )su b je c t to ( ) , 1 , . . . ,iinfxf x b i mx??? RObjective function Constraint functions 信息與通信工程學(xué)院 莊伯金 3 幾類經(jīng)典的優(yōu)化問(wèn)題 ? 線性規(guī)劃問(wèn)題 ()ifx 為線性函數(shù)? 最小二乘問(wèn)題 20 2( ) , x A x b m ?＝? 凸優(yōu)化問(wèn)題 ()ifx 為凸函數(shù)凸優(yōu)化問(wèn)題理論上有有效的方法進(jìn)行求解！ 信息與通信工程學(xué)院 莊伯金 4 本課程的主要內(nèi)容 ? 理論部分 ? 凸集和凸函數(shù) ? 凸優(yōu)化問(wèn)題 ? 對(duì)偶問(wèn)題 ? 應(yīng)用部分 ? 逼近