Fenchel–Rockafellarの双対定理

$x\notin D(\varphi)\cap D(\psi)$ なら右辺は $+\infty$ で自明である。$x\in D(\varphi)\cap D(\psi)$ とする。Fenchel–Young の不等式（Fenchel共役 の定理「共役の基本性質」の 2）を $\varphi$ と $-f$、$\psi$ と $f$ に使うと
$$ \langle -f,x\rangle\le\varphi(x)+\varphi^*(-f),\qquad\langle f,x\rangle\le\psi(x)+\psi^*(f) $$
である。左辺の和は $0$ である。$\varphi^*(-f)$、$\psi^*(f)$ の一方が $+\infty$ なら $d(f)=-\infty$ で主張は自明であり、どちらも有限なら、足して移項すると $d(f)\le\varphi(x)+\psi(x)$ を得る。$x$ について下限、$f$ について上限をとれば $b\le a$ である。$\square$

$p$ を中心とする半径 $r>0$ の開球が $C$ に含まれるとする。$\|w\|< tr$ なら $(1-t)c+tp+w=(1-t)c+t(p+w/t)$ で、$\|w/t\|< r$ より $p+w/t\in C$ なので、$C$ の凸性からこの点は $C$ に入る。よって $(1-t)c+tp$ を中心とする半径 $tr$ の開球が $C$ に含まれる。$c$ も内部の点にとれば $\operatorname{Int}C$ の凸性が従う。最後の主張は $t=1/n$ とした点 $(1-\frac1n)c+\frac1np$ が $n\to\infty$ で $c$ に収束することによる。$\square$

$x_0$ で $\varphi(x_0)+\psi(x_0)$ は有限なので $a< +\infty$ である。$a=-\infty$ なら、弱双対性（prop-fr-weak）からすべての $f$ で $d(f)=-\infty=a$ であり、主張は成り立つ。以下 $a\in\mathbb{R}$ とする。
段 1：分離する 2 つの凸集合。 $E\times\mathbb{R}$ にノルム $\|(x,\lambda)\|:=\|x\|+|\lambda|$ を入れ、$C:=\{(x,\lambda)\in E\times\mathbb{R}\mid\varphi(x)\le\lambda\}$ を $\varphi$ のエピグラフとする。$\varphi$ は凸なので $C$ は凸集合である（Fenchel–Moreauの定理 の命題「エピグラフによる言いかえ」の 1）。$\varphi$ は $x_0$ で連続なので、$r>0$ を $\|x-x_0\|< r$ なら $\varphi(x)< \varphi(x_0)+1$ となるようにとれる。このとき開集合 $\{x\mid\|x-x_0\|< r\}\times(\varphi(x_0)+1,\infty)$ は $C$ に含まれるので、$A:=\operatorname{Int}C$ は空でなく、lem-fr-interior により凸である。$(x,\lambda)\in A$ なら $\lambda>\varphi(x)$ である。実際 $\lambda=\varphi(x)$ なら、どんなに小さい $\varepsilon>0$ でも $(x,\lambda-\varepsilon)\notin C$ となり、内点であることに反する。
$$ B:=\bigl\{(x,\lambda)\in E\times\mathbb{R}\ \big|\ x\in D(\psi),\ \lambda\le a-\psi(x)\bigr\} $$
とおく。$(x_0,a-\psi(x_0))\in B$ なので $B$ は空でなく、$\psi$ の凸性から $B$ は凸である。$(x,\lambda)\in A\cap B$ があれば $\varphi(x)< \lambda\le a-\psi(x)$ となり、$\varphi(x)+\psi(x)< a$ が $a$ の定義に反する。よって $A\cap B=\emptyset$ である。
段 2：分離。 $A$ は開凸集合なので、Hahn–Banachの定理 の定理「Hahn–Banachの定理（第一幾何形）」により、$0$ でない連続線形汎関数 $\Phi$ と $\alpha\in\mathbb{R}$ で $\Phi< \alpha$（$A$ 上）、$\Phi\ge\alpha$（$B$ 上）となるものがある。$\Phi$、$\alpha$ を $-\Phi$、$-\alpha$ に替えて、$A$ 上で $\Phi>\alpha$、$B$ 上で $\Phi\le\alpha$ としてよい。Fenchel–Moreauの定理 の命題「エピグラフによる言いかえ」の 3 により $\Phi(x,\lambda)=\langle g,x\rangle+k\lambda$（$g\in E^*$、$k\in\mathbb{R}$）と書ける。lem-fr-interior により $C$ の各点は $A$ の点列の極限なので、$\Phi$ の連続性から
$$ \langle g,x\rangle+k\lambda\ge\alpha\quad((x,\lambda)\in C),\qquad\langle g,x\rangle+k\lambda\le\alpha\quad((x,\lambda)\in B)\qquad(1) $$
である。
段 3：$k>0$。 $\lambda\ge\varphi(x_0)$ なら $(x_0,\lambda)\in C$ なので、(1) の左から $\langle g,x_0\rangle+k\lambda\ge\alpha$ がいくらでも大きい $\lambda$ で成り立ち、$k\ge0$ である。$k=0$ と仮定すると、$\Phi\neq0$ より $g\neq0$ である。(1) の左から $D(\varphi)$ 上で $\langle g,x\rangle\ge\alpha$、右から（$x=x_0$、$\lambda=a-\psi(x_0)$ として）$\langle g,x_0\rangle\le\alpha$ である。$\|z\|< 1$ なら $x_0+rz\in D(\varphi)$ なので $\langle g,x_0\rangle+r\langle g,z\rangle\ge\alpha\ge\langle g,x_0\rangle$、すなわち $\langle g,z\rangle\ge0$ である。$z$ を $-z$ に替えると $\langle g,z\rangle=0$ となり、単位開球上で $0$ の線形汎関数は $0$ なので $g=0$ となって矛盾する。よって $k>0$ である。
段 4：双対問題の解。 $\bar f:=g/k$ とおく。$x\in D(\varphi)$ について $(x,\varphi(x))\in C$ なので (1) の左を $k$ で割ると $\langle\bar f,x\rangle+\varphi(x)\ge\alpha/k$、すなわち $\langle-\bar f,x\rangle-\varphi(x)\le-\alpha/k$ であり、上限をとって $\varphi^*(-\bar f)\le-\alpha/k$ である。$x\in D(\psi)$ について $(x,a-\psi(x))\in B$ なので (1) の右から $\langle\bar f,x\rangle+a-\psi(x)\le\alpha/k$ であり、$\psi^*(\bar f)\le\alpha/k-a$ である。2 つの共役は真の関数の共役なので $-\infty$ でなく、どちらも有限である。足すと $\varphi^*(-\bar f)+\psi^*(\bar f)\le-a$、すなわち $d(\bar f)\ge a$ である。弱双対性から $d(\bar f)\le b\le a$ なので $d(\bar f)=b=a$ である。$\square$

