【筆記】不動點定理（五）樊畿不等式 Ky Fans Minmax Inequality

05-02

這一部分是樊畿不等式。

預備（一）

之前我們已經使用Sperner引理表述過了KKM引理，現在為了得到樊畿不等式，需要先引入KKMF引理。

首先回顧一下KKM引理

令 $Delta = coleft {v_{0},..,v_{m} ight }subsetmathbb {R}^{m+1}$ ，其中 $left {v_{0},…,v_{m} ight}$ 仿射無關，令 $left {F_{0},…, F_{m} ight }$ 為 $Delta$ 中的一族閉集，使得任給以 $Asubsetleft {0,…,m ight }$ 為標號的子集有 $coleft {v_{i}:iin A ight}subsetigcup_{iin A}F_{i}$ ，則 $igcap_{i=0}^{m}F_{i} eq varnothing$ 。

意即， $Delta$ 為 $m+1$ 個仿射無關向量的凸包，每個 $Fi$ 均為 $Delta$ 內的閉集。如果從指標集 $left {0,…,m ight}$ 里任選一組子集A(比如 $A=left{0,2,6 ight}$ )，對相應的向量們(比如 $left{v_{0}, v_{2}, v_{6} ight}$ )做凸包，所形成的低維單純形(比如 $coleft{v_{0}, v_{2}, v_{6} ight}$ )都被包含在相應的閉集之並里(比如 $F_{0}∪F_{2}∪F_{6}$ )，那麼把全部指標都用上，把從 $i=1$ 到 $i=m$ 的所有 $Fi$ 們取交，會是非空的。

最先幾次的筆記內容所使用的語言實在是含混不清，又為了「砸掛」而使用詭異的記法，應該以後會重新寫一下。

KKM引理的一般形式

令 $K=coleft{a_{0},…,a_{m} ight}subsetmathbb R^{k}$ ，令 $left{F_{0},…,F_{m} ight}$ 為一族閉集使得任給 $Asubsetleft{0,…,m ight}$ ，有 $coleft{a_{i}:isubset A ight}subsetigcup_{iin A}F_{i}$ ，則 $igcap_{i=0}^{m}F_{i} eqvarnothing$ 。

把仿射無關向量組換成了任意一組 $a_{0},…,a_{m}$ 會帶來一些影響，例如如果 $a_{i}$ 們不是仿射無關的話 $K$ 會是低於 $m+1$ 維的單純形。不過後面會看到這並不會改變結果。

證明：

定義 $sigma:Delta ightarrow K$ 為 $sigma(z)=Sigma_{i=0}^{m}z_{i}a_{i}$ ，其中 $z_{i}$ 為使得 $z=Sigma_{i=0}^{m}z_{i}v_{i}$ 而 $forall zin Delta$ 的那些 $z_{i}$ 們，這就將單純形 $Delta$ 與 $K$ 聯繫了起來。

如果 $a_{i}$ 們不是仿射無關的，表示codomin維數低於domin維數，則 $sigma$ 不是單射。不過不是單射也無所謂，不影響其連續性。

連續函數值域中的閉集，其原像(射回去)仍是閉集，因此對於像集 $F(x_{i})$ ，則原像集 $S_{i}=σ^{-1}(F_{i})$ 也是閉的。

Claim

任給 $Asubsetleft{0,...,m ight}$ ，有 $coleft{v_{i}:iin A ight}subsetigcup_{iin A}S_{i}$ 。

if not，則有 $exists zin coleft{v_{i}:iin A ight},s.th.z otinigcup_{iin A}S_{i},i.e.z otin S_{i},forall iin A$ 。但這就意味著 $z otinsigma^{-1}(F_{i}),forall iin A,i.e.sigma(z) otinigcup_{iin A}F_{i}$ 則 $sigma(z)in coleft{a_{i}:iin A ight} subseteqigcup_{iin A}F_{i}$ ，矛盾。

至此，我們已經有了任給 $Asubsetleft{0,...,m ight}$ ，有 $coleft{v_{i}:iin A ight}subsetigcup_{iin A}S_{i}$ ，因此根據單純形上的KKM引理，有 $igcap_{i=0}^{m}S_{i} eqvarnothing$ 。

從其中任選一點 $zinigcap_{i=0}^{m}S_{i}=igcap_{i=0}^{m}sigma^{-1}(F_{i})$ ,即有 $sigma(z)inigcap_{i=0}^{m}F_{i}$ ，從而 $igcap_{i=0}^{m}F_{i} eqvarnothing$ 。 $square$

KKMF引理

令 $Xsubsetmathbb R^{k}$ ， $forall xin X$ ，令 $F(x)subsetmathbb R^{k}$ 為閉集，如果有

