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