4 つの値 $\varphi(\bar x)$、$\psi(\bar x)$、$\varphi^*(-\bar f)$、$\psi^*(\bar f)$ がすべて有限のとき、
$$ \varphi(\bar x)+\psi(\bar x)-d(\bar f)=\bigl(\varphi(\bar x)+\varphi^*(-\bar f)-\langle-\bar f,\bar x\rangle\bigr)+\bigl(\psi(\bar x)+\psi^*(\bar f)-\langle\bar f,\bar x\rangle\bigr) $$
であり、Fenchel–Young の不等式から右辺の 2 つの括弧はどちらも $0$ 以上である。左の条件のもとでは、和が有限なので $\varphi(\bar x)$、$\psi(\bar x)$ は有限（どちらも $-\infty$ をとらない）、$d(\bar f)$ が有限なので 2 つの共役も有限であり、左辺が $0$ なので両方の括弧が $0$ である。右の条件のもとでは、劣微分 の命題「劣微分の基本性質」の 4 により 4 つの値は有限で両方の括弧が $0$ なので、左辺が $0$ である。いずれの場合も括弧が $0$ であることは、同じ命題の 4 により右の条件と同値である。最後の主張は、弱双対性から $d(\bar f)\le b\le a\le\varphi(\bar x)+\psi(\bar x)$ の両端が等しいことによる。$\square$

$\bar f$ が存在すれば prop-fr-extremality により $\bar x$ は最小点である。逆に $\bar x$ が最小点なら、$a=\varphi(\bar x)+\psi(\bar x)$ は $x_0$ での値以下なので有限である。thm-fr-main により $d(\bar f)=a$ となる $\bar f$ があり、prop-fr-extremality から結論を得る。$\square$

$\supset$ は 劣微分 の命題「劣微分の和」の 1 である。$h\in\partial(\varphi+\psi)(x)$ とすると、$x$ は $(\varphi-\langle h,\cdot\rangle)+\psi$ の最小点である。$\tilde\varphi:=\varphi-\langle h,\cdot\rangle$ は凸で、$x_0$ で連続なので、cor-fr-primal により $-\bar f\in\partial\tilde\varphi(x)$、$\bar f\in\partial\psi(x)$ となる $\bar f$ がある。定義から $\partial\tilde\varphi(x)=\partial\varphi(x)-h$ なので $h-\bar f\in\partial\varphi(x)$ であり、$h=(h-\bar f)+\bar f\in\partial\varphi(x)+\partial\psi(x)$ である。$\square$