【正文】 數(shù)，則可定義其擴展函數(shù) 為 f.: { }nf ??nR R .( ) d o m()domf x x ffxxf???? ???凸函數(shù)的擴展函數(shù)也是凸函數(shù)！ 信息與通信工程學院 莊伯金 35 凸函數(shù)的一階微分條件 ? 若函數(shù) 的定義域 為開集，且函數(shù) 一階可微，則函數(shù) 為凸函數(shù)當且僅當 為凸集，且對 ( ) ( ) ( ) ( )Tf y f x f x y x? ? ? ?f ffdomfdomf, d o mx y f??信息與通信工程學院 莊伯金 36 凸函數(shù)的二階微分條件 f? 若函數(shù) 的定義域 為開集，且函數(shù) 二階可微，則函數(shù) 為凸函數(shù)當且僅當 為凸集，且對 ，其 Hessian矩陣 2 ( ) 0 .fx??f fdomfdomfdomxf??信息與通信工程學院 莊伯金 37 凸函數(shù)的例 ? 冪函數(shù) , , 1 or x a a??? ? ?R? 負對數(shù)函數(shù) log x?? 負熵函數(shù) logxx? 范數(shù)函數(shù) pxaxe? 指數(shù)函數(shù) 信息與通信工程學院 莊伯金 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 ????信息與通信工程學院 莊伯金 39 下水平集 (sublevel set) ? 定理：凸函數(shù)的任一下水平集均為凸集。 ? 任一下水平集均為凸集的函數(shù) 不一定 為凸函數(shù)。 { d o m | ( ) }C x f f x? ?? ? ? 稱為 的 下水平集。 f ?? 定義：集合 信息與通信工程學院 莊伯金 40 函數(shù)上半圖 (epigraph) ? 定理：函數(shù) 為凸函數(shù) 當且僅當 的上半圖為凸集。 f fe p i { ( , ) | d o m , ( ) }f x t x f f x t? ? ? 稱為函數(shù) 的上半圖。 f? 定義：集合 信息與通信工程學院 莊伯金 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???信息與通信工程學院 莊伯金 42 保持函數(shù)凸性的算子 ? 凸函數(shù)的逐點最大值 1( ) m a x ( ( ) , . . . , ( ) )nf x f x f x?? 凸函數(shù)與仿射變換的復合 ( ) ( )g x f A x b??( ) s u p ( , )yf x g x y??A11( ) ( ) . . . ( )nnf x f x f x??? ? ?? 凸函數(shù)的非負加權(quán)和 信息與通信工程學院 莊伯金 43 保持函數(shù)凸性的算子 ? 復合運算 : , :( ) ( ( ) )nghf x h g x???R R R Rf? 最小值算子 ( ) i n f ( , )yCg x f x y??? 凸函數(shù)的透視算子 ( , ) ( / )g x t tf x t?信息與通信工程學院 莊伯金 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?信息與通信工程學院 莊伯金 45 共軛函數(shù)的性質(zhì) ? Fenchel’s inequality *( ) ( ) .Tf x f y y x??? 性質(zhì)：若 為凸函數(shù)，且 的上半圖是閉集，則有 ()fx ()fx** .ff?? 性質(zhì)：設(shè) 為凸函數(shù)，且可微，對于 ，若 ()fx nzR?()y f z?? 則 * ( ) ( ) ( )Tf y z f z f z? ? ?信息與通信工程學院 莊伯金 46 準凸函數(shù) (quasiconvex function) ? 準凸函數(shù)的例 ? 定義：設(shè)函數(shù) ，若函數(shù)的定義域和任意下水平集 { | ( ) , d o m }S x f x x f? ?? ? ?: nf ?nRR 則稱函數(shù) 為準凸函數(shù)。 ()fx信息與通信工程學院 莊伯金 47 準凸函數(shù)的判定定理 ? 定理：函數(shù) 為準凸函數(shù)，當且僅當 為凸集，且對 ，有 ()fx( ( 1 ) ) m a x { ( ) , ( ) }f x y f x f y??? ? ?domf, d o m , 0 1x y f ?? ? ? ?? 定理：若函數(shù) 一階可微，則 為準凸函數(shù)，當且僅當 為凸集，且對 ，有 ()fx ()fxdomf , d o mx y f??( ) ( ) ( ) ( ) 0Tf y f x f x y x? ? ? ? ? ，有 ? 定理：若函數(shù) 二階可微，且滿足對 ()fxd o m , , 0nx f y y? ? ? ?R2( ) 0 ( ) 0TTy f x y f x y? ? ? ? ? 則函數(shù) 準凸函數(shù)。 ()fx信息與通信工程學院 莊伯金 48 ? 最小值函數(shù) ? 非負權(quán)值函數(shù)的最大值函數(shù) 保持準凸性的算子 ? 復合函數(shù) 信息與通信工程學院 莊伯金 49 準凸函數(shù)的凸函數(shù)族表示 ? 若 為準凸函數(shù)，根據(jù) 的任意 下水平集，我們可以構(gòu)造一個凸函數(shù)族 ，使得 ()fx ()fx t()t x?( ) ( ) 0tf x t x?? ? ?? 性質(zhì)：若 為準凸函數(shù) 的凸函數(shù)族表示，對每一個 ，若 ，則有 ( ) ( ) .stxx???()fx()t x?domxf? st?信息與通信工程學院 莊伯金 50 對數(shù)凸函數(shù) 為凸集 為凸函數(shù)。 ? 定義：函數(shù) 稱為對數(shù)凸函數(shù)，若函數(shù) 滿足： 2 . ( ) 0fx ?()fx ()fx3 . lo g ( )fx? 定理：函數(shù) 的定義域為凸集，且 ，則 為對數(shù)凸函數(shù)，當且僅當對 ()fx ( ) 0fx ? ()fx, d o m , 0 1x y f ?? ? ? ? 有 1( ( 1 ) ) ( ) ( )f x y f x f y???? ?? ? ?? 對數(shù)凸函數(shù)的例 信息與通信工程學院 莊伯金 51 對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì) ? 性質(zhì)：對數(shù)凸性與凹性對函數(shù)乘積和正數(shù)數(shù)乘運算均保持封閉。 ? 定理：函數(shù) 二階可微，則 為對數(shù)凸函數(shù)當且僅當 2( ) ( ) ( ) ( ) Tf x f x f x f x? ? ? ?()fx ()fx? 性質(zhì)：對數(shù)凸性對函數(shù)加運算保持封閉。但對數(shù)凹性對函數(shù)加運算不封閉。 ? 推論：函數(shù) 對每一個 在 上對數(shù)凸，則函數(shù) 也是對數(shù)凸函數(shù)。 ( , )f x y yC? x( ) ( , )Cg x f x y d y? ?信息與通信工程學院 莊伯金 52 對數(shù)凸函數(shù)和凹函數(shù)的性質(zhì) ? 定理：函數(shù) 為對數(shù)凹函數(shù)，則函數(shù) 是對數(shù)凹函數(shù)。 ( , ) : nmf x y ??R R R( ) ( , )g x f x y dy? ?信息與通信工程學院 莊伯金 53 廣義不等式下的凸性 ? 廣義單調(diào)性的定義：設(shè) 為真錐，函數(shù) 稱為 單調(diào)增，若函數(shù) 滿足： nK ? R : nf ?RRK? ()fx( ) ( )Kx y f x f y? ? ?? 廣義凸函數(shù)的定義：設(shè) 為真錐，函數(shù) 稱為 凸，若函數(shù) 滿足對 mK ? R : nmf ?RRK? ()fx , d o m , 0 1x y f ?? ? ? ?( ( 1 ) ) ( ) ( 1 ) ( ) .Kf x y f x f y? ? ? ?? ? ? ? ? 均有 ? 定理 (對偶等價 )： 函數(shù) 為 凸函數(shù)，當且僅當對所有 ， 為凸函數(shù)。 ()fx K?* 0Kw ?()Tw f x信息與通信工程學院 莊伯金 54 作業(yè) (1) ? P116 ? P116 信息與通信工程學院 莊伯金 55 作業(yè) (2) ? P121 ? P122 (1)(2) 信息與通信工程學院 莊伯金 56 凸優(yōu)化理論與應用 第三章 凸優(yōu)化 信息與通信工程學院 莊伯金 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)化 信息與通信工程學院 莊伯金 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? 可行域 (可解集 ) 所有可行點的集合 信息與通信工程學院 莊伯金 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信息與通信工程學院 莊伯金 60 優(yōu)化問題的等價形式 (1) ? 定理：若 0 0 0m inim iz e ( ) ( ) , su bje c t to ( ) ( ) 0 , 1 , ... , ( ) ( ) 0 , 1 , ...,ni i