一些簡單的凸分析

基本概念與基本性質

組合 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從而上述命題凸函數內點的右極限總是不小於左極限，當屬於間斷點時右極限嚴格高於左極限中的“間斷點”可以進一步限製為跳躍間斷點（即凸函數的內點不會是無窮間斷點）。

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

令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\lbrace \mu_{i}\rbrace _{i\neq k}，滿足μi∈[0,1]\mu_{i}\in [0,1]及∑i≠kμi=1\sum_{i\neq k}\mu_{i}=1，並且μ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(x)=∫Xfdμf(x)=\int_{X}fd\mu對於任何連續線性泛函ff都成立)並且機率測度μ\mu的支撐為XX的極點(即{x∈X:μ(x)>0}=extX\lbrace x\in X:\mu(x)>0\rbrace =\text{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]inR: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≥0,∀l\mu_{l}\geq 0,\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^(μ0)−λTμ0)dμ0≥∫Δ(Ω)(v^(μ)−λTμ)τ′(dμ)\int_{\Delta(\Omega)}(\hat{v}(\mu_{0})-\lambda^{T}\mu_{0})d\mu_{0}\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定理，存在$\lbrace \hat{v}(\mu^{j}),\mu^{j}\rbrace _{j=1}^{|\Omega|+2}\subset\lbrace (v,\mu)\in\mathbb{R}\times\Delta(\Omega)|v\leq\hat{v}(\mu)\rbrace 和和\alpha\in\Delta(\lbrace 1,…,|\Omega|+2\rbrace )$使得

∑j=1∣Ω∣+2αj(μj,v^(μj))=(μ0,V(μ0))\sum_{j=1}^{|\Omega|+2}\alpha_{j}(\mu^{j},\hat{v}(\mu^{j}))=(\mu_{0},V(\mu_{0}))

結合

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

可知

V(μ0)=v^(μj),∀jV(\mu_{0})=\hat{v}(\mu^{j}),\forall j

以及

uV(μ0)+wTμ0=uv^(μj)+wTμj,∀juV(\mu_{0})+w^{T}\mu_{0}=u\hat{v}(\mu^{j})+w^{T}\mu^{j},\forall 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\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\Delta(\Omega)

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

τ(μj)=αj,∀j∈{1,...,∣Ω∣+2}\tau(\mu^{j})=\alpha_{j},\forall j\in\lbrace 1,...,|\Omega|+2\rbrace

因此

∫Δ(Ω)(v^(μj)−λTμj)τ(dμj)≥∫Δ(Ω)(v^(μ)−λTμ)τ′(dμ),∀τ′∈ΔΔ(Ω)\int_{\Delta(\Omega)}(\hat{v}(\mu^{j})-\lambda^{T}\mu^{j})\tau(d\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=1∣Ω∣+2αj(μj,v^(μj))=(μ0,V(μ0))}j=1∣Ω∣+2\lbrace \tau(\mu^{j})|\tau(\mu^{j})=\alpha_{j},\text{such that}\sum_{j=1}^{|\Omega|+2}\alpha_{j}(\mu^{j},\hat{v}(\mu^{j}))=(\mu_{0},V(\mu_{0}))\rbrace _{j=1}^{|\Omega|+2}確實解了原問題。因此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