（1）任給有限個點構成的集合 $left{x_{1},...,x_{n} ight}subset X$ ，有 $coleft{x_{1},...,x_{n} ight}subsetigcup_{i=1}^{n}F(x_{i})$ ；

（2）至少有某個 $xin X$ 使得 $F(x)$ 為緊集。

則 $igcap_{xin X}F(x) eqvarnothing$ 。

證明：

從上述KKM引理的一般形式可知，有 $igcap_{i=1}^{m}F(x_{i}) eqvarnothing$ ，而由此處題設（1）可知，對於每一組 $left{1,...,m ight}$ 都可以應用上節結果。即對於任意有限個 $F(x_{i})$ 其交集非空。

記滿足題設（2）的那個 $x$ 為 $x_{0}$ ，相應地那個緊集為 $F(x_{0})$ ，而既然任意有限個 $F(x_{i})$ 交集非空，再交上 $F(x_{0})$ 依然非空，即 $F(x_{0})igcap(igcap_{i=1}^{n}F(x_{i}))=igcap_{i=0}^{n}F(x_{i}) eqvarnothing$ ，因為在 $n$ 為有限時， $n+1$ 依然為有限。

並且 $igcap_{i=0}^{n}F(x_{i})$ 是閉集們的交集，依然為閉集，而 $igcap_{i=0}^{n}F(x_{i})subset F(x_{0})$ 表明 $igcap_{i=0}^{n}F(x_{i})$ 是緊集的閉子集，因此它本身也是緊集。一集合 $C$ 為緊集當且僅當任意具有有限交性質（F.I.P.）的非空閉子集族 $mathscr{C}$ 之交集非空。（註： $mathscr{C}=left{Binmathscr{P}(C):Bspace is space closedspace andspace nonempty ight}$ ， $mathscr{P}(C)$ 為 $C$ 的冪集。此處只要求閉子集族具有有限交性質，而閉子集族本身可以含有無限多個元素，其每個元素是閉集）。

而我們已經知道了任意有限個閉集 $F(x_{i})$ 們具有非空交集，且 $igcap_{i=0}^{m}F_{i}$ 為緊集，因此 $igcap_{xin X}F(x) eqvarnothing$ 。 $square$

預備（二）

一些概念

[Partial Order]

非空集合 $D$ ，二元關係 $Rsubset D imes D$ 。如果 $R$ 滿足反身性、傳遞性，則稱 $R$ 為 preorder(常見譯名為前序、預序)。如果除了反身性、傳遞性以外還滿足反對稱性（antisymmetry，即if $aRb$ and $bRa$ then $a=b$ ），則稱為 partial order （常見譯名為偏序、半序）。此時用來定義偏序 $R$ 的集合 $D$ 稱為partially ordered set，簡記為poset（常見譯名為偏序集）。

[有向集]

偏序集 $D$ ，偏序 $R$ 。如果滿足 $forall a,bin D$ ， $exists csubset D$ ， s.th. $cRa$ 且 $cRb$ ，即總能找到一個比 $D$ 中任意兩個元素同時都「更 $R$ 」的元素，則稱此偏序集 $D$ 為有向集。常見的有向集是在 $geq$ 關係下的自然數集 $mathbb N$ 。

[網]

$X$ 為一拓撲空間， $D$ 為一有向集。 $left{x_{α}:αin D ight}$ 稱為 $X$ 中的網。其實就是序列概念的拓展，當 $D$ 是特別的有向集，即（在 $geq$ 關係下的）自然數集 $mathbb N$ 時，網就是序列。這裡不限於自然數集，而是拓展到了一般的有向集中。

[Hausdorff 空間]

若對於一個空間中任意相異的兩點，都可以分別各用一個開集將其包住，且這兩個開集不相交，則稱此空間為 Hausdorff 空間。

[Hausdorff 拓撲線性空間]

若在Hausdorff 空間上定義拓撲，使得在此空間上的向量加法和標量乘法為連續函數，則稱此Hausdorff 空間為Hausdorff 拓撲線性空間。

[泛函]

$f:X ightarrow mathbb R$ 。定義域來自一般性的抽象空間（而函數的定義域來自於歐氏空間，取值依然為實值。在這一節里， $X$ 為 Hausdorff 拓撲空間。

[半連續]

為有所區別，遵照Afa.Ok的做法，將函數/泛函的半連續稱為 semi-continuous，將對應的半連續稱為 hemi-continuous。此處為泛函的半連續。

半連續定義·版本一[Def Vr.1]

$X$ 為Hausdorff 拓撲空間（此後記為HTS），泛函 $f:X ightarrow mathbb R$ (此後簡記為 fl )。給定點 $xin X$ 。

如果 $forall epsilon>0$ ，總能找到開鄰域 $U(x)$ ，使得 $forall xin U(x)$ ，有 $f(x)<f(x)+epsilon$ ，則稱 fl $f$ 在 $x$ 處上半連續，即 u.s.c. at $x$ ；

如果 $forall epsilon>0$ ，總能找到開鄰域 $U(x)$ ，使得 $forall xin U(x)$ ，有 $f(x)>f(x)-epsilon$ ，則稱 fl $f$ 在 $x$ 處下半連續，即 l.s.c. at $x$ .

半連續定義·版本二[Def Vr.2]

HTS $X$ , fl $f:X ightarrow mathbb R$ ，

$f$ is upper semi-continuous on $X$ iff $forall cin mathbb R$ ， $left{xin X:f(x)geq c ight}$ is closed；

$f$ is lower semi-continuous on $X$ iff $forall cin mathbb R$ ， $left{xin X:f(x)leq c ight}$ is closed；

$f$ is continuous on $X$ iff it both u.s.c. and l.s.c.

Claim. 上述兩種定義方式是等價的。

Proof.

此處只對上半連續情況作出證明。

Part I Def Vr.1 $Rightarrow$ Def Vr.2

從 Vr.1 我們知道 $f(x)$ 在X上是上半連續的，即 $forall xin X,forall epsilon>0,exists U(x)為x的開鄰域.s.th.forall xin U(x),有f(x)<f(x)+epsilon$ ，而我們需要證明 $forall cin mathbb R$ ， $left{xin X:f(x)geq c ight}$ 是閉集，意即，我們需要證明，任給來自 $left{xin X:f(x)geq c ight}$ 的網 $left{x_{alpha} ight}$ 如果 $x_{alpha} ightarrow x^{ast}$ ，則有 $f(x^{ast})geq c$ 。（ $x_{alpha} ightarrow x^{ast}$ 即是說 $forall U(x^{ast})為$ $x^{ast}$ 的鄰域， $exists alpha_{0},s.th.forall alpha>alpha_{0}$ ，都有 $x_{alpha}in U(x^{ast})$ ）

既然網 $left{x_{alpha} ight}$ 是從 $left{xin X:f(x)geq c ight}$ 里選擇的，那麼就有 $f(x_{alpha})geq c$ ；

從Vr.1知 $forall xin U(x)$ 我們有 $f(x)<f(x^{ast})+epsilon$ 因此 $f(x_{alpha})<f(x^{ast})+epsilon$ ；

將兩者結合，有 $cleq f(x_{alpha})<f(x^{ast})+epsilon$ ，由於 $epsilon$ 是任選的，因此有 $cleq f(x^{ast})$ 。

Part II Def Vr.2 $Rightarrow$ Def Vr.1

從Vr.2我們得知 $forall cin mathbb R$ ， $left{xin X:f(x)geq c ight}$ 為閉集，則 $forall cin mathbb R$ ， $left{xin X:f(x)< c ight}$ 為開集，因為 $c$ 是任選的，不妨令 $c=f(x^{ast})+epsilon$ ，因此 $left{xin X:f(x)<f(x^{ast})+epsilon ight}$ 為開集，特別地， $x^{ast}inleft{xin X:f(x)<f(x^{ast})+epsilon ight}$ 。而既然 $x^{ast}$ 屬於一個開集，那麼必存在開鄰域 $U(x^{ast})$ 使得 $x^{ast}in U(x^{ast})subset left{xin X:f(x)<f(x^{ast})+epsilon ight}$ ，而這就是說 $forall xin U(x^{ast})$ ，都有 $f(x)<f(x^{ast})+epsilon$ ，而這正是 $f$ 在 $x^{ast}$ 上半連續的Def Vr.1。 $square$

半連續定義·版本三[Def Vr.3]

$f$ u.s.c. at $x^{ast}$ iff $forall x_{alpha} ightarrow x^{ast},limspace supspace f(x_{alpha})leq f(x^{ast})$ ;

$f$ l.s.c. at $x^{ast}$ iff $forall x_{alpha} ightarrow x^{ast},limspace infspace f(x_{alpha})geq f(x^{ast})$ .

Theorem 0.

HTS $X$ ， $forall lambda inLambda$ ，fl $f_{lambda}:X ightarrow mathbb R$ .

（1）if $f_{lambda}$ u.s.c. on $X$ , $forall lambdainLambda$ , then $inf_{lambdainLambda}f_{lambda}(x)$ u.s.c on $X$ ;

（2）if $f_{lambda}$ l.s.c. on $X$ , $forall lambdainLambda$ , then $sup_{lambdainLambda}f_{lambda}(x)$ l.s.c on $X$ .

