一些簡單的凸分析

基本概念與基本性質

組合 Combination

Linear Combination 線性組合:係數無要求;
Affine Combination 仿射組合:係數之和為1,可正可負;
Conical Combination 錐組合:係數為非負;
Convex Combination 凸組合:係數為非負,且和為1。

仿射函數/線性函數

線性函數:ax+byax+by。線性函數不可以有額外的常數項。
仿射函數:ax+by+cax+by+c。仿射函數是線性函數的平移。

在經濟學的語言中,常常將仿射函數稱為線性函數,從數學上來説這是不對的,但往往遵循慣例。

凸函數的幾何刻畫

凸函數常有兩種幾何刻畫:

  1. 兩點連線處於函數圖像之上。

  2. 某點切線位於函數圖像之下。

連線、切線只是一種廣義的説法,具體的形式因維度而定,例如在高維中的切線其實是相切的超平面。

Chordal Slope Lemma

令(a,b)∈R(a,b)\in\mathbb{R}為一個開區間,f:(a,b)→Rf:(a,b)\rightarrow\mathbb{R}為一個凸函數。則對於定義域內任何三個滿足x<y<zx<y<z的點x,y,z∈(a,b)x,y,z\in (a,b)都有

f(y)−f(x)y−x≤f(z)−f(x)z−x≤f(z)−f(y)z−y\frac{f(y)-f(x)}{y-x}\leq\frac{f(z)-f(x)}{z-x}\leq\frac{f(z)-f(y)}{z-y}

特別地,給定任何x0∈(a,b)x_{0}\in (a,b),函數x→f(x)−f(x0)x−x0x\rightarrow\frac{f(x)-f(x_{0})}{x-x_{0}}是遞增的。

(三條線各自均為兩點連線,可以將斜率處於中間的那條兩點連線視為斜率最陡峭和最平緩的兩條兩點連線的加權平均,斜率處於中間者,是斜率最陡峭和最平緩的兩條兩點連線拼接而成。)

證明:

y(z−x)=zy−xy=zy−zx+zx−xy=z(y−x)+x(z−y)\begin{aligned} y(z-x)=&zy-xy\\ =&zy-zx+zx-xy\\ =&z(y-x)+x(z-y) \end{aligned}

從而

y=y−xz−xz+z−yz−xxy=\frac{y-x}{z-x}z+\frac{z-y}{z-x}x

其中z−yz−x=1−y−xz−x\frac{z-y}{z-x}=1-\frac{y-x}{z-x},
由x<y<zx<y<z可知y−xz−x∈(0,1)\frac{y-x}{z-x}\in (0,1),從而上式即是將yy表示成zz和xx的凸組合的表達式,根據ff為凸函數,可知

f(y)≤y−xz−xf(z)+z−yz−xf(x)=y−xz−x(f(z)−f(x))+f(x)\begin{aligned} f(y)\leq&\frac{y-x}{z-x}f(z)+\frac{z-y}{z-x}f(x)\\ =&\frac{y-x}{z-x}(f(z)-f(x))+f(x) \end{aligned}

從而

f(y)−f(x)≤y−xz−x(f(z)−f(x))f(y)-f(x)\leq\frac{y-x}{z-x}(f(z)-f(x))

即

f(y)−f(x)y−x≤f(z)−f(x)z−x\frac{f(y)-f(x)}{y-x}\leq\frac{f(z)-f(x)}{z-x}

但

f(y)≤y−xz−xf(z)+z−yz−xf(x)f(y)\leq\frac{y-x}{z-x}f(z)+\frac{z-y}{z-x}f(x)

又可以表示為

f(y)≤z−yz−x(f(x)−f(z))+f(z)f(y)\leq\frac{z-y}{z-x}(f(x)-f(z))+f(z)

從而

f(x)−f(z)x−z≤f(z)−f(y)z−y\frac{f(x)-f(z)}{x-z}\leq\frac{f(z)-f(y)}{z-y}

得證。

這意味著,當把x−hx-h視為前面的xx、xx視為前面的yy、x+hx+h視為前面的zz時,有

f′(x−)=lim⁡h→0f(x)−f(x−h)h≤lim⁡h→0f(x+h)−f(x)h=f′(x+)\begin{aligned} f^{\prime}(x^{-})&=\lim_{h\rightarrow 0}\frac{f(x)-f(x-h)}{h}\\ &\leq\lim_{h\rightarrow 0}\frac{f(x+h)-f(x)}{h}=f^{\prime}(x^{+}) \end{aligned}

即凸函數任何內點x∈(a,b)x\in (a,b)的右極限總是不小於左極限,當屬於間斷點時右極限嚴格高於左極限。
進一步地

f′(x−)≤f′(x+)≤f(y)−f(x)y−x≤f′(y−)≤f′(y+)f^{\prime}(x^{-})\leq f^{\prime}(x^{+}) \leq\frac{f(y)-f(x)}{y-x} \leq f^{\prime}(y^{-})\leq f^{\prime}(y^{+})

因此,凸函數任何內點x∈(a,b)x\in (a,b)的左導數和右導數總是有界的:∣f′(x−)∣<∞|f^{\prime}(x^{-})|<\infty,∣f′(x+)∣<∞|f^{\prime}(x^{+})|<\infty從而上述命題凸函數內點的右極限總是不小於左極限,當屬於間斷點時右極限嚴格高於左極限中的“間斷點”可以進一步限制為跳躍間斷點(即凸函數的內點不會是無窮間斷點)。

Supergradient

參考 KC Border。

令 CC 為 mm 維歐氏空間的凸子集,ff 為定義在 CC 上的凹函數。稱(同樣為 mm 維的)向量 pp 是函數 ff 在點 x∈Cx\in C 處的 supergradient, 如果對於任何向量 yy,都有 f(x)+p⋅(y−x)≥f(y)f (x) + p · (y − x) \geq f (y)。

supergradient 是 gradient 概念的推廣。

supergradient

把不等式取相反符號,即為 subgradient。

命題:定義在開區間上的凸函數都是連續函數

令f:(a,b)→Rf:(a,b)\rightarrow\mathbb{R}為凸函數,則對於任何[x‾,xˉ]⊂(a,b)[\underline{x},\bar{x}]\subset(a,b),ff都是李普希茨連續的,因此ff在[x‾,xˉ][\underline{x},\bar{x}]上也是絕對連續的。

證明:

(待補充)

命題

命題:凸函數的幾乎處處連續可微性質。

定義:極點 Extreme Point

令S⊂RnS\subset\mathbb{R}^{n}為nn維歐氏空間的凸子集,那些無法被SS裡的點們由非平凡凸組合得到的點就是極點(這裡的平凡是指:就令所選取的點的權重為1,其他任意點的權重為0,依然是凸組合,但冇有實際意義)。如三角形的三個頂點、矩形的四個角、立方體的八個角等等都是極點。但任一條邊都可以被那條邊的端點組合而成,所以邊上的點不是極點。將SS的極點們記為ext(S)\text{ext}(S)。

凹凸性與擬凹凸性

凹凸性是基數性質,在單調變換下可能會發生改變。而擬凹凸性是敘述性質,可以在單調變化下保留。例如,無論是凹函數還是擬凹函數,在單調正變換後都將變成擬凹函數。

Polyhedra

給定超平面 H⊂RdH\subset\mathbb{R}^{d},記 H−H^{-} 和 H+H^{+} 分別為超平面的兩個閉半空間。至於是大於等於的記為正、還是小於等於的記為正具有任意性。一個 Polyhedron 是能被表示為有限多個閉半空間的交集的集合。一個 Polytope 是有限多個點的凸包。一個 Polyhedral cone 是一個有限多個點的正包,即只要求係數為正、不要求合為一(因此不是凸包)。

凸集表示定理

凸集表示定理(一)Minkowski 定理

給定有限維向量空間EE,X⊂EX\subset E為緊凸子集,則對於任何x∈Xx\in X,都存在有限個x1,...,xk∈ext(X)x_{1},...,x_{k}\in\text{ext}(X)和正數μ1,...,μk\mu_{1},...,\mu_{k}滿足∑iμi=1\sum_{i}\mu_{i}=1,使得∑iμixi=x\sum_{i}\mu_{i}x_{i}=x。

定義:表示 Representation

