Convex Optimization(Boyd)--Ch3-Convex functions
3。1 基本性質與例子
3。1。1 定義
對於函式
,如果其定義域
是凸集,且對於
均有
,則稱函式
為
凸函式
。
在上式中,若對於
,均有
,則稱函式
為
嚴格凸函式
。
當函式
為凸函式,則稱
為
凹函式
。當函式
為嚴格凸函式,則稱
為
嚴格凹函式
。
所有的仿射函式及時凸函式又是凹函式。反過來,既是凸函式又是凹函式的函式一定是仿射函式。
函式
為凸函式 當且僅當 該函式限制在定義域內任意直線上的時候是凸函式。換言之,
函式 #FormatImgID_14# 為凸函式 的充要條件是 對 #FormatImgID_15# ,函式 #FormatImgID_16# 是凸函式( #FormatImgID_17# )
。這一點性質很有用,可以透過將函式在被限制在直線上時的凹凸性進而判斷函式的凹凸性。
此外,它也可以將證明 #FormatImgID_18# (定義域為多維)的凹凸性轉化為證明 #FormatImgID_19# (定義域為一維)。
3.1.2 值延拓函式
如果函式
是凸函式,定義其延拓(extended-value extentions)為
:
如果函式
是凹函式,定義其延拓(extended-value extentions)為
:
這樣拓展後,不需要每次指出
。
3。1。3 一階條件
假設函式
是可微的(differentiable)。
函式 #FormatImgID_28# 是凸函式 的充要條件是 #FormatImgID_29# 是凸集且對 #FormatImgID_30# 均有 #FormatImgID_31# 。
其意義為 對於凸函式,其一階泰勒近似是該函式的underestimator;
對於 #FormatImgID_32# 時,凸函式f在x處的切線 #FormatImgID_33# 始終在函式影象的下方。
凸函式一階條件的幾何意義
對於嚴格凸函式,可將上述不等式中的
換成
。
函式
是凹函式 的充要條件是
是凸集且對
均有
。
對於嚴格凹函式,要講上述不等式中的
換成
。
證明見原書P70。(思路為先證明n=1時的情況;對於n>1在透過將原函式限制在直線上轉化為n=1時的證明)
3。1。4 二階條件
假設函式
是二階可微的(differentiable),即二階導數(也稱為Hessian矩陣)
存在。
函式
是凸函式 的充要條件是
是凸集且對
,其Hessian矩陣是半正定矩陣(positive semidefinite),即
。
對 #FormatImgID_50# ,均有#FormatImgID_51#
#FormatImgID_52#
#FormatImgID_53# 是嚴格凸函式。反之不成立!!!如
。
函式
是凹函式 的充要條件是
是凸集且對
,其Hessian矩陣是半負定矩陣(negative semidefinite),即
。
3.1.5 一些常見例子
3。1。6 sublevel set和suprlevel set(將凸函式與凸集建立關係的一種方法)
函式
的
被定義為
,也就是定義域中使得函式值不超過
的元素的集合。
對於凸函式, #FormatImgID_71# 取任意值時的sublevel sets均為凸集。反過來不成立!!!(結合3.4理解)
函式
的
被定義為
,也就是定義域中使得函式值不小於
的元素的集合。
對於凹函式,
取任意值時的superlevel sets均為凸集。反過來不成立!!!(結合3.4理解)
上述兩個性質可以用來
判斷某個集合是否為凸集
(透過把這個集合表示為某個凸函式的sublevel set,或者某個凹函式的superlevel set)。
3。1。7 epigraph和hypograph(將凸函式與凸集建立關係的一種方法)
函式
的
函式
的影象被定義為集合
函式
的epigraph被定義為集合
,也就是函式
的影象上面的部分。
一個函式是凸函式的充要條件是其epigraph為凸集。
函式
的hypograph被定義為集合
,也就是函式
的影象下面的部分。
一個函式是凹函式的充要條件是其hypograph為凸集。
凸函式的一些性質可以藉助epigraph和hypograph來進行幾何上的解釋。
3。1。8 Jensen不等式及其拓展
3。1。1中的不等式
有時被稱為Jensen不等式。
可以將其拓展到兩個點以上的凸組合上:如果
函式
是凸函式,
,
且
,則有
。
同樣,可以將上述有限和拓展到
無限求和
、
積分
和
求期望
。
例如:如果在
上有
,且
,則有
。(假設上述積分存在。)如果x是隨機變數,也可以表示為
。
3。1。9 其他不等式
很多關於凸函式的不等式都可以由Jensen不等式匯出。
例如:
均值不等式:
,
Hölder不等式:對於
,有
3。2 對函式而言保凸的運算
3。2。1 非負加權和
若
是凸函式且
,則
是凸函式。
若
是凸函式,則
是凸函式。
多個凸函式的非負加權和:若
是凸函式,則
是凸函式。
可以拓展到
無窮和
以及
積分
。例如若對於
,
是
的凸函式,且
,
,則函式
是凸函式。(
)
3。2。2 與仿射對映的複合函式
設函式
,
,定義函式
,則如果
是凸/凹函式,那麼
也是凸/凹函式。
3。2。3 pointwise maximum(函式的逐點最大值)和pointwise supremum(函式的逐點上界)
凸函式
設
都是凸函式,那麼它們的
pointwise maximum
同樣是凸函式,其中
。
上述性質可以拓展到無窮集下的凸函式成為
pointwise supremum
。若對於
,
是
的
凸
函式,那麼函式
是凸函式,其中
。(證明pointwise supremum函式的epigraph等於各個函式epigraph的交集,凸集的交集還是凸集)
凹函式
設
都是凹函式,那麼它們的
pointwise minimum
同樣是凹函式,其中
。(這一點原書中沒有,我自己加上去的,應該也是對的)
同理可以拓展到凹函式的
pointwise infimum
。若對於
,
是
的
凹
函式,那麼函式
是凹函式,其中
。
這一部分書中的有很多例子可以看一看。如對稱矩陣的最大特徵值、矩陣的譜範數(spectral norm)都可以根據上述方法判定為凸函式。
將函式表示為放射函式的pointwise supremum
上述幾個性質提供了一種證明函式凹凸性的方法:將函式表示為一組affine functions的pointwise supremum。
反之:幾乎每一個凸函式都能表示為一組仿射函式的pointwise supremum。
例如:若
是凸函式且
,則有
。(證明見P83)
3。2。4 複合函式
研究當
且
時,它們的複合函式
的凹凸性。
scalar composition(k=1時)
考慮n=1的情況(其餘情況可以透過restriction on a line來轉化為n=1的情況)。
首先
,考慮函式g和h是二階可微 且
的情況。
可以求出函式
的二階導數:
,可以有以下結論:
其次
,如果 去掉函式g和h是二階可微的條件 或
,有以下結論:
其中
是在
是凸(凹)函式時用
(
)將其拓展到整個
上的延拓函式。
一些常見的例子:
vector composition(
)
若
,
首先
,考慮函式g和h是二階可微 且
的情況。
可以求出函式
的二階導數:
,可以有以下結論:
其次
,對於更一般的情況
必須保證單調條件。
3。2。5 Minimization(對比3。2。3的 pointwise maximum/supremum)
如果函式
對
都是凸函式,且
是一個非空凸集,則函式
是凸函式(假設
),其中
。可以用定義證明。
此外也可以透過epigraph證明,
顯然是個凸集,因為
是
是在某些子維度上的投影。(
高維凸集在某些子維度上的投影仍是凸集
)
3。2。6 函式的投影
設函式
,函式
叫做函式
的投影(perspective):
,其中
。
如果 #FormatImgID_178# 是凸/凹函式,那麼其perspective #FormatImgID_179# 也是凸/凹函式。
可以藉助epigraph/hypograph方便地證明。
例子有資訊理論中可能涉及的相對熵、KL散度的概念。
例子3。20(類比第二章中linear-fractional functions)。假設函式
是凸函式,且
。定義
,其中
。則
也是凸函式。
3。3 共軛函式(*重點)
3。3。1 共軛函式的定義與例子
函式
的
共軛(conjugate)
被定義為:
根據3。2。3,
是一組仿射函式(凸函式)的pointwise supremum,
因此#FormatImgID_189#是凸函式,無論 #FormatImgID_190# 是不是凸函式
。
3。3。2 共軛函式的基本性質
Fenchel不等式
從共軛函式的定義可以得到:
共軛函式的共軛
當
是凸函式且
是closed的(
是closed set),那麼
可微函式
可微函式
的共軛函式也叫做它的
Legendre變換
。(一般條件下的共軛函式和也稱為
Fenchel變換
。)
設
是可微凸函式且
,使得
達到最大值時的
滿足
;反之滿足
的
使
達到最大值。因此,我們有:
也就是說對任意
要確定
時,我們只需要求解
,然後
與仿射函式的縮放和複合
對於
,函式
的共軛函式為
。
若
是非奇異矩陣,
,則函式
的共軛函式為
,其中
獨立函式的和
如果函式
,其中
都是凸函式且他們的共軛函式分別為
,則
。即獨立函式之和的共軛函式等於它們共軛函式的和。
3。4 quasiconvex functions(擬凸函式)
3。4。1 擬凸函式的定義和例子
如果函式
的定義域
以及所有
的sublevel set
都是凸集,則
被稱為
擬凸函式(quasiconvex)
。
如果
是擬凸函式,則
被稱為
擬凹函式(quasiconcave)
。即它的所有superlevel sets
是凸集。
如果一個函式既是擬凸函式也是擬凹函式,那麼它被稱為
擬線性函式(quasilinear)
。如果一個函式是擬線性函式,那麼它的定義域和每個level set
都是凸集。
如果一個定義在
的函式具備擬凸性(quasiconvexity),這要求其每一個sublevel set都是一個區間(可能是無窮區間)。如圖
R上的擬凸函式
凸函式和擬凸函式都具有凸的sublevel sets。
例子:
是quasiconvex,也是quasiconcave的,因此也是quasilinear。(因此擬凸函式也可能是凹函式)
liear-franctional函式
(
)既是quasiconvex的,也是quasiconcave的,因此也是quasilinear的。(見P97)
3。4。2 基本性質
擬凸函式、擬凹函式的Jensen不等式
函式
是quasiconvex的
充要條件
是
是凸集且對
有
。這個不等式也被稱為
擬凸函式的Jensen不等式
。
也就是說
擬凸函式在一條線段上的取值不會超過線段端點取值的最大值
。
函式
是quasiconcave的
充要條件
是
是凸集且對
有
。這個不等式也被稱為
擬凹函式的Jensen不等式
。
也就是說
擬凹函式在一條線段上的取值不會小於線段端點取值的最小值
。
restriction to a line
同凸函式一樣,
#FormatImgID_245# 是quasiconvex的充要條件是 #FormatImgID_246# 在任意直線上的restriction是quasiconvex的。
#FormatImgID_247# 上的連續擬凸函式
連續函式
是擬凸函式的充要條件是 該函式至少滿足以下條件之一:
(1)
是非減的
(2)
是非增的
(3)
,使得:對所有的
,
是非增的;對所有的
,
是非減的。
3。4。3 可微擬凸函式
一階條件
若函式
是可微函式。那麼
是擬凸函式的充要條件是
是凸集且對
有
。
這一不等式的幾何解釋為當
時,
定義了sublevel set
在
點處的支援平面,如下圖:
對於凸函式,若
,則
是
的全域性最小值點;而對於擬凸函式,若
,
未必是
的全域性最小值點。
二階條件
設函式
二階可微。如果
是擬凸函式,那麼對
均有
。
反過來,如果對
均有ww
,那麼
是擬凸函式。、
證明見P101。
3。4。4 保函式quasiconvexity的操作
非負加權的最大
對
,
都是擬凸函式,則
是擬凸函式。
這一性質可以拓展到一般的pointwise supremum:
若對
,
且
是
的凸函式,則
是擬凸函式。
函式的複合
如果
是
非減的
且
是擬凸函式時,它們的複合函式
是擬凸函式。
擬凸函式和仿射函式(或linear-fractional函式)的複合函式仍然是擬凸函式。假設函式
是擬凸函式,則
和
是擬凸函式,其中
。
最小化
如果
對
和
是jointly quasiconvex的,
是一個凸集,則函式
是擬凸函式。
3。4。5 透過一組凸函式來表示
3。5 log-convave(對數凸函式)和log-concave(對數凹函式)
3。5。1 定義
如果對所有
都有
且
是凸函式,那麼則稱
是log-convex的。
同樣如果對所有
都有
且
是凹函式,那麼則稱
是log-concave的。
是log-convex的當且僅當
是log-concave的。
函式 #FormatImgID_310# 是log-convex的充要條件是 #FormatImgID_311# 是凸集且 #FormatImgID_312# 且對 #FormatImgID_313#有
#FormatImgID_314#
。右端為
幾何平均值
。
根據函式的複合法則,當
是凸函式時
也是凸函式,所以
log-convex的函式也是convex的
。
例子:
多元正態分佈的機率密度函式是log-convex的
Gamma函式
在
時事log-convex的
3。5。2 性質
二階可微的log-convex/log-concave函式
對於二階可微函式
,設
是凸集,可以得到
,因此
是log-convex的充要條件是
;
是log-concave的充要條件是
。
乘法、加法、積分
log-convexity和log-concavity 對 乘法和正數縮放是封閉的。
log-concave的函式的和不一定是log-concave的。(!!!)
log-convex函式的和是log-convex的。
拓展到積分形式:一般地,如果對
,
對x都是log-convex的,那麼函式
也是log-convex的。
例如,若
滿足
,那麼
的Laplace變換,
是log-convex的;當滿足
時,
是一個機率密度函式,此時
被稱作
矩生成函式(moment generating functions)
,它的各階導數在
處的取值可以用來計算滿足
分佈的隨機變數的各階矩,而凸函式
被稱為
累積生成函式(cumulant generating functions
),它的各階導數在
處的取值可以用來計算滿足
分佈的隨機變數的各階累積量(一階對應期望,二階對應方差)。
log-concave函式的積分
在一定的條件下,log-concavity可以在積分下保持。
若
是log-concave的,那麼
是log-concave的。
這一結論可以推出雨多重要結論。 例如log-concave的機率密度函式的邊緣分佈(marginal distribution)仍舊是log-concave的。例如log-concave對卷積操作(Convolution)是保持的。例如log-concave機率分佈函式的累積分佈函式(cumulative distribution function)是log-concava的。
3。6 convexity與泛化不等式
3。6。1 單調性與泛化不等式
設
是真錐(proper cone),對應的泛化偏序不等關係為
。函式
是:
K-不減(K-nondecreasing)的,如果
K-增(K-increasing)的,如果
K-不增(K-nonincreasing)的,如果
K-減(K-decreasing)的,如果
梯度條件
對可微函式
,
是K-不減(K-nondecreasing)的
是K-增(K-increasing)的
注意這裡的偏序關係使用的是
對偶不等關係(dual inequality)
定義的。
3。6。2 convexity與泛化不等式
設
是真錐(proper cone),對應的泛化偏序不等關係為
。
函式
是:
K-凸(K-convex)的,如果
,均有
;
嚴格K-凸(strictly K-convex)的,如果
,均有
。
K-凹(K-concave)和嚴格K-凹(strictly K-concave)可類比定義。
K-convexity的對偶特性
是K-convex的
對
,實值函式
都是凸函式;
是strictly K-convex的
對
,實值函式
都是嚴格凸函式;
可微K-convex函式
可微函式
是K-convex的 充要條件是 其定義域為凸集且對
,均有
(其中
是Jacobian矩陣)。
同理可以得到strictly K-convex的充要條件。
複合定理
convexity的複合函式的凹凸性判定中的許多結果都可以一般化到K-convexity。