Theorem 5.8（Rockafellar 1970）

Convex Function
定理

$f_1, \dots, f_m$ を $\mathbb{R}^n$上の真凸関数とする。以下も凸関数である。

\begin{aligned} &f(x) = \inf \big\lbrace \max \lbrace f_1(x_1), \dots, f_m(x_m) \rbrace \ &\mid& \ x_1 + \cdots + x_m = x \big \rbrace \\ &g(x) = \inf \big\lbrace (f_1 \lambda_1)(x) + \cdots + (f_m \lambda_m)(x) \ &\mid& \lambda_i \ge 0, \ \lambda_1 + \cdots + \lambda_m = 1 \big\rbrace \\ &h(x) = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x) , \cdots, (f_m \lambda_m)(x) \rbrace \ &\mid& \lambda_i \ge 0, \ \lambda_1 + \cdots + \lambda_m = 1 \big\rbrace \\ &k(x) = \inf \big\lbrace \max \lbrace \lambda_1 f_1(x_1), \cdots, \lambda_m f_m(x_m) \rbrace \ &\mid& \lambda_1 x_1 + \dots + \lambda_m x_m = x \big\rbrace \\ \end{aligned}

方針

$f,g,h,k$順に、その関数を定義する錐に対して、$x$、$\lambda, \mu$ 、$\lambda$、$\lambda, x$についてpartial addtionをとれば良い。

証明

錐$K \equiv \lbrace (\lambda, x, \mu) \mid \lambda \ge 0, x \in \mathbb{R}^{n}, \mu \ge (f \lambda)(x) \rbrace$ を用いて、$F = \lbrace (x, \mu) \mid (1, x, \mu) \in K \rbrace$を定義する。
Theorem 5.3（Rockafellar 1970）より、凸関数は$\inf \lbrace \mu \mid (x, \mu) \in F \rbrace$より定まるため、そのことを念頭に以下を証明していく。

($f$の凸性)
$i = 1, \cdots, m$に対して、$K_{x_i} = \lbrace (\lambda, {x_i}, \mu) \mid \lambda \ge 0, x_i \in \mathbb{R}^{n}, \mu \ge (f_i \lambda)(x_i) \rbrace$を考え、$x$についてpartial addtionを行う。

\begin{aligned} K_{x} = \lbrace (\lambda, {x}, \mu) \mid &\lambda \ge 0, \\ &x_1, \cdots, x_m \in \mathbb{R}^{n}, \ x = x_1 + \cdots + x_m, \\ &\mu \ge (f_1 \lambda)(x_1) , \cdots, \ \mu \ge (f_m \lambda)(x_m) \rbrace \end{aligned}

この$K_x$から定まる関数を$f(x)$とすると、

\begin{aligned} f(x) &= \inf \lbrace \mu &\mid &\ x_1, \cdots, x_m \in \mathbb{R}^{n}, \ x = x_1 + \cdots + x_m, \\ & & & \mu \ge (f_1)(x_1) , \cdots, \ \mu \ge (f_m)(x_m) \rbrace \\ & = \inf \big\lbrace \max \lbrace f_1(x_1) , \cdots, f_m \rbrace &\mid & x_1, \cdots, x_m \in \mathbb{R}^{n}, x = x_1 + \cdots + x_m, \big\rbrace \end{aligned}

$K_{x_i}$から定まる$F$について、$x_i \in \mathbb{R}^{n}$で、$f_i$が真凸関数であることから凸集合となる。よって、Theorem 3.1（Rockafellar 1970）よりそのparitial additionで定まる集合も凸集合となる。このことからTheorem 5.3（Rockafellar 1970）より、$f(x)$が凸関数であることが言える。

($g$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i, \mu_i} = \lbrace (\lambda_i, x, \mu_i) \mid \lambda_i \ge 0, x \in \mathbb{R}^{n}, \mu_i \ge (f_i \lambda_i)(x) \rbrace$を考え、$\lambda, \mu$についてpartial addtionを行う。

