Definition: 凸関数 (Convex function)
関数\(f:\mathbb{R}^p\to\mathbb{R}\)が、凸な領域\(D\subseteq\mathbb{R}^p\)において凸関数であるとは、任意の\(x,y\in D\)について次が成立することをいう。
\[ \forall \lambda\in[0,1],\quad f((1-\lambda)x+\lambda y)\le(1-\lambda)f(x)+\lambda f(y)\]
いま\(x,y\)はベクトルだけども細字なことに注意。1次元の場合を図で示すと次のようになる。
赤が対象としている関数\(f\)の曲線、青は\(x\)と\(y\)の点をつなぐ直線。どんな\(x,y\)をとってもその内分点が関数値よりも大きいということです(逆に外分点は小さいといえる)。いまは関数が微分可能(なめらか)である必要は無いのであえて微分不可能な点も書いている。
次に、凸な領域とは、領域内の点集合が凸集合であること。すなわち\(x,y\in D\) \(\Rightarrow\) \(\forall\lambda\in[0,1]\) \(\lambda x+(1-\lambda)y\in D\)が成立すること。あたりまえだけど要素間に普通の線形演算が定義されるような集合じゃないと凸集合は定義できなそうだよね。
連続微分可能な凸関数について (Continuously differentiable)
関数\(f\)が連続微分可能（1階導関数が存在して連続）で、任意の\(x,y\in D\)について次が成立していれば関数\(f\)は領域\(D\)において凸関数。
\[ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle\]
場合によっては連続微分可能な関数が凸であるという定義にこの性質を用いることもある。この性質は図的には次のように理解できる。
証明 (Proof)
簡単のためにまずは\(p=1\)を考える（つまり\(x,y\)はベクトルではなくただの数)。凸関数の定義より、
\[ \begin{align} f(x+\lambda(y-x)) &\le f(x)+\lambda(f(y)-f(x))\\ f(x+\lambda(y-x))-f(x) &\le\lambda(f(y)-f(x))\\ \frac{f(x+\lambda(y-x))-f(x)}{\lambda(y-x)} &\le\frac{f(y)-f(x)}{y-x}\\ f(x)+\frac{f(x+\lambda(y-x))-f(x)}{\lambda(y-x)}(y-x)&\le f(y) \end{align}\]
がわかる。ちなみに、(1)\(\lambda\)でくくる、(2)\(f(x)\)を移項する、(3)両辺\(\lambda(y-x)\)で割る(一般性を失わずに\(y\gt x\)とする)、(4)もっかい\(y-x\)掛けて移項する。ややまわりくどいか？これが思いつかなければ図から式を立てて逆に凸関数の定義にもっていけばいい。
\(p=1\)はこれでほとんど終わり。微分の定義\(f'(x)=\lim_{t\to 0}(f(x+t)-f(x))/t\)より、この式において\(\lambda(y-x)=t\)とおいて\(\lambda\to 0\)を考えれば\(t\to 0\)より左辺第1項の分数は\(f'(x)\)になるはずなので
\[ f(y)\ge f(x)+f'(x)(y-x)\]
がわかった。このアナロジーにより\(p>1\)の場合におけるもとの式が成り立つことも予想できます。一応、あらかじめ内積のところを書き下しておくと、
\[ \nabla f(x)=\left(\begin{matrix} \frac{\partial f(x)}{\partial x_1}\\ \vdots\\ \frac{\partial f(x)}{\partial x_p}\\ \end{matrix} \right)\]
なので、右辺第2項を書き下すと次のようになります。
\[ \langle \nabla f(x),y-x\rangle =\sum_{i=1}^p\frac{\partial f(x)}{\partial x_i}(y_i-x_i)\]
ついでに、
\[ \begin{align} \frac{\partial f(x)}{\partial x_i} &=\lim_{t\to 0}\frac{f(x+tx_i)-f(x)}{t|x_i|}\\ &=\lim_{t\to 0}\frac{f(x)-f(x-tx_i)}{t|x_i|} \end{align}\]
前からいくやつと後ろからいくやつがあります。ここで、\(x_i\)は\(i\)番目の要素が\(x\)の\(i\)番目の要素、それ以外の要素はゼロのベクトルのことを表すことにします。これはここでのみ使う書き方、かつ最初の方の書き下しには適用されない表記なので注意してください(ベクトルに足したり引いたりしていて下付き\(i\)があればこういう意味になる)。書きやすさのためです。ゼロでない要素が1つのベクトルなので\(|x_i|\)はその要素の値そのものになります。記号が\(y\)に代わっても下付きの\(i\)があれば意味は同じです。念のために書き下しておくと、
\[ \begin{align} x_1&=(x_1,0,0,\dots,0)^\top\\ x_2&=(0,x_2,0,\dots,0)^\top\\ &\vdots\\ x_p&=(0,\dots,0,0,x_p)^\top\\ \end{align}\]
です。
\[ x=\sum_{i=1}^px_i\]
が容易にわかるとおもいます。いちいち書きませんがこれを浮かべないと厳しいので適宜イメージしましょう。
だらだらと書きましたが、言いたいことはこの偏微分の定義式の形に凸関数の定義式を変形していって\(\lambda\to 0\)とすればよいわけです。途中までは\(p=1\)と同じようにできます。
\[ f(y)\ge f(x)+\frac1\lambda \{f(x+\lambda(y-x))-f(x) \}\]
\(p=1\)と違ってベクトルで割るということはできません。\(\lambda\)では割れます。ここからは右辺第2項に注目します。例によって間に\(f(x+\lambda(y-x)-(y_1-x_1))=f_1\)を引いて足します。(長いのでこれを\(f_1\)とおきます、想像で見ましょう)
\[ \frac1\lambda\{f(x+\lambda(y-x))-f_1+f_1-f(x)\}\\ =\frac{f(x+\lambda(y-x))-f_1}{\lambda|y_1-x_1|}|y_1-x_1|\\ +\frac1\lambda\{f_1-f(x)\}\]
これで\(x_1\)についての微分の項が出ました。次も同じです。\(f(x+\lambda(y-x)-(y_1-x_1)-(y_2-x_2))=f_2\)を足して引いて同じようにやると\(x_2\)についての項が出せます。これを繰り返すと
\[ \sum_{i=1}^p \frac{f(x+\lambda(y-x)-\sum_{j=1}^{i-1}(y_j-x_j)) -f(x+\lambda(y-x)-\sum_{j=1}^{i}(y_j-x_j))} {\lambda|y_i-x_i|}|y_i-x_i|\]
になることがわかります。よくみると\(i-1\)まで引いてるところと\(i\)まで引いているところで偏微分の形が生まれています。両方から同じ量を引いても偏微分には影響しません。同様に\(\lambda\to 0\)とすれば次が示せて完了です。
\[ =\sum_{i=1}^p\frac{\partial f(x)}{\partial x_i}|y_i-x_i|\]
余談
一見してテイラー展開の形だがそれは考えなくていい。冷静に途中のベクトル表記わかりにくすぎるな。