二元实函数关于x的最小值关于y的最大值

hbghlyj

在math.stackexchange.com/questions/483735证明了\[\sup_{y\in Y}\left(\inf_{x\in X}f(x,y)\right)\leq \inf_{x\in X}\left(\sup_{y\in Y}f(x,y)\right)\]一般不能取等。

但是如果 $X=[0,1],Y=[0,1]$ 且 $f(x,y)=axy+bx+cy+d$，那么等式成立，为什么？

hbghlyj

当然可以忽略常数$d$.
$f(x,y)=axy+bx+cy$关于$x,y$都是一次的，在边界$\partial[0,1]=\{0,1\}$处取最值，所以
\begin{align*}
\inf_{x\in X}f(x,y)&=\min\{f(0,y),f(1,y)\}
\\\sup_{y\in Y}f(x,y)&=\max\{f(x,0),f(x,1)\}
\end{align*}
将这些代入：
\begin{align*}\LHS&=\sup_{y\in Y}\biggl(\inf_{x\in X}f(x,y)\biggr)\\&=\sup_{y\in Y}\biggl(\min\{f(0,y),f(1,y)\}\biggr)
\\&🟰\inf_{x\in X}\biggl(\max\{f(x,0),f(x,1)\}\biggr)\\&=\inf_{x\in X}\biggl(\sup_{y\in Y}f(x,y)\biggr)=\RHS
\end{align*}
疑问：等式🟰怎么看出？

hbghlyj

对此的@Czhang271828式的范畴论证明可以在《语境中的范畴论》第 113 页的推论 3.8.4 中找到。

Czhang271828

一楼的问题: 函数形如 $(x+p)(y+q)+r$, 从而等号显然.

一般的证明: 将一个偏序集 $(X,\leq)$ 视同通常意义下的小范畴 $\mathcal X$. 定义对象集 $\mathsf{Ob}(\mathcal X)=X$, 态射集 $\bigcup_{x\leq y}\{x\to y\}$. 很明显 $|\mathrm{Hom}_{\mathcal X}(x,y)|=1$ 或 $0$ (依照 $x\leq y$ 与否).

此时对子图 $i:\mathcal X_0\hookrightarrow \mathcal X$, 余极限 $\varinjlim i$ 若存在, 则等于 $\sup \mathcal X_0$; 极限 $\varprojlim i$ 若存在, 则等于 $\inf \mathcal X_0$. 以上的子图 $i$ 可以替换做一般意义下的集合间映射 $G:S\to \mathcal X$. 如果将全体偏序集视同 $2$-范畴, 则 $G$ 等同离散偏序集 $S$ 至 $\mathcal X$ 的函子.

实分析常用的 $\mathcal X=(\mathbb R\cup\{\pm \infty\},\leq)$ 对极限与余极限封闭. 以下只需证明对任意双函子 $F:X\times Y\to (\mathbb R,\leq)$, 总存在态射 $$ \varinjlim_{y\in Y}\,\, \varprojlim_{x\in X} F(x,y)\to \varprojlim_{x\in X} \,\,\varinjlim_{y\in Y} F(x,y)\quad \Leftrightarrow \quad \sup_{y\in Y}\inf_{x\in X}F(x,y)\leq \inf_{x\in X}\sup _{y\in Y} F(x,y). $$ 这是因为平凡态射 $\{\varphi_{x,y}:F(x,y)\to F(x,y)\}_{x\in X, y\in Y}$ 给出一族态射 (图中 $1$). 泛性质表明 $(1)$ 通过余极限分解得 $(2)$, $(2)$ 又通过极限分解得 $(3)$. 态射 $(3)$ 的存在性即原式中不等号成立. 特别地, 置 $X=Y=(\mathbb N,\leq)$, $F:(m,n)\mapsto m+n$, 以及数列 $a:\mathbb N\to \mathbb R$. 此时 $$ \varprojlim_{n\in \mathbb N}\,\, \varinjlim_{m\in \mathbb N} a_{F(m,n)}\to \varinjlim_{m\in \mathbb N} \,\,\varprojlim_{n\in \mathbb N} a_{F(m,n)}, $$ 这也就是 $\liminf a\leq \limsup a$.

将偏序语言翻译成自然语言, 结果如下:

• 存在一族不等式 $\{\inf_x f(x,y_0)\leq f(x_0,y_0)\leq \sup_y f(x_0,y)\}_{x_0\in X,y_0\in Y}$;
• 对固定的 $x_0$, 不等式族 $\{\inf_x f(x,y_0)\leq \sup_{y}f(x_0,y)\}_{y_0\in Y}$ 等价于一个不等式 $\sup_{y}\inf_{x} f(x,y)\leq \sup_y f(x_0,y)$;
• 不等式族 $\{\sup_{y}\inf_{x} f(x,y)\leq \sup_y f(x_0,y)\}_{x_0\in X}$ 等价于一个不等式 $\sup_{y}\inf_{x} f(x,y)\leq \inf_x\sup_y f(x,y)$.

证明全过程只有逻辑等价, 没有出现什么 $\varepsilon$.

hbghlyj

von Neumann's minimax theorem states:

Let $ X\subset \mathbb {R} ^{n} $ and $ Y\subset \mathbb {R} ^{m} $ be compact convex sets. If $ f:X\times Y\rightarrow \mathbb {R} $ is a continuous function that is concave-convex, i.e.
$ f(\cdot ,y):X\to \mathbb {R} $ is concave for fixed $ y $, and
$ f(x,\cdot ):Y\to \mathbb {R} $ is convex for fixed $ x $.
Then we have that
$$ \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y). $$

---

Theorem 3.7. The Minimax Theorem: $\max _x \min _j x A_j=\min _y \max _i A_i y^T$, i.e.
\[
v_I=v_{I I}
\]
Proof. Let $A$ be a matrix game. According to Lemma 3.4, either condition (3.4) or (3.5) must be true.

Suppose condition (3.4) holds. Thus, 0 is contained in the convex hull of the $m+n$ points, and is therefore a convex linear combination of the $m+n$ vectors. Consequently, $\exists s_1, \ldots, s_{m+n}$ such that $\sum_{j=1}^n s_j a_{i j}+s n+i=0$ for $i=1, \ldots, m$, $s_j \geq 0$ for $j=1, \ldots, m+n$, and $\sum_{j=1}^{m+n} s_j=1$

If all the numbers $s_1, \ldots, s_n$ were 0, then 0 would be a convex linear combination of the $m$ unit vectors $e_1, \ldots, e_m$, which would be a contradiction since these are independent vectors. Therefore, at least one of the numbers $s_1, \ldots, s_n$ is positive,
meaning $\sum_{j=1}^n s_j>0$.
Let $y_j=s_j / \sum_{j=1}^n s_j$. Therefore $y_j \geq 0, \sum_{j=1}^n y_j=1$, and $\sum_{j=1}^n a_{i j} y_i=-s_{n+1} / \sum_{j=1}^n s_j \leq 0 \forall i$.
Thus $v(y) \leq 0$ and $v_{I I} \leq 0$.
Now suppose that condition (3.5) holds instead. Then $v(x)>0$, and $v_I>0$.
Since it is impossible for both conditions not to hold, it is not possible to have a situation in which $v_I \leq 0<v_{I I}$.
Now let's look at a different matrix game $B$, where $B=\left(b_{i j}\right)$, and $b_{i j}=a_{i j}+k$, where $k$ is a random variable. $\forall x, y,\; x B y^T=x A y^T+k$.
Therefore, $v_I(B)=v_I(A)+k$, and $v_{I I}(B)=v_{I I}(A)+k$. Since it is impossible for $v_I(B)<0<v_{I I}(B)$, we cannot obtain a situation in which $v_I(A)+k<0<v_{I I}(A)+k$, where by subtracting $k$ from both sides we get $v_I(A)<-k<v_{I I}(A)$.
But since $k$ was arbitrary, it is impossible for $v_I<v_{I I}$.
Using the same method as lemma 2.4 we see that $v_I \leq v_{I I}$. Therefore $v_I=v_{I I}$.

hbghlyj

hbghlyj 发表于 2024-7-4 02:59
一般不能取等。

关于原问题我有一个愚蠢的问题，$$\sup_{y\in [0,1]}\left(\inf_{x\in [0,1]}f(x,y)\right)\leq \inf_{x\in[0,1]}\left(\sup_{y\in[0,1]}f(x,y)\right)$$什么时候不取等

hbghlyj

二元实函数关于x的最小值关于y的最大值可以看作：在每个垂直于x轴的平面截面的曲线上取最小值，得到一条“沟壑”，然后在这条曲线上取最大值，得到一个“鞍点”。 二元实函数关于y的最大值关于x的最小值可以看作：在每个垂直于y轴的平面截面的曲线上取最大值，得到一条“山脊”，然后在这条曲线上取最小值，得到一个“鞍点”。
这两种“鞍点”什么时候不相等	上图描绘的是f(x, y) = x2 − y2

Minimax theorem #Special_case: Bilinear function