如前述Minkowski 定理中那般,對於某個x∈Xx\in X,如果存在有限個x1,...,xk∈ext(X)x_{1},...,x_{k}\in\text{ext}(X)和正數μ1,...,μk\mu_{1},...,\mu_{k}滿足∑iμi=1\sum_{i}\mu_{i}=1,使得∑iμixi=x\sum_{i}\mu_{i}x_{i}=x,則稱xx通過{μi}i\lbrace \mu_{i}\rbrace _{i}得到了(凸)表示。

積分形式為:

對於定義在XX上的任何連續線性(註意,這裡不限制為有限維空間,因此線性不意味著連續,而線性連續等價於線性有界)泛函ff,和某個x∈Xx\in X,如果f(x)=∫Xfdμf(x)=\int_{X}fd\mu對於某個機率測度μ\mu都成立,則稱xx通過μ\mu得到了表示。

因此Minkowski 定理也可以敘述為:

對於有限維向量空間中的緊凸子集,其任一元素都可以使用其極點得到表示。

凸集表示定理(二)Caratheodory 定理

對於任何有限維度n∈Nn\in\mathbb{N},令S⊂RnS\subset\mathbb{R}^{n}為nn維歐氏空間的子集,則SS的凸包co(S)co(S)中的任一點x∈co(S)x\in co(S),都存在n+1n+1個點{xi}i=1n+1⊂S\lbrace x^{i}\rbrace _{i=1}^{n+1}\subset S和{λi}i=1n+1⊂[0,1]\lbrace \lambda_{i}\rbrace _{i=1}^{n+1}\subset [0,1](如果其中有某些λj=0\lambda_{j}=0,那就意味著只需要少於n+1n+1個xix^{i}),滿足∑i=1n+1λi=1\sum_{i=1}^{n+1}\lambda_{i}=1(意味著權重非負、和為11,因此是凸組合),使得x=∑i=1n+1λixix=\sum_{i=1}^{n+1}\lambda_{i}x^{i}。

即:對於任何有限nn維空間裡的任一集合SS,其凸包co(S)co(S)中的任一點都可由原SS中不多於n+1n+1個點的凸組合來表示。

證明:假設用了m≥n+2m\geq n+2個點來做凸組合,即x=∑i=1mλixix=\sum_{i=1}^{m}\lambda_{i}x^{i},{xi}i=1m⊂S\lbrace x^{i}\rbrace _{i=1}^{m}\subset S,{λi}i=1m⊂[0,1]\lbrace \lambda_{i}\rbrace _{i=1}^{m}\subset [0,1],∑i=1mλi=1\sum_{i=1}^{m}\lambda_{i}=1。假設每個λi>0,∀i=1,...,m\lambda_{i}>0,\forall i=1,...,m,否則有等於00的權重就意味著已經只使用了少於mm個點。

但即使{xi}i=1m\lbrace x^{i}\rbrace _{i=1}^{m}不是線性相關的,任取一個xkx^{k},{xi−xk}i≠k\lbrace x^{i}-x^{k}\rbrace _{i\neq k}也是線性相關的,因此存在一組{μi}i≠k⊂R\lbrace \mu_{i}\rbrace _{i\neq k}\subset\mathbb{R},並且μi\mu_{i}不全為0,使得

∑i≠kμi(xi−xk)=0\sum_{i\neq k}\mu_{i}(x^{i}-x^{k})=0

如果我們取μk=−∑i≠kμi\mu_{k}=-\sum_{i\neq k}\mu_{i}則有

∑i=1mμi=0\sum_{i=1}^{m}\mu_{i}=0

以及

0=∑i≠kμi(xi−xk)=∑i≠kμixi−∑i≠kμixk=∑i≠kμixi+μkxk=∑i=1mμixi\begin{aligned} 0=\sum_{i\neq k}\mu_{i}(x^{i}-x^{k})=&\sum_{i\neq k}\mu_{i}x^{i}-\sum_{i\neq k}\mu_{i}x^{k}\\ =&\sum_{i\neq k}\mu_{i}x^{i}+\mu_{k}x^{k}\\ =&\sum_{i=1}^{m}\mu_{i}x^{i} \end{aligned}

目前我們已經有了x=∑i=1mλixix=\sum_{i=1}^{m}\lambda_{i}x^{i}和∑i=1mμixi=0\sum_{i=1}^{m}\mu_{i}x^{i}=0,那麼對於任一實數α∈R\alpha\in\mathbb{R}都有

x=∑i=1mλixi−α∑i=1mμixi=∑im(λi−αμi)xix=\sum_{i=1}^{m}\lambda_{i}x^{i}-\alpha\sum_{i=1}^{m}\mu_{i}x^{i}=\sum_{i}^{m}(\lambda_{i}-\alpha\mu_{i})x^{i}

既然這個式子對任一α\alpha都成立,那麼我們可以選取特定的某個α\alpha,即

α=min⁡i=1,...,m{λiμi∣μi>0}\alpha=\min_{i=1,...,m}\lbrace \frac{\lambda_{i}}{\mu_{i}}|\mu_{i}>0\rbrace

即只在那些μi>0\mu_{i}>0的組裡選,而xkx^{k},{xi−xk}i≠k\lbrace x^{i}-x^{k}\rbrace _{i\neq k}的線性相關保證了至少有一個μi>0\mu_{i}>0。我們將這些λiμi\frac{\lambda_{i}}{\mu_{i}}中取到最小值的那一組記為第ll組,那麼

α=λlμl\alpha=\frac{\lambda_{l}}{\mu_{l}}

因此λi−αμi≥0,∀i\lambda_{i}-\alpha\mu_{i}\geq 0,\forall i,但λl−αμl=0\lambda_{l}-\alpha\mu_{l}=0。

這樣就把mm個向量的凸組合變成了m−1m-1個向量的凸組合。可以將這個過程一直持續下去。那麼這個過程應該到什麼時候停止呢?

應該到{xi−xk}i\lbrace x^{i}-x^{k}\rbrace _{i}不再線性相關了為止。

而每個xix^{i}都是取自Rn\mathbb{R}^{n},因此最多可以有nn個線性不相關的xi=xi−xkx^{i}=x_{i}-x_{k},也就是最多可以有n+1n+1個xjx_{j}使得nn個xi=xi−xkx^{i}=x_{i}-x_{k}線性不相關,即要表示xx,最多需要{xj}j=1n+1\lbrace x_{j}\rbrace _{j=1}^{n+1}。當然,這只是說最多需要n+1n+1個,在不同的情景中可以只需要更少,但永遠不需要更多。

特殊情況:邊界點

對於 S⊂RnS\subset\mathbb{R}^{n},記 C:=coSC:=\text{co}S。如果 x∈C∩boudaryCx\in C\cap \text{boudary}C,那麼如果想要將這種特別的 xx 表示為其它元素的凸組合,無需像 Carathedory 那樣要求 n+1n+1 個元素,而只需 nn 個就好了。

證明: 由於 x∈dbCx\in\text{db}C,根據支撐超平面定理,存在超平面 Hs,rH_{s,r},其中 s≠0,r∈Rs\neq 0,r\in\mathbb{R},使得

<s,x>−r=0<s,x>-r=0

並且

<s,y>−r≤0,∀y∈C<s,y>-r\leq 0,\forall y\in C

由於 x∈Cx\in C,根據 Caratheodory 定理,存在 x1∈S,...xi∈S,...,xn+1∈Sx_{1}\in S,...x_{i}\in S,...,x_{n+1}\in S 以及 α1>0,...αi>0,...,αn+1>0\alpha_{1}>0,...\alpha_{i}>0,...,\alpha_{n+1}>0 使得 x=∑j=1n+1αjxjx=\sum_{j=1}^{n+1}\alpha_{j}x_{j}。代入 y=xjy=x_{j},得

0=<s,x>−r=∑j=1n+1αj(<s,xj>−r)≤00=<s,x>-r=\sum_{j=1}^{n+1}\alpha_{j}(<s,x_{j}>-r)\leq 0

因此必有 <s,xj>−r=0,∀j=1,...,n+1<s,x_{j}>-r=0,\forall j=1,...,n+1,這意味著每個 xjx_{j} 都滿足超平面 Hs,rH_{s,r} 的定義式 <s,x>−r=0<s,x>-r=0。而超平面 Hs,rH_{s,r} 的維度為 n−1n-1 (x∈Rnx\in\mathbb{R}^{n} 本身處於維度為 nn 的空間內,<s,x>−r=0<s,x>-r=0 的約束使得維度減 11)。