Proof. (for case（1）only)

$forall cin mathbb R$ , $left{xin X:inf_{lambdainLambda}f_{lambda}(x)geq c ight}$ = $left{xin X:inff_{lambda}(x)geq c,foralllambdainLambda ight}$ = $igcap_{lambdainLambda}left{xin X:f_{lambda}geq c ight}$ ，而既然 $f_{lambda}$ 在 $X$ 上半連續，則 $left{xin X:f_{lambda}geq c ight}$ 為閉集，因此 $igcap_{lambdainLambda}left{xin X:f_{lambda}geq c ight}$ 為閉集，即 $left{xin X:inf_{lambdainLambda}f_{lambda}(x)geq c ight}$ 是閉集，因此 $inf_{lambdainLambda}f_{lambda}(x)$ 在 $X$ 為上半連續。

接下來可以進入主題了。

樊畿不等式

Theorem 1.

Hausdorff 拓撲線性空間 $X$ ， $E$ 為 $X$ 中的非空緊凸子集，泛函 $f:X ightarrow mathbb R$ 。如果滿足

（1） $forall xin X,y ightarrow f(x,y)$ 在 $X$ 為下半連續，且

（2） $forall yin X,x ightarrow f(x,y)$ 在 $X$ 為擬凹的。

則 $min_{yin X}sup_{xin X}f(x,y)leq sup_{xin X}f(x,x)$ 。

Proof.

由題設（1）有 $forall xin X,y ightarrow f(x,y)$ 在 $X$ 為下半連續，根據前述Theorem 0，可知 $forall xin X,y ightarrow supf(x,y)$ 在 $X$ 為下半連續。而 $X$ 為緊集，可知最小值 $min_{yin X}sup_{xin X}f(x,y)$ 存在。

令 $b=sup_{xin X}f(x,x)$ ， $F(x):=left{yin X:f(x,y)leq b ight}$ 。

而 $y ightarrow f(x,y)$ 在 $X$ 為下半連續，根據半連續定義·版本二[Def Vr.2]，可知 $F(x)$ 為閉集。此外，根據 $F(x)$ 的定義方式，有 $F(x)subset X$ ，作為緊集的閉子集，因此 $F(x)$ 也為緊集。

Claim.

$forallleft{x_{1},...,x_{n} ight}subset X,coleft{x_{1},...,x_{n} ight}subsetigcup_{i=1}^{n}F(x_{i}).$

if not, 則 $exists lambda_{i}geq 0 (i=1,...,n)$ with $sum_{i=1}^{n}lambda_{i}=1$ 使得 $sum_{i=1}^{n}lambda_{i}x_{i} otin igcup_{i=1}^{n}F(x_{i})$ ，而既然它不屬於並集，那麼它必然也不屬於其中任何一個集合，有 $sum_{i=1}^{n}lambda_{i}x_{i} otin F(x_{j})，forall j=1,...,n$ ，

根據 $F(x_{j})$ 的定義，這等於說 $f(x_{j},sum_{i=1}^{n}lambda_{i}x{i})>b, forall j=1,...,n.$ ，而既然每一個 $f( x_{j},sum_{i=1}^{n}lambda_{i}x{i} )>b$ ，那麼它們的最小值 $min_{j}f(x_{j},sum_{i=1}^{n}lambda_{i}x{i}>b$ 。此外，根據題設（2） $forall yin X,x ightarrow f(x,y)$ 在 $X$ 為擬凹的，因此 $f(sum_{i=1}^{n}lambda_{i}x{i},sum_{i=1}^{n}lambda_{i}x{i})geq min_{j}f(x_{j},sum_{i=1}^{n}lambda_{i}x{i})>b$ ，意即 $f(sum_{i=1}^{n}lambda_{i}x{i},sum_{i=1}^{n}lambda_{i}x{i})>b$ ，但根據 $b$ 的定義， $b=sup_{xin X}f(x,x)$ ，矛盾。因此，必有 $forallleft{x_{1},...,x_{n} ight}subset X,coleft{x_{1},...,x_{n} ight}subsetigcup_{i=1}^{n}F(x_{i}).$

根據KKMF引理， $igcap_{xin X}F(x) eqvarnothing$ ，既然非空，可以任選一點 $y^{ast}inigcap_{xin X}F(x)=igcap_{xin X}left{yin X:f(x,y)leq b ight}=left{yin X:f(x,y)leq b,forall xin b ight}$ ，意即 $forall xin X$ ， $f(x,y^{ast})leq b$ ，既然任給 $xin X$ 都有 $f(x,y^{ast})leq b$ ，那麼 $sup_{xin X}f(x,y^{ast})leq b$ .