\begin{aligned} K_{\lambda, \mu} = \lbrace (\lambda, {x}, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ &x \in \mathbb{R}^{n}, \mu = \mu_1 + \cdots + \mu_m, \mu_1 \ge (f_1 \lambda_1)(x) , \cdots, \ \mu_m \ge (f_m \lambda_m)(x) \rbrace \end{aligned}

この$K_{\lambda, \mu}$から定まる関数を$g(x)$とすると、

\begin{aligned} g(x) & = \inf \lbrace \mu &\mid &(1, x, \mu) \in K_{\lambda, \mu} \rbrace \\ & = \inf \lbrace \mu_1 + \cdots + \mu_m &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 , \\ & & & \mu_1 \ge (f_1 \lambda_1)(x) , \cdots, \ \mu_m \ge (f_m \lambda_m)(x) \rbrace \\ & = \inf \lbrace (f_1 \lambda_1)(x) + \cdots + (f_m \lambda_m)(x) & \mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 \rbrace \\ \end{aligned}

となる。$(f_i \lambda_i)(x)$は$\lambda_i \operatorname{epi}f_i$から定まる凸関数であるため、$K_{\lambda, \mu}$はそれらの積集合となるため、凸集合となる。よって、Theorem 5.3（Rockafellar 1970）より、$g(x)$が凸関数であることが言える。

($h$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i} = \lbrace (\lambda_i, x, \mu) \mid \lambda_i \ge 0, x \in \mathbb{R}^{n}, \mu \ge (f_i \lambda_i)(x) \rbrace$を考え、$\lambda$についてpartial addtionを行う。

\begin{aligned} K_{\lambda} = \lbrace (\lambda, x, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ \ &x \in \mathbb{R}^{n}, \mu \ge (f_1 \lambda_1)(x) , \cdots, \ \mu \ge (f_m \lambda_m)(x) \rbrace \end{aligned}

この$K_{\lambda, \mu}$から定まる関数を$h(x)$とすると、

\begin{aligned} h(x) & = \inf \lbrace \mu \mid (1, x, \mu) \in K_{\lambda} \rbrace \\ & = \inf \lbrace \mu \mid \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 , \ \mu \ge (f_1 \lambda_1)(x) , \cdots, \ \mu \ge (f_m \lambda_m)(x) \rbrace \\ & = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x) , \cdots , (f_m \lambda_m)(x) \rbrace \mid \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 \big\rbrace \\ \end{aligned}

となる。、$K_{\lambda, \mu}$から定まる$F$は、$\lambda$については確率単体であり、$x,\mu$については凸関数のepigraphであることから凸集合となっている。よって、Theorem 5.3（Rockafellar 1970）より、$h(x)$が凸関数であることが言える。

($k$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i, x_i} = \lbrace (\lambda_i, x_i, \mu) \mid \lambda_i \ge 0, x_i \in \mathbb{R}^{n}, \mu \ge (f_i \lambda_i)(x_i) \rbrace$を考え、$\lambda$についてpartial addtionを行う。

\begin{aligned} K_{\lambda, x} = \lbrace (\lambda, x, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ &x = x_1 + \cdots + x_m, x_1, \cdots, x_m \in \mathbb{R}^{n}, \\ &\mu \ge (f_1 \lambda_1)(x_1) , \cdots, \ \mu \ge (f_m \lambda_m)(x_m) \rbrace \end{aligned}

この$K_{\lambda, x}$から定まる関数を$k(x)$とすると、

\begin{aligned} k(x) & = \inf \lbrace \mu &\mid &(1, x, \mu) \in K_{\lambda, x} \rbrace \\ & = \inf \lbrace \mu &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0, \\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n}, \\ & & & \forall i \ \ \mu \ge (f_i \lambda_i)(x_i) \rbrace \\ & = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x_1) , \cdots , (f_m \lambda_m)(x_m) \rbrace &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0, \\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ & = \inf \big\lbrace \max \lbrace \lambda_1(f_1)({\lambda_1}^{-1}x_1) , \cdots , \lambda_m(f_m)({\lambda_m}^{-1}x_m) \rbrace &\mid & \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0,\\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ & = \inf \big\lbrace \max \lbrace \lambda_1f_1(x_1) , \cdots , \lambda_m f_m(x_m) \rbrace &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0,\\ & & &x = \Sigma_{i=1}^{m} \lambda_i x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ \end{aligned}

となる。最後２つの等式はright scalar multiplicationの定義および変数変換である。
$K_{\lambda, \mu}$から定まる$F$も凸集合となっており、Theorem 5.3（Rockafellar 1970）から$k(x)$が凸関数であることが言える。

参考文献

Tyrrell Rockafellar, R, 1970 p40