這表明 xx 只需用超平面 Hs,rH_{s,r} 上的點的凸組合,就可以表示。根據 Caratheodory 定理,xx 可以表示為 (n−1)+1(n-1)+1 個點的凸組合,得證。 □\square

凸集表示定理(三)Krein Milman 定理

  1. 版本一
    對於任何非空緊凸集S⊂RnS\subset\mathbb{R}^{n},將SS的極點們記為ext(S)={si}j\text{ext}(S)=\lbrace s_{i}\rbrace _{j},則co({si}i)=S\text{co}(\lbrace s_{i}\rbrace ^{i})=S。

  2. 版本二

證明:我們將採用歸納法證明。

當n=1n=1時,非空緊凸集既是實端點的閉區間,其極點即是端點,極點的凸包即是這個區間。

假設對於n−1n-1成立,我們表明對於nn也成立。假設不成立,即S∖co(ext(S))≠∅S\setminus \text{co}(\text{ext}(S))\neq\emptyset,那麼

結合Caratheodory定理和Krein Milman定理,可知在nn維歐氏空間Rn\mathbb{R}^{n}中的任何非空緊凸集中的任一點,都可以被寫為其極點們中至多n+1n+1個的凸組合。

凸集表示定理(四)Choquet integral representation

給定EE為局部凸空間,X⊂EX\subset E為可度量化的緊凸子集,任給x0∈Xx_{0}\in X,都存在某個定義在XX上的機率測度μ\mu可以表示x0x_{0}(意即f(x0)=∫Xf(x)dμ(x)f(x_{0})=\int_{X}f(x)d\mu(x)對於任何連續仿射函數ff都成立),並且μ\mu集中在XX的極點上:μ(ext⁡X)=1\mu(\operatorname{ext}X)=1。這裡不能理解為每個極點都有正質量;一般地,拓撲支撐只需包含在ext⁡X‾\overline{\operatorname{ext}X}中。

Bauer 最大值原理

給定任何賦範線性空間XX中的任何非空緊凸子集S⊂XS\subset X,若f:S→Rf:S\rightarrow\mathbb{R}是上半連續(是semi,不是hemi)的凸函數(註意,這裡定義域是緊集,因此凸函數並不自動意味著連續函數),則集合SS的極點ext(S)ext(S)中至少存在一個點,使得函數ff在該點取得最大值

arg⁡max⁡x∈Sf(x)∩ext(S)≠∅\arg\max_{x\in S}f(x)\cap ext(S)\neq\emptyset

例子

(待補充)

(補上 Kleiner, A., Moldovanu, B., & Strack, P. (2020). Extreme Points and Majorization: Economic Applications. Available at SSRN.)

分離定理與支撐超平面定理

(待補充)

分離超平面定理

任取兩個非空凸集A,B⊂RnA,B\subset\mathbb{R}^{n},並且其中任一個具有非空內部,不妨令int(A)≠∅int(A)\neq\emptyset,那麼AA的內部int(A)int(A)與BB不相交即int(A)∩B=∅int(A)\cap B=\emptyset當且僅當可以找到一個各分量不全為00的向量$v\in\mathbb{R}^{n}\setminus\lbrace 0\rbrace 和一個實數和一個實數\alpha\in\mathbb{R}$使得

vTy≥α≥vTx,∀y∈B,x∈Av^{T}y\geq\alpha\geq v^{T}x,\forall y\in B,x\in A

若從AA的內部取點x∈int(A)x\in int(A),則後一個不等號取嚴格

α>vTx,∀x∈int(A)\alpha > v^{T}x,\forall x\in int(A)

(若令int(B)≠∅int(B)\neq\emptyset,則是前一個不等號取嚴格)

支撐超平面定理

(待補充)

supporting hyperplanes to epigraphs

(待補充)

避免誤解

注意!!!儘管二階連續可微的函數 f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} 是凸函數當且僅當其海塞矩陣為半正定,但嚴格凸函數僅僅是海塞矩陣正定的必要而非充分條件,或者說海塞矩陣正定是嚴格凸函數的充分而非必要條件。

例如 f(x)=x4f(x)=x^{4} 是嚴格凸函數,但 f′′(0)=0f^{\prime\prime}(0)=0。這是一個極其容易被誤用的性質!!!有很多老師會把嚴格凸函數時的海塞矩陣正定説成充要條件!!!這是錯的!!!

另外,“二階連續可微”這個性質也不可少。當然,可微性的假設要求定義域是開集,正如凸函數的假設要求定義域是凸集。

即使是一維歐式空間定義域(單變量)的嚴格凸函數,其充要條件也僅僅是 {x∈R:f′′(x)>0}\left\{x\in\mathbb{R}:f^{\prime\prime}(x)>0\right\} 為稠密集而已!!!對於高維定義域(多變量)的嚴格凸函數,至今不存在任何通用的、簡化的充要條件刻畫!!!

(跑題一下,對於求解最優化問題來説,在 critical point 処的嚴格正/負定就足以作為局部最優化的充分條件了,而無需在整個定義域都滿足嚴格正/負定,也無需凹凸性。但如果在整個定義域都滿足嚴格正/負定就可以談凹凸性和全局最優化了,儘管在整個定義域都滿足嚴格正/負定只是凹凸性的充分條件,也就意味著,有可能不滿足在整個定義域都嚴格正/負定但卻依然是嚴格凹凸函數,例如 f(x)=−x4f(x)=-x^{4} 和 f(x)=x4f(x)=x^{4} )

弱對偶定理

對於問題

sup⁡x∈Rnf(x)s.t.gj(x)≥0,∀j∈{1,...,J}hl(x)=0,∀i∈{1,...,L}\begin{aligned} \sup_{x\in\mathbb{R}^{n}}f(x)\\ s.t.\\ g_{j}(x)\geq 0,\forall j\in\lbrace 1,...,J\rbrace \\ h_{l}(x)= 0,\forall i\in\lbrace 1,...,L\rbrace \end{aligned}

其中,f(x)f(x)、{gj}j=1J\lbrace g_{j}\rbrace _{j=1}^{J}和{hl}l=1L\lbrace h_{l}\rbrace _{l=1}^{L}的凹凸性、可微性甚至連續性均不做要求。

這一問題可以採用對偶方式來求解,定義前述問題的值函數為p∗p^*,則前述問題的對偶問題為

inf⁡λ∈RJ,μ∈RLq(λ,μ)\inf_{\lambda\in\mathbb{R}^{J},\mu\in\mathbb{R}^{L}}q(\lambda,\mu)

其中

q(λ,μ)=sup⁡x∈Rn(f(x)+λTg(x)+μTh(x))q(\lambda,\mu)=\sup_{x\in\mathbb{R}^{n}}(f(x)+\lambda^{T}g(x)+\mu^{T}h(x))

由於q(λ,μ)q(\lambda,\mu)(註意,qq不是xx的函數)是關於仿射函數λTg(x)+μTh(x)\lambda^{T}g(x)+\mu^{T}h(x)的逐點上確界,因此即使對f(x)f(x)、{gj}j=1J\lbrace g_{j}\rbrace _{j=1}^{J}和{hl}l=1L\lbrace h_{l}\rbrace _{l=1}^{L}的凹凸性不做任何要求,作為上確界函數(當能取到最值時,也就是關於參數λ\lambda和μ\mu的最優值函數)這一點本身,使它成為了凸函數。

定義inf⁡λ∈RJ,μ∈RLq(λ,μ)\inf_{\lambda\in\mathbb{R}^{J},\mu\in\mathbb{R}^{L}}q(\lambda,\mu)問題的值函數為d∗d^*,有如下定理

弱對偶定理

弱對偶定理:d∗≥p∗d^*\geq p^*

證明:由於$g_{j}(x)\geq 0,\forall j\in\lbrace 1,…,J\rbrace 和和h_{l}(x)= 0,\forall i\in\lbrace 1,…,L\rbrace ,所以對於任何,所以對於任何x$,都有

f(x)≤f(x)+∑jλjgj(x)+∑lμlhl(x)f(x)\leq f(x)+\sum_{j}\lambda_{j}g_{j}(x)+\sum_{l}\mu_{l}h_{l}(x)

