用户: Rushcheyo/对偶性

对偶性是我们研究凸优化问题的重要工具, 在优化和算法设计等领域应用广泛. 本文将以几何直观的方式较为自然的引入对偶性, 并且证明一些比较重要的对偶定理.

1基本定义

设 $V$ 是一个线性空间, 扩展实数 $\overline{\mathbb{R}}:=\mathbb{R}\cup \{+\infty ,-\infty \}$, 为了方便我们使用如下的凸函数定义:

定义 1.1.

我们称 $f:V\to \overline{\mathbb{R}}$ 是凸函数当且仅当:

$$\forall u,v\in V,\lambda \in [0,1],f(\lambda u+(1-\lambda )v)\le \lambda f(u)+(1-\lambda )f(v).$$(1)

上式只在 $u$ 和 $v$ 不是不同号的无穷大时作要求.

我们定义函数 $f$ 的图像 (英文: epigraph) 是集合 $\mathrm{epi}f:=\{(u,a)\in V\times \mathbb{R}:f(u)\le a\}$. 注意这里我们并不考虑 $\pm \infty$.

命题 1.2. 函数 $f$ 是凸函数当且仅当 $\mathrm{epi}f$ 是凸集.

证明. 由于 “仅当” 的方向比较简单, 下面只证 “当” 的方向.

任取 $u,v\in V,\lambda \in [0,1]$. 如果 $f(u)$ 或 $f(v)$ 为 $+\infty$, (1) 式明显成立, 否则取实数 $a\ge f(u),b\ge f(v)$, 由于 $\mathrm{epi}f$ 是凸集, $\lambda (u,a)+(1-\lambda )(v,b)\in \mathrm{epi}f$, 于是:

$$f(\lambda u+(1-\lambda )v)\le \lambda a+(1-\lambda )b$$(2)

如果 $f(u)$ 和 $f(v)$ 不是 $-\infty$ 令 $a=f(u),b=f(v)$ 即可, 否则令 $a,b\to -\infty$.

$\square$

