【正文】 ?: nf ?nRR 則稱函數(shù) 為準(zhǔn)凸函數(shù)。 ? 任一下水平集均為凸集的函數(shù) 不一定 為凸函數(shù)。 ? 定理：若一個閉的非中空集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。 xS? yS?Kyx? x Syx?信息與通信工程學(xué)院 莊伯金 27 分割超平面 (separating hyperplane) ? 定理：設(shè) 和 為兩不相交凸集，則存在超平面將 和 分離。2. 。3. , 。| | ,x x xt x t x tx y x y? ? ???? ? ?當(dāng) 且 僅 當(dāng)；R。 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的最小的凸集。 信息與通信工程學(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) ? 仿射集的定義：過集合 C內(nèi)任意兩點(diǎn)的直線均在集合C內(nèi)，則稱集合 C為仿射集。 課程要求 信息與通信工程學(xué)院 莊伯金 6 參考書目 ? Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”, Cambridge University Press. ? 袁亞湘、孫文瑜，“最優(yōu)化理論與方法”，科學(xué)出版社， 1999。 信息與通信工程學(xué)院 莊伯金 11 仿射集 ? 內(nèi)點(diǎn)（ interior）： i n t { | ( , ) , 0 }C x B x r C r? ? ?? 相對內(nèi)點(diǎn)（ relative interior）： r e l i n t { | ( , ) a f f , 0 }C x B x r C C r? ? ? ?信息與通信工程學(xué)院 莊伯金 12 凸集 (Convex Sets) ? 凸集的定義：集合 C內(nèi)任意兩點(diǎn)間的線段均在集合 C內(nèi)，則稱集合 C為凸集。 1{ | , 0 }ki i i iix x C??????信息與通信工程學(xué)院 莊伯金 15 超平面和半空間 ? 超平面 (hyperplane) ： { | }Tx a x b?? 半空間 (Halfspace)： { | }Tx a x b? { | }Tx a x b?信息與通信工程學(xué)院 莊伯金 16 歐氏球和橢球 ? 歐氏球 (euclidean ball): 22( , ) { | } { | ( ) ( ) }ccTccB x r x x x rx x x x x r? ? ?? ? ? ?? 橢球 (ellipsoid): 12{ | ( ) ( ) } , TccE x x x P x x r P?? ? ? ? 為對稱正定矩陣2( , ) { | 1 }ccB x r x r u u? ? ?1 / 22{ | 1 } , cE x A u u A P? ? ? ?信息與通信工程學(xué)院 莊伯金 17 范數(shù)球和范數(shù)錐 ? 范數(shù) (norm)： 0 , 0 0 。2. , 。6. , l i m , l i m .KKKK K KK K KKKi K i i i Kxxx y y x x yx y y z x zx y u v x u y vx y x yx y x x y y x y? ? ??? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ?信息與通信工程學(xué)院 莊伯金 25 嚴(yán)格廣義不等式的性質(zhì) 1. 。 xS? yS??Kxy? x S? 極小元的定義：設(shè) ，對于 ，若 ，則 成立，則稱 為 的極小元。 C 0x C 0a?xC?0TTa x a x?0{ | }TTx a x a x? C 0x? 定理：凸集邊界上任意一點(diǎn)均存在支撐超平面。, f o r a l l 0 , 0 .TTK KTTK Kx y x yx y x y? ? ?? ? ? ?? ? ? ?? ? ? ?? 最小元的對偶特性： * 0 , , .TKx S Kx z z S????為集合 中關(guān)于 偏序的最小元對所有 為使 最小的值信息與通信工程學(xué)院 莊伯金 31 對偶廣義不等式 ? 極小元的對偶特性 * 0 , , .TK x z z S x?? ??為使 最小的值 為極小元反過來不一定成立！ 信息與通信工程學(xué)院 莊伯金 32 作業(yè) ? P60 ? P60 ? P60 ? P62 ? P62 ? P64 ? P64 ? P64 信息與通信工程學(xué)院 莊伯金 33 凸優(yōu)化理論與應(yīng)用 第二章 凸函數(shù) 信息與通信工程學(xué)院 莊伯金 34 凸函數(shù)的定義 為凸集； dom f .( ( 1 ) ) ( ) ( 1 ) ( ) .f x y f x f y? ? ? ?? ? ? ? ?2. ，有 , d o m , 0 1x y f ?? ? ? ? .? 凸函數(shù)的定義：函數(shù) ，滿足 : nf ?nR R .? 凸函數(shù)的擴(kuò)展定義：若 為凸函數(shù)，則可定義其擴(kuò)展函數(shù) 為 f.: { }nf ??nR R .( ) d o m()domf x x ffxxf???? ???凸函數(shù)的擴(kuò)展函數(shù)也是凸函數(shù)！ 信息與通信工程學(xué)院 莊伯金 35 凸函數(shù)的一階微分條件 ? 若函數(shù) 的定義域 為開集，且函數(shù) 一階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對 ( ) ( ) ( ) ( )Tf y f x f x y x? ? ? ?f ffdomfdomf, d o mx y f??信息與通信工程學(xué)院 莊伯金 36 凸函數(shù)的二階微分條件 f? 若函數(shù) 的定義域 為開集，且函數(shù) 二階可微，則函數(shù) 為凸函數(shù)當(dāng)且僅當(dāng) 為凸集，且對 ，其 Hessian矩陣 2 ( ) 0 .fx??f fdomfdomfdomxf??信息與通信工程學(xué)院 莊伯金 37 凸函數(shù)的例 ? 冪函數(shù) , , 1 or x a a??? ? ?R? 負(fù)對數(shù)函數(shù) log x?? 負(fù)熵函數(shù) logxx? 范數(shù)函數(shù) pxaxe? 指數(shù)函數(shù) 信息與通信工程學(xué)院 莊伯金 38 凸函數(shù)的例 1( ) m a x ( , . . . , )nf x x x?2( ) / , 0f x x y y??1( ) l o g ( . . . )nxxf x e e? ? ?1/1( ) ( ) , d o mn nniif x x f ?????? R( ) l og ( de t ) , do m nf X X f S ????信息與通信工程學(xué)院 莊伯金 39 下水平集 (sublevel set) ? 定理：凸函數(shù)的任一下水平集均為凸集。 f fe p i { ( , ) | d o m , ( ) }f x t x f f x t? ? ? 稱為函數(shù) 的上半圖。 ? 定義：函數(shù) 稱為對數(shù)凸函數(shù)，若函數(shù) 滿足： 2 . ( ) 0fx ?()fx ()fx3 . lo g ( )fx? 定理：函數(shù) 的定義域?yàn)橥辜?，? ，則 為對數(shù)凸函數(shù)，當(dāng)且僅當(dāng)對 ()fx ( ) 0fx ? ()fx, d o m , 0 1x y f ?? ? ? ? 有 1( ( 1 ) ) ( ) ( )f x y f x f y???? ?? ? ?? 對數(shù)凸函數(shù)的例 信息與通信工程學(xué)院 莊伯金 51 對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì) ? 性質(zhì)：對數(shù)凸性與凹性對函數(shù)乘積和正數(shù)數(shù)乘運(yùn)算均保持封閉。 ( , )f x y yC? x( ) ( , )Cg x f x y d y? ?信息與通信工程學(xué)院 莊伯金 52 對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì) ? 定理：函數(shù) 為對數(shù)凹函數(shù)，則函數(shù) 是對數(shù)凹函數(shù)。則原優(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)化問題。則 為最優(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。 ? 對 和 ，若原最優(yōu)化問題有最優(yōu)值 ，則 0??? ?? *p(