其中λj≥0,∀j\lambda_{j}\geq 0,\forall j以及μl∈R,∀l\mu_{l}\in\mathbb{R},\forall l,從而

f(x)≤sup⁡x{f(x)+∑jλjgj(x)+∑lμlhl(x)}=q(λ,μ),∀xf(x)\leq \sup_{x}\lbrace f(x)+\sum_{j}\lambda_{j}g_{j}(x)+\sum_{l}\mu_{l}h_{l}(x)\rbrace =q(\lambda,\mu),\forall x

進而

sup⁡f(x)≤g(λ,μ),∀λ≥0,μ≥0\sup f(x)\leq g(\lambda,\mu),\forall \lambda\geq 0,\mu\geq 0

最終

p∗=sup⁡f(x)≤inf⁡λ,μg(λ,μ)=d∗p^*=\sup f(x)\leq\inf_{\lambda,\mu}g(\lambda,\mu)=d^*

超梯度與次梯度

(這個就是前面提到過的兩種幾何刻畫的第二種,即通過在該點処的切線來刻畫。凸函數的切線在函數圖像之上,凹函數的切線在函數圖像之下。)

Thm1 凹函數在切線以下

假設函數ff在xx的一個凸開鄰域C⊂RnC\subset\mathbb{R}^{n}上是凹的,並且在xx點可微,則對於CC中的任一yy,都有

f(x)+f′(x)(y−x)≥f(y)f(x)+f^{\prime}(x)(y-x)\geq f(y)

證明:任取y∈Cy\in C,根據ff在CC上為凹函數,則對於任一λ∈[0,1]\lambda\in\left[0,1\right]有

f(x+λ(y−x))=f((1−λ)x+λy)≥(1−λ)f(x)+λf(y)=f(x)+λ(f(y)−f(x))f(x+\lambda (y-x))=f((1-\lambda)x+\lambda y)\geq (1-\lambda)f(x)+\lambda f(y)=f(x)+\lambda(f(y)-f(x))

特別地,選取λ>0\lambda>0並通除

f(x+λ(y−x))−f(x)λ≥f(y)−f(x)\frac{f(x+\lambda(y-x))-f(x)}{\lambda}\geq f(y)-f(x)

取λ>0\lambda>0趨向於00的單側極限,並根據ff在xx處可微,則有

f′(x)(y−x)≥f(y)−f(x)f^{\prime}(x)(y-x)\geq f(y)-f(x)

即

f(x)+f′(x)(y−x)≥f(y)f(x)+f^{\prime}(x)(y-x)\geq f(y)

意即,在xx處,凹函數f(x)f(x)與仿射函數f(x)+f′(x)(y−x)f(x)+f^{\prime}(x)(y-x)(此時y=xy=x,即f(x)=f(x)+f′(x)(x−x)f(x)=f(x)+f^{\prime}(x)(x-x))相切,並在任何點yy處,凹函數f(x)f(x)都在仿射函數f(x)+f′(x)(y−x)f(x)+f^{\prime}(x)(y-x)的下方。

Thm2

若ff在凸開集U⊂RnU\subset\mathbb{R}^{n}上可微,並假設對於任何xx和yy屬於CC,都有f(x)+f′(x)(y−x)≥f(y)f(x)+f^{\prime}(x)(y-x)\geq f(y),那麼ff是凹函數。

證明:對於任何x∈Cx\in C,定義仿射函數hxh_{x}為hx=f(x)+f′(x)(y−x)≥f(y)h_{x}=f(x)+f^{\prime}(x)(y-x)\geq f(y)。由於仿射函數(即不嚴謹的經濟學語言中的“線性函數”)是凹函數,並且根據假設,對於任何x∈Cx\in C都有f≤hxf\leq h_{x},並且f(x)=hx(x)f(x)=h_{x}(x),所以有

f=inf⁡x∈Chxf=\inf_{x\in C}h_{x}

而一族凹函數的下確界仍然是凹函數,因此ff是凹函數。

解讀:這意味著,我們可以用逐點取值不低於某一凹函數ff的一族仿射函數hxh_{x}來逼近(在下確界意義上)原函數ff。f≤hxf\leq h_{x}並且f(x)=hx(x)f(x)=h_{x}(x)的這種關係,稱之為仿射函數hxh_{x}majorize函數ff。註意,majorization是一個全局的性質,仿射函數hxh_{x}在處處都不低於函數ff,並在xx處相切。

Def3

若一般地,不假設ff的可微性,給定ff是凸集C∈RnC\in\mathbb{R}^{n}上的凹函數,那麼我們稱一個向量p∈Rnp\in\mathbb{R}^{n}是ff在點xx處的超梯度,若向量pp滿足如下超梯度不等式:

f(x)+p(y−x)≥f(y)f(x)+p(y-x)\geq f(y)

對比Th1,可知超梯度pp是f′(x)f^{\prime}(x)的推廣。並且對於給定的凹函數ff和點x∈Cx\in C,有可能存在多個向量pip_{i}都滿足超梯度不等式,即超梯度可以是個多點集∂f(x)={pi}i\partial f(x)=\lbrace p_{i}\rbrace _{i}。函數在某點處超梯度的存在稱為該函數在該點超可微。

將f(x)+p(y−x)f(x)+p(y-x)寫為f(x)+<p,y>−<p,x>f(x)+<p,y>-<p,x>,進而<p,y>−[<p,x>−f(x)]<p,y>-[<p,x>-f(x)]中括號中的部分在給定點xx時為常數,這意味著,當給定xx從而f(x)f(x)時,pp是仿射函數f(x)+p(y−x)f(x)+p(y-x)的斜率,這一斜率使得f(x)+p(y−x)f(x)+p(y-x)是與f(y)f(y)在xx處相切、並且處處不低於ff的那些仿射函數中最低的一個。而截距項−[<p,x>−f(x)]-[<p,x>-f(x)]便是使得f(y)≤<p,y>+αf(y)\leq <p,y>+\alpha對於任何yy都成立的最小的α\alpha。

Lemma4

Thm5 超可微性

凹函數在定義域的內點處都是超可微的。

證明:取定義域凸集CC,並假設函數ff在CC上為凹函數,並且某點xx屬於CC的內點。則ff的嚴格下圖SS為

S={(y,α)∈C×R∣α<f(y)}S=\lbrace (y,\alpha)\in C\times\mathbb{R}|\alpha<f(y)\rbrace

凹函數的下圖(及嚴格下圖)為凸集,即SS為凸集。由於(x,f(x))(x,f(x))不屬於SS(被“嚴格”掉了),則根據分離超平面定理,存在非00的法向量(p,λ)∈Rn×R(p,\lambda)\in\mathbb{R}^{n}\times\mathbb{R}將(x,f(x))(x,f(x))與集合SS分離開:

px+λf(x)≥py+λαpx+\lambda f(x)\geq py+\lambda\alpha

對於任何的(y,α)∈S(y,\alpha)\in S,即y∈Cy\in C且α<f(y)\alpha < f(y)。

我們可以進一步限制法向量元素的符號:既然任何α<f(y)\alpha < f(y)都需要滿足這一不等式,那麼令α\alpha為足夠大的負數,如果λ\lambda也是負數的話,不等式右端將會變得足夠大以至於不等式不能滿足,因此lamda≥0lamda\geq 0。(但無法取α\alpha為足夠大的正數,因為這樣將無法滿足α\alpha的選取條件,即α<f(y)\alpha < f(y));

進一步地lambdalambda也不能取00。如果λ=0\lambda=0的話,那麼不等式變為

px≥pypx\geq py

但由於xx是CC的內點,y=x±ϵzy=x\pm\epsilon z其中ϵ>0\epsilon>0以及任一z∈Rnz\in\mathbb{R}^{n}依然滿足y∈Cy\in C,從而

px≥px±pϵzpx\geq px\pm p\epsilon z

進而pz=0pz=0,但由於zz是任取的,只能p=0p=0。但這意味著“法向量”(p,λ)(p,\lambda)是零向量,矛盾。

因此λ>0\lambda>0。將不等式通除λ\lambda

f(x)+(−pλ)(y−x)≥αf(x)+(-\frac{p}{\lambda})(y-x)\geq\alpha

令α\alpha從下方(左側)趨近於f(x)f(x)

f(x)+(−pλ)(y−x)≥f(y)f(x)+(-\frac{p}{\lambda})(y-x)\geq f(y)