从而, 凸集 $\mathrm{epi}f$ 的一个截面 $\{u\in V:f(u)\le a\}$ 也是凸集. 反过来, 若 $S$ 是凸集, 其示性函数 ${\mathrm{ind}}_S(x)=\{\begin{array}{ll}0& x\in S\\ +\infty & x\notin S\end{array}$ 也是凸函数.

凸优化问题是指在凸集 $S\subseteq V$ 上求解凸函数 $f$ 的最小值 (确切地说, ${\inf }_{x\in S}f(x)$) . 由上面的讨论, 我们可以只考虑优化问题 $\inf \{f(x):g(x)\le 0\}$, 其中 $f,g$ 都是 $V$ 上的凸函数.

2凸集的对偶

后面的讨论中, 我们总假设 $V$ 是 Banach 空间, 记 $V^{\ast }$ 是 $V$ 的对偶空间, 即 $V$ 上的连续线性函数集合配备算子范数.

定义 2.1. 对于 $m^{\ast }\in V^{\ast },\alpha \in \mathbb{R}$, 我们把 $x\mapsto m^{\ast }(x)-\alpha$ 称为一个仿射函数, $m^{\ast }$ 和 $\alpha$ 分别是斜率和截距, 集合 $\{x\in V:m^{\ast }(x)-\alpha =0\}$ 则是超平面; 相应的, $\{x\in V:m^{\ast }(x)-\alpha \le 0\}$ 则是半平面. 我们不加区分的使用这几个词.

对于两个不交的凸集, 我们总可以用一个超平面将它们分离开, 于是有下面的定理.

定理 2.2 (超平面分离定理). 令 $A,B$ 是 $V$ 上两个不交的非空凸子集, 存在不同时为 $0$ 的 $m^{\ast },\alpha$ 使得:

$$\forall x\in A,y\in B,m^{\ast }(x)-\alpha \ge 0,m^{\ast }(y)-\alpha \le 0$$

注意两个等号都是取得到的, 考虑 $V={\mathbb{R}}^2$, $A=\{(x,y):x>0\}\cup \{(0,y):y>0\}$, $B=\overline{A}$. 对两个闭子集, 则可以建立严格的分离, 但我们不需要.

该定理的完整证明需要许多铺垫且与主题无关, 我们难以收录, 读者可在任何泛函分析教材上找到, 也可参考 Hahn–Banach theorem. Hilbert 空间的证明可以见维基百科 (另外, 我们知道 ${\mathbb{R}}^n$ 上的线性映射都可以表为内积) .

下面的命题是上述定理的简单推论:

命题 2.3. 对于闭的凸集 $S$, 所有包含 $S$ 的半平面之交 $\mathrm{aff}(S)$ 恰好为 $S$.

证明. 显然 $S\subseteq \mathrm{aff}(S)$. 若 $x\notin S$, 则有包含 $x$ 的小球 $B_{\epsilon }(x)$ 与 $S$ 不交, 对 $B_{\epsilon }(x)$ 和 $S$ 使用定理 2.2 得到分离超平面 $m^{\ast }(x)-\alpha =0$. 该仿射函数在 $x$ 上的取值不可能是 $0$, 否则以 $x$ 为原点其是非零线性函数, 在球内取值有正有负, 与分离的同号要求相悖. 从而 $x$ 同样不在 $\mathrm{aff}(S)$ 内.

$\square$

命题 2.3 给我们这样的启发: 为了研究凸集, 我们可以转而研究包含它的所有超平面, 后者包含了前者的全部信息. 这一思想是所谓的对偶原理的核心.

3共轭函数

现在, 我们考虑包含凸函数 $f$ 的图像 $\mathrm{epi}f$ 的半平面 $\{(x,y)\in V\times \mathbb{R}:m^{\ast }(x)-\alpha \le y\}$, 需满足:

$$\forall x\in V,m^{\ast }(x)-\alpha \le f(x)$$

这也就是:

$$\forall x\in V,\alpha \ge m^{\ast }(x)-f(x)$$

我们显然只用考虑最紧的那些半平面, 这使得如下定义顺理成章:

定义 3.1. $f$ 的共轭函数 $f^{\ast }:V^{\ast }\to \overline{\mathbb{R}}$ 定义为:

$$\forall m^{\ast }\in V^{\ast },f^{\ast }(m^{\ast })=\underset{x\in V}{\sup }{m}^{\ast }(x)-f(x)$$(3)

有了 “对偶”、“共轭” 的暗示, 下面的关系成立也并不奇怪:

命题 3.2. 设 $\mathrm{id}:V\to V^{\ast \ast }$ 是 $V$ 与 $V^{\ast \ast }$ 的自然保距同构. 如果 $f$ 闭 (即 $\mathrm{epi}f$ 闭) , 那么 $f=f^{\ast \ast }\circ \mathrm{id}$.

证明. 我们只需证 $\mathrm{epi}f=\mathrm{epi}\left(f^{\ast \ast }\circ \mathrm{id}\right)$.

依定义,

$$\begin{array}{rl}\forall n\in V,f^{\ast \ast }\left(\mathrm{id}(n)\right)& =\underset{m^{\ast }\in V^{\ast }}{\sup }\mathrm{id}(n)(m^{\ast })-f^{\ast }(m^{\ast })\\ & =\underset{m^{\ast }\in V^{\ast }}{\sup }{m}^{\ast }(n)-\underset{x\in V}{\sup }\left(m^{\ast }(x)-f(x)\right)\\ & =\underset{m^{\ast }\in V^{\ast }}{\sup }\underset{x\in V}{\inf }{m}^{\ast }(n-x)+f(x)\\ & \le f(n)\end{array}$$

这说明 $\mathrm{epi}f\subseteq \mathrm{epi}\left(f^{\ast \ast }\circ \mathrm{id}\right)$. 由命题 2.3, $\mathrm{aff}(\mathrm{epi}f)=\mathrm{epi}f$, 故只需证 $\mathrm{epi}\left(f^{\ast \ast }\circ \mathrm{id}\right)\subseteq \mathrm{aff}(\mathrm{epi}f)$.

任取满足 $\forall x\in V,l^{\ast }(x)-\alpha \le f(x)$ 的超平面, 需证 $l^{\ast }(n)-\alpha \le f^{\ast \ast }(\mathrm{id}(n))$, 在 $\sup$ 号中取 $m^{\ast }=l^{\ast }$ 归约到证明:

$$\begin{array}{rl}& l^{\ast }(n)-\alpha \le \underset{x\in V}{\inf }{l}^{\ast }(n-x)+f(x)\\ ⟺& -\alpha \le \underset{x\in V}{\inf }f(x)-l^{\ast }(x)\\ ⟺& \underset{x\in V}{\inf }f(x)-(l^{\ast }(x)-\alpha )\ge 0\end{array}$$

由 $(l^{\ast },\alpha )$ 的选取立得.

$\square$

4优化问题的对偶

读者或许已经知道 (我们也将会提及) , 同一优化问题的不同写法会导致对偶问题不同, 实际上对偶问题的确定需要我们指定一个扰动方式.

对两个 Banach 空间 $X,Y$, 有函数 $\phi :X\times Y\to \overline{\mathbb{R}}$, 优化目标是 ${\inf }_{x\in X}\phi (x,0)$, 那么扰动后的问题便是 $h(y)={\inf }_{x\in X}\phi (x,y)$, 而对偶问题, 正是求 $h^{\ast \ast }(0)$. 如果 $h$ 是凸函数且闭, 那么由命题 3.2 $h^{\ast \ast }(0)=h(0)$, 这叫做强对偶原理, 否则只能得到 $h^{\ast \ast }(0)\ge h(0)$ (命题 3.2 证明的前半段) , 这叫做弱对偶原理. 此时 $h^{\ast \ast }(0)-h(0)$ 被叫做对偶间隙 (英文: duality gap) .

先处理一下 $h$ 的凸性. 至于闭性 (约等于在值不取无穷部分的连续性) 则比较复杂, 后面再说.

命题 4.1. 如果 $\phi$ 是凸函数, 那么 $h$ 是凸函数.

证明. 对 $y_1,y_2\in Y$ 和 $\lambda \in [0,1]$, 我们必须证明:

$$\underset{x\in X}{\inf }\phi (x,\lambda y_1+(1-\lambda )y_2)\le \lambda \underset{x\in X}{\inf }\phi (x,y_1)+(1-\lambda )\underset{x\in X}{\inf }\phi (x,y_2)$$

上式的右边如果是 $+\infty$ 或无定义, 没什么好证明的. 否则任取 $h(y_1)<a<+\infty ,h(y_2)<b<+\infty$, 存在 $h(y_1)\le \phi (x,y_1)<a,h(y_2)\le \phi (v,y_2)<b$, 从而:

$$\begin{array}{rl}& \underset{x\in X}{\inf }\phi (x,\lambda y_1+(1-\lambda )y_2)\\ \le & \phi (\lambda u+(1-\lambda )v,\lambda y_1+(1-\lambda )y_2)\\ \le & \lambda \phi (u,y_1)+(1-\lambda )\phi (v,y_2)\\ <& \lambda a+(1-\lambda )b\end{array}$$

令 $a\to h(y_1),b\to h(y_2)$ 即证.

$\square$

我们写出对偶问题的具体形式:

$$\begin{array}{rl}{h}^{\ast \ast }(0)& =\underset{m^{\ast }\in Y^{\ast }}{\sup }\underset{y\in V}{\inf }h(y)-m^{\ast }(y)\\ & =\underset{m^{\ast }\in Y^{\ast }}{\sup }\underset{y\in V}{\inf }\underset{x\in V}{\inf }\phi (x,y)-m^{\ast }(y)\\ & =\underset{m^{\ast }\in Y^{\ast }}{\sup }-{\phi }^{\ast }(0,m^{\ast })\end{array}$$

总结一下:

定义 4.2. 优化问题 ${\inf }_{x\in X}\phi (x,0)$ 的对偶问题是 ${\sup }_{m^{\ast }\in Y^{\ast }}-{\phi }^{\ast }(0,m^{\ast })$.

以下命题正当化了 “对偶” 一词的使用.

命题 4.3. 如果 $V$ 自反, $\phi$ 凸且闭, 优化问题 ${\sup }_{m^{\ast }\in Y^{\ast }}-{\phi }^{\ast }(0,m^{\ast })$ 的对偶问题是 ${\inf }_{x\in X}\phi (x,0)$.

证明. 为了让对偶问题有定义, 我们改写成 $-{\inf }_{m^{\ast }\in Y^{\ast }}{\phi }^{\ast }(0,m^{\ast })$, 对偶后就是 ${\sup }_{m^{\ast \ast }\in X^{\ast \ast }}{\phi }^{\ast \ast }(m^{\ast \ast },0)$, 由命题 3.2 立得.

$\square$

5Lagrange 对偶

我们现在讨论优化问题 $\inf \{f(x):g(x)\le 0\}$, 其中 $f:X\to \overline{\mathbb{R}},g:X\to Y$, $Y$ 是元素为 $I\to \mathbb{R}$ 映射的实 Banach 空间, 这里 $g$ 的含义是一族限制的交, 这些限制以 $I$ 为指标集.

扰动方式很直接: $\inf \{f(x):g(x)+y\le 0\}$. 于是定义 $\phi (x,y)=\{\begin{array}{ll}f(x)& g(x)+y\le 0\\ +\infty & \text{otherwise}\end{array}$, 计算 $-{\phi }^{\ast }(0,y^{\ast })$:

$$\begin{array}{rl}-{\phi }^{\ast }(0,y^{\ast })& =-\underset{g(x)+q\le 0}{\sup }{y}^{\ast }(q)-f(x)\\ & =-\underset{x\in X,q\ge 0}{\sup }{y}^{\ast }(-g(x)-q)-f(x)\\ & =\underset{x\in X,q\ge 0}{\inf }f(x)+y^{\ast }(g(x))+y^{\ast }(q)\\ & =\underset{x\in X}{\inf }f(x)+y^{\ast }(g(x))+\underset{q\ge 0}{\inf }{y}^{\ast }(q)\end{array}$$

注意里面的 $\inf$ 号如果 $y^{\ast }\ge 0$ 不成立 ($y^{\ast }\ge 0$ 是指 $\forall q\ge 0,y^{\ast }(q)\ge 0$) , 可以取 $q$ 使得 $q(y)\to -\infty$, 最终得到:

$$\underset{y^{\ast }\in Y^{\ast }}{\sup }-{\phi }^{\ast }(0,y^{\ast })=\underset{y^{\ast }\ge 0}{\sup }\underset{x\in X}{\inf }f(x)+y^{\ast }(g(x))$$(4)

上面的形式相信读者并不陌生: $y^{\ast }$ 便是所谓的 Lagrange 乘数. 处理形如 $g(x)=0$ 的限制则拆成 $g(x)\le 0$ 和 $-g(x)\le 0$, 重算一遍:

$$\begin{array}{rl}-{\phi }^{\ast }(0,y^{\ast },z^{\ast })& =-\underset{g(x)+q\le 0,-g(x)+p\le 0}{\sup }{y}^{\ast }(q)+z^{\ast }(p)-f(x)\\ & =-\underset{x\in X,p,q\ge 0}{\sup }{y}^{\ast }(-g(x)-q)+z^{\ast }(g(x)-p)-f(x)\\ & =\underset{x\in X,p,q\ge 0}{\inf }f(x)+(y^{\ast }-z^{\ast })(g(x))+y^{\ast }(q)+z^{\ast }(p)\\ & =\underset{x\in X}{\inf }f(x)+(y^{\ast }-z^{\ast })(g(x))+\underset{p,q\ge 0}{\inf }{y}^{\ast }(q)+z^{\ast }(p)\end{array}$$于是:

$$\underset{y^{\ast },z^{\ast }\in Y^{\ast }}{\sup }-{\phi }^{\ast }(0,y^{\ast },z^{\ast })=\underset{y^{\ast },z^{\ast }\ge 0}{\sup }\underset{x\in X}{\inf }f(x)+(y^{\ast }-z^{\ast })(g(x))=\underset{y^{\ast }\in Y^{\ast }}{\sup }\underset{x\in X}{\inf }f(x)+y^{\ast }(g(x))$$

最后一步是由于 $Y^{\ast }$ 中每个元素都能拆成两个非负元素之差: $y^{\ast }=\Vert y^{\ast }\Vert -(\Vert y^{\ast }\Vert -y^{\ast })$.

为了使用命题 3.2, 我们需要验证两个条件. 首先 $f$ 和 $g$ 凸时, $\phi$ 的凸性等价于 $\{(x,y):g(x)+y^{\ast }\le 0\}$ 是凸集, 由 $g(x)+y^{\ast }$ 的凸性立得. 现在整理成如下定理:

定理 5.1 (Lagrange 对偶). 对于凸函数 $f$ 和 $g$, 若扰动函数 $h(y)={\inf }_{g(x)+y\le 0}f(x)$ 在某个包含 $0$ 的邻域上连续, 则成立:

$$\underset{g(x)\le 0}{\inf }f(x)=\underset{y^{\ast }\ge 0}{\sup }\underset{x\in X}{\inf }f(x)+y^{\ast }(g(x))$$(5)

请注意, $f,g$ 再光滑都不能推出 $h$ 连续, 事实上 $h$ 的连续性是优化问题本身的正则性. 如果 $g$ 是一个局部的同胚, 即 $Y$ 的包含 $0$ 的开集和 $X$ 中的一个开集之间的连续双射, 那么 $h(y)={\inf }_{x+y\le 0}f(g^{-1}(x))$ 自然连续. 然而, 如果我们的限制有 (譬如说) 很大的冗余性, 一些限制必须取到 $0$, 那么将 $g$ 扰动一下就一定会远离最小值, $h$ 不可能连续, 不过我们也不是没有办法. 我们考虑 (5) 式左边如果在 $x^{\ast }$ 处取到最小值, 若向量 $g(x^{\ast })$ 中已经有一些限制是紧的 (即取到 $0$) , 无法再扰动, 我们可以进入不紧的那些限制构成的子空间扰动, 这样我们便可能继续使用定理 5.1.

下面看几个经典例子.

例 5.2 (线性规划). 线性规划是指 $f$ 和 $g$ 都是仿射函数的情形, 即 $f(x)=c^{\ast }(x),g(x)=A(x)+b$ ($f$ 的常数没多少意义) , 其中 $c^{\ast }\in X^{\ast },b\in Y$, $A:X\to Y$ 是连续线性映射.

回忆对偶映射 $A^{\ast }:Y^{\ast }\to X^{\ast }$ 的定义: $A^{\ast }(y^{\ast })(x)=y^{\ast }(A(x))$.

我们化简对偶问题:

$$\begin{array}{rl}& \underset{y^{\ast }\ge 0}{\sup }\underset{x\in X}{\inf }f(x)+y^{\ast }(g(x))\\ =& \underset{y^{\ast }\ge 0}{\sup }\underset{x\in X}{\inf }{c}^{\ast }(x)+y^{\ast }(A(x))+y^{\ast }(b)\\ =& \underset{y^{\ast }\ge 0}{\sup }{y}^{\ast }(b)+\underset{x\in X}{\inf }\left(A^{\ast }(y^{\ast })+c^{\ast }\right)(x)\\ =& \underset{y^{\ast }\ge 0,A^{\ast }(y^{\ast })+c^{\ast }=0}{\sup }{y}^{\ast }(b)\end{array}$$

最后一步是因为当仿射 $A^{\ast }(y^{\ast })+c^{\ast }$ 不为 $0$ 时, 值必定无下界. 如果原始问题里有 $x\ge 0$ 的要求, 这里自然就是 $A^{\ast }(y^{\ast })+c^{\ast }\ge 0$.

例 5.3 (算子范数). 给定复 Hilbert 空间 $H$ 上的连续线性算子 $A:H\to \mathbb{C}$, 求解优化问题 $\Vert A{\Vert }_{op}=\sup \{\Vert Ax{\Vert }_2:\Vert x{\Vert }_2\le 1\}$.

改写成 $\sqrt{-\inf \{-⟨Ax,Ax⟩:⟨x,x⟩-1\le 0\}}$, 计算对偶问题 (注意需要验证凸且连续) :

$$\begin{array}{rl}& \underset{\alpha \ge 0}{\sup }\underset{x\in {\mathbb{R}}^n}{\inf }-⟨Ax,Ax⟩+\alpha (⟨x,x⟩-1)\\ =& \underset{\alpha \ge 0}{\sup }-\alpha +\underset{x\in {\mathbb{R}}^n}{\inf }⟨\left(\alpha I-A^{\ast }A\right)x,x⟩\end{array}$$

当 $\alpha I-A^{\ast }A\ge 0$ 不成立时, 里面的 $\inf$ 号是 $-\infty$, 因此答案就是:

$$\begin{array}{rl}& \sqrt{-\underset{\alpha I-A^{\ast }A\ge 0}{\sup }-\alpha }\\ =& \sqrt{\underset{\alpha I-A^{\ast }A\ge 0}{\inf }\alpha }\end{array}$$

集合 $\{\alpha \in R:\alpha I-A^{\ast }A\ge 0\}$ 是 $R$ 的一个后部. 由连续性, 取到该 $\inf$ 的 $\ge$ 必然不严格, 即 $\alpha I-A^{\ast }A$ 不是单射, 或者说 $\alpha$ 是 $A^{\ast }A$ 的特征值. 这样 $\Vert A{\Vert }_{op}$ 就是 $A^{\ast }A$ 的最小特征值开根号.

例 5.4 (半正定规划). 考虑有限维复 Hilbert 空间 $H$, 设 $B=\{x\in H:\Vert x{\Vert }_2=1\}$ 是 $H$ 上的单位球, 在例 5.2 中取 $X$ 是 $H$ 上所有自伴算子组成的有限维实 Hilbert 空间, $Y=C(B)$ 是紧集 $B$ 上的连续函数组成的 Banach 空间 (配备 $L^{\infty }$ 范数) . $\forall A\in X,x\in B,g(A)(x)=⟨-Ax,x⟩$, 容易验证 $g$ 的确是 $X\to Y$ 的连续线性映射.

除了由这里 $g(A)\le 0$ 给出的 $A\ge O$ 的限制外, 还可以加一些 $A$ 的线性限制 $⟨L_i,A⟩+b_i\le 0,i=1,2,\dots ,m$, 现在对偶:

$$\begin{array}{rl}& \underset{y^{\ast }\ge 0,z\ge 0}{\sup }\underset{A\in X}{\inf }⟨C,A⟩+y^{\ast }(g(A))+⟨z,b⟩+\sum _{i=1}^m{z}_i⟨L_i,A⟩\\ =& \underset{y^{\ast }\ge 0,z\ge 0}{\sup }⟨z,b⟩+\underset{A\in X}{\inf }\left({\left(C+\sum _{i=1}^m{z}_i{L}_i\right)}^{\ast }+(y^{\ast }\circ g)\right)(A)\\ =& \sup \left\{⟨z,b⟩:z\ge 0,T(z):=C+\sum _{i=1}^m{z}_i{L}_i,\exists y^{\ast }\ge 0,\forall A\in X,⟨T(z),A⟩=y^{\ast }(-g(A))\right\}\\ =& \sup \left\{⟨z,b⟩:z\ge 0,C+\sum _{i=1}^m{z}_i{L}_i\ge O\right\}\end{array}$$

最后一步的集合相等关系的解释: 若 $T(z)$ 非半正定, 可以找到与 $T(z)$ 交换的半正定的 $A$ 使得内积为负, 然而等式右边非负; 若 $T(z)\ge O$, 设其谱分解为 $T(z)={\sum }_{i=1}^n{\lambda }_i{v}_i{v}_i^{\ast }$, 则 $⟨T(z),A⟩={\sum }_{i=1}^n{\lambda }_i⟨A{v}_i,v_i⟩$. 那么我们定义 $y^{\ast }(f)={\sum }_{i=1}^n{\lambda }_{i}f(v_i)$, 则容易验证 $y^{\ast }$ 是 $B$ 上连续线性映射, $y^{\ast }\ge 0$, 且 $y^{\ast }(-g(A))=⟨T(z),A⟩$.

6Minimax 定理

我们仍然让底空间是 $X\times Y$, 其中 $X$ 和 $Y$ 是自反的 Banach 空间. 为了避免琐碎的正则性讨论喧宾夺主, 我们考虑一个较弱的版本:

定理 6.1 (Minimax 定理 (弱) ). 令 $K\subset X$ 和 $C\subset Y$ 是两个紧凸集, 若连续函数 $f:X\times Y\to \mathbb{R}$ 满足:

1.	$\forall y\in C$, $f(\cdot ,y)$ 是凸函数,
2.	$\forall x\in K$, $f(x,\cdot )$ 是凹函数,

那么成立:

$$\underset{x}{\min }\underset{y}{\max }f(x,y)=\underset{y}{\max }\underset{x}{\min }f(x,y).$$

和弱对偶性类似, 我们有以下的命题:

命题 6.2. 对任意实值函数 $f$, 成立:

$$\underset{x}{\inf }\underset{y}{\sup }f(x,y)\le \underset{y}{\sup }\underset{x}{\inf }f(x,y)$$

证明. $$\begin{array}{rl}& \underset{x}{\inf }\underset{y}{\sup }f(x,y)\le \underset{y}{\sup }\underset{x}{\inf }f(x,y)\\ \iff & \forall x_0,y_0,\underset{y}{\sup }f(x_0,y)\le \underset{x}{\inf }f(x,y_0)\end{array}$$

而 ${\sup }_{y}f(x_0,y)\ge f(x_0,y_0)\ge {\inf }_{x}f(x,y_0)$.

$\square$

容易验证, ${\max }_{y}f(x,y)$ 是连续凸函数, ${\min }_{x}f(x,y)$ 是连续凹函数. 下面证明较难的另一半:

定理 6.1 的证明. 考虑优化问题 $-\inf \{a:\forall x\in K,-a\le {\max }_{y}f(x,y)\}$: 这是一个线性规划问题, 限制空间取紧集 $K$ 上的连续函数组成的 Banach 空间 $C(K)$ (配备 $L^{\infty }$ 范数) , 那么限制函数 $h(a)(x)=-{\max }_{y}f(x,y)-a$ 自然是 $\mathbb{R}\to C(K)$ 的连续线性映射.

对偶: ${\inf }_{L\ge 0,L(\mathrm{id})=1}L({\max }_{y}f(x,y))$, 其中 $\mathrm{id}$ 将实数映至对应的常函数. 那么我们必须证明:

$$\forall L\ge 0,L(\mathrm{id})=1,y_0,L(\underset{y}{\max }f(x,y_0))\ge \underset{x}{\min }f(x,y_0)$$

然而

$$\forall x_0,y_0,\underset{y}{\max }f(x_0,y)\ge f(x_0,y_0)\ge \underset{x}{\min }f(x,y_0)$$

考虑到 ${\max }_y(x,y_0)-{\min }_{x}f(x,y_0)\ge 0$, 两边用 $L$ 作用即证.

然而这个证明肯定是错的. . 因为没用到凸函数条件, 看来还得将无穷维 LP 对偶的正则性问题处理好, 有限维是没这个问题的

$\square$

参考文献

[ET99]

Ekeland and Témam (1999). Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics.