凸関数¶

基本的な性質¶

これはちょっとした共有用に準備したページで, 現代数学探険隊 解析学編には凸関数の基本的な性質に関してまとまった記録があります.

ここでは下に凸な関数を単に凸関数と呼びます.

凸関数族の上限は凸¶

凸集合$\Omega \subset \mathbb{R}^d$上の凸関数の族 $(f_\lambda){\lambda \in \Lambda}$ に対して $f = \sup f_\lambda$ とする. この$f$は凸である.

証明¶

任意の$a \in (0,1)$と$x,y \in \Omega$を取る. 任意の$\lambda \in \Lambda$に対して \begin{align} f_\lambda (ax + (1-a)y) \leq a f_\lambda(x) + (1-a) f_\lambda(y) \leq a f(x) + (1-a)f(y) \end{align} が成り立つ. 左辺の上限を取ると求める凸性が得られる.

凸関数の和は凸¶

凸集合$\Omega \subset \mathbb{R}^d$上の凸関数 $f_1, \dots, f_n \colon \Omega \to \mathbb{R}$に対して $h = \sum_{k=1}^n f_k$は凸である.

証明¶

任意の$a \in (0,1)$と$x,y \in \Omega$を取る. このとき \begin{align} f(ax + (1-a)y) &= \sum_{k=1}^n f_k(ax + (1-a)y) \leq \sum_{k=1}^n (af_k(x) + (1-a) f_k(y)) \ &= ah(x) + (1-a)h(y) \end{align} が成り立つ.

凸関数族の下限は凸とは限らない¶

一般には成り立ちません. 具体的には$f(x) = x^2$, $g(x) = (x-1)^2$として $h = \min (f,g)$が反例です.

具体的な計算が面倒なので数値計算でさぼりました. 凸でないことは次のリンク先のグラフを見てください.

• gist, calc.ipynb

線型写像の場合の事例¶

このツイートで次の問題が出ています.

問題¶

以下で定義される関数 $f \colon \mathbb{R}^n \to \mathbb{R}$は凸関数か. \begin{align} f(x) = \sum_{i=1}^n \min (x_i, (Ax + b)_i). \end{align} 先の凸関数の一般論が使えないのは明らかですが, 線型写像なのでうまいこと嫌な現象をくぐり抜ける可能性があります. しかし一般には偽です. 反例を構成しましょう.

反例の構成¶

一次元で $A = -1$, $b = 0$としよう. このとき$f$は次のように書ける. \begin{align} f(x) = \begin{cases} x, & x \leq 0, \ -x, & x > 0. \end{cases} \end{align} これは凹関数(上に凸)である.

念のため確認しておくと $g(x) = \max (x, -x)$に対して \begin{align} g(x) = \begin{cases} -x, & x \leq 0, \ x, & x > 0 \end{cases} \end{align} で確かに凸である.

注意¶

まだきちんと議論を詰められていないため予想ではありますが, $A > 0$とすると$f$は凸であり, $A$が成分を正とする対角行列ならやはり凸なので, 一般次元でも行列$A$が(半)正定値性や強連結性(エルゴード性)のような強い性質を持つなら, 問題の$f$は凸になる可能性があります.