則超梯度不等式由超梯度−pλ-\frac{p}{\lambda}滿足,即凹函數ff在點xx處是超可微的。而點xx是ff的定義域內任一內點,因此凹函數ff在其內點是超可微的。

註釋:在現代的凸分析中,凹/凸函數的定義域一般不是某個任一凸集CC,而是一個特定的凸集Rn\mathbb{R}^{n}。並通過賦予Rn∖C\mathbb{R}^{n}\setminus C中的點∞\infty(凸函數)或−∞-\infty(凹函數)的方式,將定義域拓展到全空間Rn\mathbb{R}^{n}上去(並相應地將值域從實數域變為拓展後的實數域)。因此,若CC的維度(定義為其仿射包aff(C)aff(C)的維度)低於nn,則定理中的“內點”在現代凸分析中,是指“相對內點”,即相對於其仿射包aff(C)aff(C)而言的內點。

Def6 單側方向導數

定義函數ff在點xx處沿方向vv的單側方向導數為

f′(x;v)=lim⁡λ>0,λ→0f(x+λv)−f(x)λf^{\prime}(x;v)=\lim_{\lambda>0,\lambda\rightarrow 0}\frac{f(x+\lambda v)-f(x)}{\lambda}

允許單側方向導數取值±∞\pm\infty

Lemma7

Lemma8 超梯度與單側方向導數

令ff為凸集CC上的凹函數,則

p∈∂f(x)p\in\partial f(x)當且僅當pv≥f′(x;v)pv\geq f^{\prime}(x;v)對於任何使得x+v∈Cx+v\in C的v∈Rv\in\mathbb{R}。

證明:

取x+v∈Cx+v\in C,則對於λ∈[0,1]\lambda\in\left[0,1\right]都有x+λv∈Cx+\lambda v\in C。因此,如果p∈∂f(x)p\in\partial f(x),則根據超梯度不等式

f(x)+p(λv)≥f(x+λv)p(λv)≥f(x+λv)−f(x)pv≥f(x+λv)−f(x)λpv≥f′(x;v)\begin{align} f(x)+p(\lambda v)&\geq f(x+\lambda v)\\ p(\lambda v)&\geq f(x+\lambda v)-f(x)\\ pv&\geq\frac{f(x+\lambda v)-f(x)}{\lambda}\\ pv&\geq f^{\prime}(x;v) \end{align}

反之,如果p∉∂f(x)p\notin\partial f(x),則超梯度不等式對於pp必然在至少一個滿足x+v∈Cx+v\in C的vv處不成立,即

f(x)+pv<f(x+v)f(x)+pv<f(x+v)

但由於ff是凹函數,選定λ∈(0,1]\lambda\in(0,1]有

f(x+λv)=f((1−λ)x+λ(x+v))≥(1−λ)f(x)+λf(x+v)f(x+λv)≥f(x)+λ[f(x+v)−f(x)]f(x+λv)−f(x)≥λ[f(x+v)−f(x)]f(x+λv)−f(x)λ≥f(x+v)−f(x)f(x+λv)−f(x)λ≥f(x+v)−f(x)>pv\begin{align} f(x+\lambda v)&=f((1-\lambda)x+\lambda(x+v))\geq (1-\lambda)f(x)+\lambda f(x+v)\\ f(x+\lambda v)&\geq f(x)+\lambda[f(x+v)-f(x)]\\ f(x+\lambda v)-f(x)&\geq\lambda[f(x+v)-f(x)]\\ \frac{f(x+\lambda v)-f(x)}{\lambda}&\geq f(x+v)-f(x)\\ \frac{f(x+\lambda v)-f(x)}{\lambda}&\geq f(x+v)-f(x)>pv \end{align}

意即f′(x;v)>pvf^{\prime}(x;v)>pv。

Thm9 凹函數在某點處可微當且僅當該函數在該點處的超梯度為單點集。

即

Slater’s Condition

例子:效用最優化與成本最小化

應用:信息設計

一個發送者,一個接收者。有限的世界狀態空間Ω\Omega,發送者和接收者對世界狀態具有共同先驗μ0∈int(ΔΩ)\mu_{0}\in int(\Delta\Omega)。

發送者的vNM效用函數v:A×Ω→Rv:A\times\Omega\rightarrow\mathbb{R},

接收者的vNM效用函數u:A×Ω→Ru:A\times\Omega\rightarrow\mathbb{R}。

發送者承諾(commit)一個信息結構(S,q)(S,q),其中SS為信號實現的可能集,為有限集;q:Ω→Δ(S)q:\Omega\rightarrow\Delta(S)為條件機率。

接收者根據觀察到的信號實現s∈Ss\in S和先驗信念pp進行貝葉斯更新,並採取行動a∈Aa\in A,其中AA為接收者的有限行動空間。

接收者的行動同時影響發送者和接收者的效用。

接收者信念更新的形式為,對於任何ω∈Ω\omega\in\Omega

μs(ω)=q(s∣ω)μ0(ω)∑ω′∈Ωq(s∣ω′)μ0(ω′)\mu_{s}(\omega)=\frac{q(s|\omega)\mu_{0}(\omega)}{\sum_{\omega^{\prime}\in\Omega}q(s|\omega^{\prime})\mu_{0}(\omega^{\prime})}

根據這一後驗信念μs\mu_{s},接收者採取a^(s)∈A\hat{a}(s)\in A來求解如下問題

max⁡a∈A∑s∈Su(a,ω)μs(ω)\max_{a\in A}\sum_{s\in S}u(a,\omega)\mu_{s}(\omega)

預期到接收者的行為,發送者選擇並承諾信息結構(S,q)(S,q)來求解如下問題

max⁡(S,q)∑ω∈Ω∑s∈Sv(a^(s),ω)q(s∣ω)μ0(ω)\max_{(S,q)}\sum_{\omega\in\Omega}\sum_{s\in S}v(\hat{a}(s),\omega)q(s|\omega)\mu_{0}(\omega)

但發送者的問題很不直觀,需要做如下簡化。我們在接收者問題中看到,當信息結構給定時,每個信號實現ss對應於一個後驗信念μs\mu_{s},從而每個信息結構(S,q)(S,q)根據不同的信號實現s∈Ss\in S可以轉化為在一系列後驗信念{μs}s∈S\lbrace \mu_{s}\rbrace _{s\in S}上的分佈τ∈ΔΔ(Ω)\tau\in\Delta\Delta(\Omega),τ(μs)=∑ω∈Ωq(s∣ω)μo(ω)\tau(\mu_{s})=\sum_{\omega\in\Omega}q(s|\omega)\mu_{o}(\omega)。

在後驗信念的這個分佈上,貝葉斯可行總是成立的

∑s∈Sμs(ω)∑ω′∈Ωq(s∣ω′)μ0(ω′)=∑s∈Sq(s∣ω)μ0(ω)∑ω′′∈Ωq(s∣ω′′)μ0(ω′′)∑ω′∈Ωq(s∣ω′)μ0(ω′)=∑s∈Sq(s∣ω)μ0(ω)=1⋅μ0(ω)\begin{aligned} \sum_{s\in S}\mu_{s}(\omega)\sum_{\omega^{\prime}\in\Omega}q(s|\omega^{\prime})\mu_{0}(\omega^{\prime})\\ =\sum_{s\in S}\frac{q(s|\omega)\mu_{0}(\omega)}{\sum_{\omega^{\prime\prime}\in\Omega}q(s|\omega^{\prime\prime})\mu_{0}(\omega^{\prime\prime})}\sum_{\omega^{\prime}\in\Omega}q(s|\omega^{\prime})\mu_{0}(\omega^{\prime})\\ =\sum_{s\in S}q(s|\omega)\mu_{0}(\omega)=1\cdot\mu_{0}(\omega) \end{aligned}

即後驗信念的期望等於先驗信念。

實際上,信號結構(S,q)(S,q)與後驗信念上的分佈τ\tau之間是雙射(bijection),即所有可能的信息結構可以被滿足貝葉斯可行的後驗信念上的分佈來表示

{τ∈ΔΔ(Ω)∣∫Δ(Ω)uτ(dμ)=μ0}\lbrace \tau\in\Delta\Delta(\Omega)|\int_{\Delta(\Omega)}u\tau(d\mu)=\mu_{0}\rbrace

