最小最大值定理

hbghlyj

Wikipedia – Minmax theorem
Du, Ding-Zhu; Pardalos, Panos M., eds. (1995). Minimax and Applications.
最小最大值定理也称博弈论基本定理，是一个关于最大最小不等式等号成立的条件的定理。1928年由冯·诺伊曼证明。
若 $X ⊆\Bbb R^n$，$Y ⊆\Bbb R^m$ 为紧致凸集。$f:X\times Y\rightarrow \mathbb {R}$ 为连续的凸-凹函数（即 $f(x,y)$关于 $x$ 是凸函数，关于 $y$ 是凹函数）。则：
\[\max _{y\in Y}\min _{x\in X}f(x,y)=\min _{x\in X}\max _{y\in Y}f(x,y)\]
例子:

The function $f(x, y) = y^2-x^2$ is concave-convex.

例子:
If $f(x,y)=x^{\mathsf {T}}Ay$ for a finite matrix $A\in \mathbb {R} ^{n\times m}$, we have:
$$\max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.$$
相关帖子:矩阵按行、列排序

hbghlyj

For any function $f:Z\times W\to \mathbb {R}$,\[\sup _{z\in Z}\inf _{w\in W}f(z,w)\leq \inf _{w\in W}\sup _{z\in Z}f(z,w)\]

Define $g(z)\triangleq \inf _{w\in W}f(z,w)$.
$∀ w ∈ W , ∀ z ∈ Z , g ( z ) ≤ f ( z , w )$.
$⟹ ∀ w ∈ W , \sup_{z ∈ Z} g ( z ) ≤ \sup_{z ∈ Z} f ( z , w )$.
$⟹ \sup_{z ∈ Z} g ( z ) ≤ \inf_{w ∈ W}\sup_{z ∈ Z} f ( z , w )$.
$⟹ \sup_{z ∈ Z}\inf_{w ∈ W}f ( z , w ) ≤ \inf_{w ∈ W}\sup_{z ∈ Z} f ( z , w ) \ _◻$

hbghlyj

如果改为\[\sup _{z\in Z}\inf _{w\in W}f(z,w)\leq \inf _{z\in Z}\sup _{w\in W}f(z,w)\]则不一定成立. 考虑 2-dimensional array $\left(x_{m, n}\right)$,$x_{11}=2$; $x_{1n}=1$ for $n>1$; $x_{mn}=0$ for $m>1$ \begin{align*}&\sup_{n⩾1}x_{1,n}=2\quad\inf_{n⩾1} x_{1,n}=1\\ \forall m>1:\quad&\sup_{n⩾1} x_{m,n}=\inf_{n⩾1} x_{m,n}=0\end{align*} 故$$\inf_{m⩾1}\sup_{n⩾1}x_{m,n}=0<1=\sup_{m⩾1}\inf_{n⩾1}x_{m,n}$$\begin{array}{c|cc}x_{1,n}&2&1&1&⋯\\x_{2,n}&0&0&0&⋯\\x_{3,n}&0&0&0&⋯\\⋮&⋮&⋮&⋮&\ddots\end{array}

hbghlyj

数列$(x_n)$的上极限定义是
\[\limsup_{n\rightarrow\infty}x_n=\inf_{n\geq 0}\,\sup_{k\geq n}x_k=\inf\{\,\sup\{\,x_k:k\geq n\,\}:n\geq 0\,\}\]
或者
\[\limsup_{n\rightarrow\infty}x_n=\lim_{n\rightarrow\infty}\left(\sup_{m\geq n}x_m\right)\]
同样的，序列$x_n$的下极限定义是
\[\liminf_{n\rightarrow\infty}x_n=\sup_{n\geq 0}\,\inf_{k\geq n}x_k=\sup\{\,\inf\{\,x_k:k\geq n\,\}:n\geq 0\,\}\]
或者
\[\liminf_{n\rightarrow\infty}x_n=\lim_{n\rightarrow\infty}\left(\inf_{m\geq n}x_m\right)\]
这些定义在任意的 偏序集 都适用，只需要 上确界 和 下确界 存在。
在 完全格 裡，上确界和下确界总是存在，所以其中的序列一定有上极限和下极限。
每当$\liminf x_n$和$\limsup x_n$都存在，那么
\[\liminf_{n\rightarrow\infty}x_n\leq\limsup_{n\rightarrow\infty}x_n\]