給定任何一個後驗信念μ∈supp(τ)\mu\in supp(\tau),接收者採取行動a^(μ)\hat{a}(\mu),這樣就把接收者的行動規則從信號實現的函數變成了後驗信念的函數。

將a^(μ)\hat{a}(\mu)代入發送者的效用函數,就可以把發送者的效用函數表示為接收者後驗信念的值函數

v^(μ)=∑ω∈Ωv(a^(μ),ω)μ(ω)\hat{v}(\mu)=\sum_{\omega\in\Omega}v(\hat{a}(\mu),\omega)\mu(\omega)

因此發送者的問題可以進一步表示為

sup⁡τ∈ΔΔ(Ω)∫Δ(Ω)v^(μ)τ(dμ)s.t.∫Δ(Ω)μτ(dμ)=μ0\begin{aligned} \sup_{\tau\in\Delta\Delta(\Omega)}\int_{\Delta(\Omega)}\hat{v}(\mu)\tau(d\mu)\\ s.t.\\ \int_{\Delta(\Omega)}\mu\tau(d\mu)=\mu_{0} \end{aligned}

進一步定義函數v^(μ)\hat{v}(\mu)的下圖的凸包

V=co({(v,μ)∈R×Δ(Ω)∣v≤v^(μ)})V=co(\lbrace (v,\mu)\in\mathbb{R}\times\Delta(\Omega)|v\leq\hat{v}(\mu)\rbrace )

對於接收者的任意後驗信念μ∈Δ(Ω)\mu\in\Delta(\Omega),定義發送者效用值函數的凹化函數,

V(μ)=sup⁡{v∈R∣(v,μ)∈V}V(\mu)=\sup\lbrace v\in\mathbb{R}|(v,\mu)\in V\rbrace

命題:發送者的問題可以進一步簡化為

V(μ)=sup⁡τΔΔ(Ω)∫Δ(Ω)v^(μ)τ(dμ)s.t.∫Δ(Ω)μτ(dμ)=μ0\begin{aligned} V(\mu)=\sup_{\tau_{\Delta\Delta(\Omega)}}\int_{\Delta(\Omega)}\hat{v}(\mu)\tau(d\mu)\\ s.t.\\ \int_{\Delta(\Omega)}\mu\tau(d\mu)=\mu_{0} \end{aligned}

證明:我們先將發送者最終問題的值函數表示為W(μ)W(\mu),並表明W(μ)=V(μ)W(\mu)=V(\mu)。

考慮發送者問題的對偶問題

D(λ)=sup⁡τ∈ΔΔ(Ω)∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)D(\lambda)=\sup_{\tau\in\Delta\Delta(\Omega)}\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau(d\mu)

根據弱對偶定理

D∗=inf⁡λ∈R∣Ω∣D(λ)≥W(μ0)D^*=\inf_{\lambda\in\mathbb{R}^{|\Omega|}}D(\lambda)\geq W(\mu_{0})

而v^\hat{v}的下圖的凸包VV根據設定就是個內部非空int(V)≠∅int(V)\neq\emptyset的凸集。

並且

V(μ0)=sup⁡{v∈R∣(v,μ0)∈V}V(\mu_{0})=\sup\lbrace v\in\mathbb{R}|(v,\mu_{0})\in V\rbrace

同時,V(μ0)<v^(μ0)V(\mu_{0})<\hat{v}(\mu_{0})不成立,所以(μ0,V(μ0))∈V∖int(V)(\mu_{0},V(\mu_{0}))\in V\setminus int(V)。

根據支撐超平面定理,存在一個向量(比世界狀態空間的維度高一維)(u,w)∈R×R∣Ω∣(u,w)\in\mathbb{R}\times\mathbb{R}^{|\Omega|}滿足u>0u>0使得

uV(μ0)+wTμ0≥uv^(μ)+wTμuV(\mu_{0})+w^{T}\mu_{0}\geq u\hat{v}(\mu)+w^{T}\mu

其中(v,μ)∈V(v,\mu)\in V。即使用支撐超平面定理,表明(μ0,V(μ0))∈V∖int(V)(\mu_{0},V(\mu_{0}))\in V\setminus int(V)與int(V)int(V)在(μ0,V(μ0))(\mu_{0},V(\mu_{0}))處存在支撐超平面(u,w)(u,w)。

(1) 如果V(μ0)=v^(μ0)V(\mu_{0})=\hat{v}(\mu_{0}),那麼對於任何μ∈Δ(Ω)\mu\in\Delta(\Omega),代入

uv^(μ0)+wTμ0≥uv^(μ)+wTμu\hat{v}(\mu_{0})+w^{T}\mu_{0}\geq u\hat{v}(\mu)+w^{T}\mu

得到

v^(μ0)+1uwTμ0≥v^(μ)+1uwTμ\hat{v}(\mu_{0})+\frac{1}{u}w^{T}\mu_{0}\geq \hat{v}(\mu)+\frac{1}{u}w^{T}\mu

接下來我們表明τ=δ{μ0}\tau=\delta_{\lbrace \mu_{0}\rbrace }(即不揭露任何信息,唯一地使接收者的後驗信念確定為先驗信念μ0\mu_{0})

在這種情況下(V(μ0)=v^(μ0)V(\mu_{0})=\hat{v}(\mu_{0}))

對於發送者為唯一最優的

(即W(μ0)=v^(μ0)=V(μ0)W(\mu_{0})=\hat{v}(\mu_{0})=V(\mu_{0}))。

根據

D(λ)=sup⁡τ∈ΔΔ(Ω)∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)D(\lambda)=\sup_{\tau\in\Delta\Delta(\Omega)}\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau(d\mu)

可知,如果能夠找到某個λ\lambda使得

δ{μ0}∈arg⁡max⁡τ∈ΔΔ(Ω)∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)\delta_{\lbrace \mu_{0}\rbrace }\in\arg\max_{\tau\in\Delta\Delta(\Omega)}\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau(d\mu)

就可以了。但這就意味著找到了某個τ\tau使得原問題的目標函數取得了D(λ)D(\lambda)這個期望效用,那麼原問題目標函數的上確界值函數W(μ0)W(\mu_{0})就至少為D(λ)D(\lambda),即

W(μ0)≥D(λ)W(\mu_{0})\geq D(\lambda)

但根據定義有

D∗=inf⁡λ∈R∣Ω∣D(λ)≥W(μ0)D^*=\inf_{\lambda\in\mathbb{R}^{|\Omega|}}D(\lambda)\geq W(\mu_{0})

因此

W(μ0)≥D(λ)≥D∗≥W(μ0)W(\mu_{0})\geq D(\lambda)\geq D^*\geq W(\mu_{0})

即

W(μ0)=D(λ)W(\mu_{0})=D(\lambda)

因此δ{μ0}\delta_{\lbrace \mu_{0}\rbrace }確實解了原始問題。下面我們考慮如何找到這個λ\lambda

令λ=−1uw\lambda=-\frac{1}{u}w

則

v^(μ0)+1uwTμ0≥v^(μ)+1uwTμ\hat{v}(\mu_{0})+\frac{1}{u}w^{T}\mu_{0}\geq \hat{v}(\mu)+\frac{1}{u}w^{T}\mu

變為

v^(μ0)+λTμ0≥v^(μ)+λTμ\hat{v}(\mu_{0})+\lambda^{T}\mu_{0}\geq \hat{v}(\mu)+\lambda^{T}\mu

兩邊同時積分,並代入τ=δ{μ0}\tau=\delta_{\lbrace \mu_{0}\rbrace },有

∫Δ(Ω)(v^(μ)−λTμ)δ{μ0}(dμ)≥∫Δ(Ω)(v^(μ)−λTμ)τ′(dμ)\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\delta_{\lbrace \mu_{0}\rbrace}(d\mu)\geq\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau^{\prime}(d\mu)

但這就意味著當λ=−1uw\lambda=-\frac{1}{u}w時,τ=δ{μ0}\tau=\delta_{\lbrace \mu_{0}\rbrace }比任何其他的τ′∈Δ(Δ(Ω))\tau^{\prime}\in\Delta(\Delta(\Omega))對於發送者來說都能帶來更高的效用。因此,當V(μ0)=v^(μ0)V(\mu_{0})=\hat{v}(\mu_{0})時,完全不披露任何信息,使得後驗信念與先驗信念完全重合是發送者的最優策略。

(2) 如果V(μ0)>v^(μ0)V(\mu_{0})>\hat{v}(\mu_{0}),那麼根據Caratheodory定理,存在J≤∣Ω∣+1J\leq|\Omega|+1、後驗信念與權重{μj,αj}j=1J\lbrace \mu^{j},\alpha_{j}\rbrace _{j=1}^{J},其中αj>0\alpha_{j}>0且∑j=1Jαj=1\sum_{j=1}^{J}\alpha_{j}=1,使得

∑j=1Jαj(μj,v^(μj))=(μ0,V(μ0)),\sum_{j=1}^{J}\alpha_{j}(\mu^{j},\hat{v}(\mu^{j}))=(\mu_{0},V(\mu_{0})),

並且每個(μj,v^(μj))(\mu^{j},\hat{v}(\mu^{j}))都屬於{(μ,v)∈Δ(Ω)×R∣v≤v^(μ)}\{(\mu,v)\in\Delta(\Omega)\times\mathbb{R}\mid v\leq\hat{v}(\mu)\}。

結合

uV(μ0)+wTμ0≥uv^(μ)+wTμuV(\mu_{0})+w^{T}\mu_{0}\geq u\hat{v}(\mu)+w^{T}\mu

可知這些以正權重進入凸組合的點都位於同一條支撐超平面上。理由是,對上式按αj\alpha_j加權求和會恰好得到左端uV(μ0)+wTμ0uV(\mu_0)+w^T\mu_0;若某個正權重點處為嚴格不等式,則加權和也會嚴格小於左端,矛盾。因此對所有j=1,…,Jj=1,\ldots,J,

uV(μ0)+wTμ0=uv^(μj)+wTμj.uV(\mu_{0})+w^{T}\mu_{0}=u\hat{v}(\mu^{j})+w^{T}\mu^{j}.

從而

uv^(μj)+wTμj≥uv^(μ)+wTμ,∀j,∀μ∈Δ(Ω)u\hat{v}(\mu^{j})+w^{T}\mu^{j}\geq u\hat{v}(\mu)+w^{T}\mu,\forall j,\forall \mu\in\Delta(\Omega)

取λ=−1uw\lambda=-\frac{1}{u}w,得

v^(μj)−λTμj≥v^(μ)−λTμ,∀j,∀μ∈Δ(Ω)\hat{v}(\mu^{j})-\lambda^{T}\mu^{j}\geq \hat{v}(\mu)-\lambda^{T}\mu,\forall j,\forall \mu\in\Delta(\Omega)

由於{αj}j=1J\lbrace \alpha_{j}\rbrace _{j=1}^{J}是凸組合的係數,因此可以作為τ\tau分配給μj\mu^{j}的權重,即

τ(μj)=αj,∀j∈{1,...,J}\tau(\mu^{j})=\alpha_{j},\forall j\in\lbrace 1,...,J\rbrace

因此

∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)=∑j=1Jαj(v^(μj)−λTμj)≥∫Δ(Ω)(v^(μ)−λTμ)τ′(dμ),∀τ′∈Δ(Δ(Ω))\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau(d\mu)=\sum_{j=1}^{J}\alpha_j(\hat{v}(\mu^{j})-\lambda^{T}\mu^{j})\geq\int_{\Delta(\Omega)}(\hat{v}(\mu)-\lambda^{T}\mu)\tau^{\prime}(d\mu),\forall\tau^{\prime}\in\Delta(\Delta(\Omega))

從而{τ(μj)∣τ(μj)=αj,such that∑j=1Jαj(μj,v^(μj))=(μ0,V(μ0))}j=1J\lbrace \tau(\mu^{j})|\tau(\mu^{j})=\alpha_{j},\text{such that}\sum_{j=1}^{J}\alpha_{j}(\mu^{j},\hat{v}(\mu^{j}))=(\mu_{0},V(\mu_{0}))\rbrace _{j=1}^{J}確實解了原問題。因此W(μ0)=V(μ0)W(\mu_{0})=V(\mu_{0})。

凸錐

凸錐是個凸集 SS,需要滿足:其元素的任意縮放(無論是以 λ∈[0,1]\lambda\in[0,1] 還是 λ≥1\lambda\geq 1 的比率)仍然要在這個凸集內

λx∈S,∀λ≥0,∀x∈S\lambda x\in S,\forall \lambda\geq 0,\forall x\in S

正極錐

給定一個錐 C={x}C=\lbrace x\rbrace,把那些對於錐中每個元素(向量) x∈Cx\in C 都滿足 yTx≥0y^{T}x\geq 0 的 yy 們放在一起,就構成了它的正極錐 C+C^{+}

C+={y:yTx≥0,∀x∈C}C^{+}=\lbrace y:y^{T}x\geq 0,\forall x\in C\rbrace

yTx≥0y^{T}x\geq 0 的條件意味著 yy 跟 CC 中每個元素的夾角都要小於或者等於 90 度。

負極錐(對偶錐)

C−={y:yTx≤0,∀x∈C}C^{-}=\lbrace y:y^{T}x\leq 0,\forall x\in C\rbrace

yTx≤0y^{T}x\leq 0 的條件意味著 yy 跟 CC 中每個元素的夾角都要大於或者等於 90 度。

舉例 1

錐 {b}\lbrace b \rbrace 為一條射線,那麼其對偶錐為 {b}⋆={y:yTb≤0}\lbrace b \rbrace^{\star}=\lbrace y:y^{T}b\leq 0 \rbrace 即半空間。

舉例 2

對於任何 y∈Rny\in\mathbb{R}^{n} 來說,y1×nT0n×1≤0y^{T}_{1\times n}0_{n\times 1}\leq 0 恆(以等式)成立,因此退化的錐 {0}\lbrace 0\rbrace 的對偶錐 {0}⋆=Rn\lbrace 0\rbrace^{\star}=\mathbb{R}^{n} 為全空間。

相應地,向量 0n×10_{n\times 1} 是唯一能夠滿足對於任何 x∈Rnx\in\mathbb{R}^{n} 都有 01×nTxn×1≤00^{T}_{1\times n}x_{n\times 1}\leq 0 (以等式成立)的向量,從而 {Rn}⋆={0}\lbrace \mathbb{R}^{n}\rbrace ^{\star}=\lbrace 0\rbrace

函數的凸化與凹化

函數的凸化或凹化即是函數上圖或下圖的凸集化。函數的凸化,是函數上圖的凸集化;函數的凹化,是函數下圖的凸集化。二者都是凸集化,並沒有“凹集”這種東西。

藉助於單位形,Δk\Delta_{k}

Δk:={(α1,...,αk)∈Rk:∑j=1kαj=1,αj≥0,∀j=1,...,k}\Delta_{k}:=\lbrace (\alpha_{1},...,\alpha_{k})\in\mathbb{R}^{k}:\sum_{j=1}^{k}\alpha_{j}=1,\alpha_{j}\geq 0,\forall j=1,...,k \rbrace

Minorize by Affine Function

給定一個函數 g:Rn→R∪{+∞}g:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\lbrace +\infty\rbrace,並且要求其取值不可以恆為 +∞+\infty。如果對於某對 (s,b)∈Rn×R(s,b)\in\mathbb{R}^{n}\times\mathbb{R},有

g(x)≥<s,x>−b,∀x∈Rng(x) \geq <s,x>-b,\forall x\in\mathbb{R}^{n}

則稱仿射函數 <s,x>−b<s,x>-b minorize 了函數 gg。

凸化定理

對於可以被某個 (s,b)(s,b) 所代表的仿射函數所 minorize 的、滿足前述要求的函數 gg 來説,可以定義如下三個函數 f1,f2,f3f_{1},f_{2},f_{3},並且這三個函數在 R\mathbb{R} 上是等價的

  1. f1(x):=inf⁡{r:(x,r)∈co epig}f_{1}(x):=\inf \lbrace r: (x,r)\in \text{co epi} g\rbrace

  2. f2(x):=sup⁡{h(x):h∈Convex functions in Rn,h≤g}f_{2}(x):=\sup\lbrace h(x):h\in\text{Convex functions in }\mathbb{R}^{n},h\leq g \rbrace

  3. f3(x):=inf⁡{∑j=1kαjg(xj):k=1,2,...;xj∈domg,∑j=1kαjxj=x}f_{3}(x):=\inf\lbrace \sum_{j=1}^{k}\alpha_{j}g(x_{j}):k=1,2,...;x_{j}\in\text{dom}g,\sum_{j=1}^{k}\alpha_{j}x_{j}=x \rbrace


這個 ∑j=1kαjxj=x\sum_{j=1}^{k}\alpha_{j}x_{j}=x 條件無論是在 minorization 還是 majorization 裡都是需要滿足的。這個條件在經濟學裡的運用,比如,後驗信念 xjx_{j} 們的期望等於先驗信念 xx。

反過來看,也可以視為將先驗信念 xx 分解為 kk 個後驗信念 xj,j=1,...,kx_{j},j=1,...,k,其係數分別為 αj,j=1,...,k\alpha_{j},j=1,...,k。


證明

將那些 minorize 了 gg 的凸函數們(任何凸函數,不必是仿射函數)組成一個集合,記為 Γ\Gamma。

由於仿射函數本身也是凸函數,所以至少仿射函數可以 minorize 函數 gg,所以 Γ\Gamma 不是空集。

  1. f1(x)f_{1}(x) 是一個凸集 co epig\text{co epi}g 的下確界函數,因此 f1(x)f_{1}(x) 是一個凸函數。

  2. 接下來我們證明 f2≤f1,∀xf_{2}\leq f_{1},\forall x

對於任一 h∈Γh\in\Gamma,考慮它的上圖 epih\text{epi}h。既然 epih\text{epi}h 本身就是 hh 的上圖,那麼由其定義的下確界函數 lepih\mathscr{l}_{\text{epi}h} 就是 hh 本身。既然 h≤gh\leq g,那麼 gg 的上圖 epig\text{epi}g 是包含在 hh 的上圖之內的,並且由於 epih\text{epi}h 是個包含 epig\text{epi}g 在內的凸集,因此 epih\text{epi}h 也包含 co epig\text{co epi}g 在內,所以

h=lepih≤lco epig=f1h=\mathscr{l}_{\text{epi}h}\leq\mathscr{l}_{\text{co epi}g}=f_{1}

由於這個不等式是對任一 h∈ConvRnh\in\text{Conv}\mathbb{R}^{n} 都成立的,那麼必然也對 f2(x):=sup⁡{h(x):h∈Convex functions in Rn,h≤g}f_{2}(x):=\sup\lbrace h(x):h\in\text{Convex functions in }\mathbb{R}^{n},h\leq g \rbrace 成立。

  1. 接下來我們證明 f3≤f2,∀xf_{3}\leq f_{2},\forall x

我們採用的方式是表明 f3∈Γf_{3}\in\Gamma。我們表明 f3≤gf_{3}\leq g:當 k=1k=1 時,inf⁡{∑j=1kαjg(xj):k=1,2,...;xj∈domg,∑j=1kxj=x}≤αα=1g(x)≤g(x)\inf\lbrace \sum_{j=1}^{k}\alpha_{j}g(x_{j}):k=1,2,...;x_{j}\in\text{dom}g,\sum_{j=1}^{k}x_{j}=x \rbrace \leq \alpha_{\alpha=1} g(x) \leq g(x),因此,如果 f3∈ConvRnf_{3}\in\text{Conv}\mathbb{R}^{n},那麼 f3f_{3} 就是一個 minorize 了 gg 的凸函數,所以 f3∈Γf_{3}\in\Gamma,那麼 f3f_{3} 肯定也不會大於 Γ\Gamma 裡面的上確界,即 f2f_{2},則有 f3≤f2f_{3}\leq f_{2}。那麼如何表明 f3f_{3} 是個凸函數呢?

首先,由於存在某個 (s,b)(s,b) 來 minorize gg,這意味著要對於每個 xx 都成立,即對於每個 xx 都有 g(x)≥<s,x>−bg(x)\geq <s,x>-b。那麼既然對於每個 xx 都成立,也就當然有

∑j=1kαjg(xj)≥∑j=1kαj(<s,xj>−b)=<s,x>−b\sum_{j=1}^{k}\alpha_{j}g(x_{j})\geq \sum_{j=1}^{k}\alpha_{j}(<s,x_{j}>-b)=<s,x>-b

即 f3f_{3} 是被仿射函數 <s,⋅>−b<s,\cdot>-b 所 minorize 了的。

現在從 f3f_{3} 的嚴格上圖裡選取兩個點 (x,r)(x,r) 和 (x′,r′)(x^{\prime},r^{\prime}),即使得 f3(x)<rf_{3}(x)<r 和 f3(x′)<r′f_{3}(x^{\prime})<r^{\prime} 的 (x,r)(x,r) 和 $(x^{\prime}。根據 f3f_{3} 的定義,這意味著存在某個 (k,{αj},{xj})(k,\lbrace \alpha_{j}\rbrace,\lbrace x_{j}\rbrace) 和 (k′,{αj′},{xj′})(k^{\prime},\lbrace \alpha_{j}^{\prime}\rbrace,\lbrace x_{j}^{\prime}\rbrace) 使得

∑j=1kαjg(xj)<r\sum_{j=1}^{k}\alpha_{j}g(x_{j})<r

和

∑j=1kαj′g(xj′)<r′\sum_{j=1}^{k}\alpha_{j}^{\prime}g(x_{j}^{\prime})<r^{\prime}

對於任何 t∈(0,1)t\in(0,1) 來説,做二者的嚴格凸組合,有

t∑j=1kαjg(xj)+(1−t)∑j=1kαj′g(xj′)<tr+(1−t)t′t\sum_{j=1}^{k}\alpha_{j}g(x_{j})+(1-t)\sum_{j=1}^{k}\alpha_{j}^{\prime}g(x_{j}^{\prime})<tr+(1-t)t^{\prime}

注意

t∑j=1kαjxj+(1−t)∑j=1kαj′xj′=tx+(1−t)x′t\sum_{j=1}^{k}\alpha_{j}x_{j}+(1-t)\sum_{j=1}^{k}\alpha_{j}^{\prime}x_{j}^{\prime}=tx+(1-t)x^{\prime}

可以把左側視為對 tx+(1−t)x′tx+(1-t)x^{\prime} 凸分解為 k+k′k+k^{\prime} 個元素。根據 f3f_{3} 的定義,有

f3(tx+(1−t)x′)≤t∑j=1kαjxj+(1−t)∑j=1kαj′xj′=tx+(1−t)x′f_{3}(tx+(1-t)x^{\prime})\leq t\sum_{j=1}^{k}\alpha_{j}x_{j}+(1-t)\sum_{j=1}^{k}\alpha_{j}^{\prime}x_{j}^{\prime}=tx+(1-t)x^{\prime}

這就意味著 f3f_{3} 的上圖是凸集,從而 f3f_{3} 是個凸函數。

  1. 接下來我們證明 f1≤f3f_{1}\leq f_{3}。任選定義域內的一個點 x∈Rnx\in\mathbb{R}^{n},以及 xx 的一個凸分解 x=∑j=1kαjxjx=\sum_{j=1}^{k}\alpha_{j}x_{j}。

根據定義,(xj,g(xj))∈epig,∀j=1,...,k(x_{j},g(x_{j}))\in\text{epi}g,\forall j=1,...,k,那麼根據構造凸包的方法

(x,∑j=1kαjg(xj))∈co epig(x,\sum_{j=1}^{k}\alpha_{j}g(x_{j}))\in\text{co epi}g

即

f1(x):=inf⁡{r:(x,r)∈co epig}≤∑j=1kαjg(xj)f_{1}(x):=\inf \lbrace r: (x,r)\in \text{co epi} g\rbrace\leq \sum_{j=1}^{k}\alpha_{j}g(x_{j})

由於這個凸分解是任意的,那麼對於凸分解中的下碻界 f3f_{3} 也應該是成立的。□\square


epi(cog)≠co(epig)\text{epi}(\text{co}g)\neq\text{co}(\text{epi}g)

需要截斷下部分。

∑j=1kαjxj=x\sum_{j=1}^{k}\alpha_{j}x_{j}=x 使得 xx 為邊界點,根據 Caratheodory 定理在邊界點的特殊情況,k≤n+1k\leq n+1。


參考文獻

[1] Vohra, R. V. (2004). Advanced mathematical economics. Routledge.
[2] Kamenica, E., & Gentzkow, M. (2011). Bayesian persuasion. American Economic Review, 101(6), 2590-2615.
[3] Kai Hao Yang’s Lecture Notes