一変数関数、多変数関数の凸性を求める方法

機械学習の教科書「言語処理のための機械学習入門 (自然言語処理シリーズ) 」を再び読み始めました。勉強したことを忘れないように、メモがてらなにか書いていこうと思います。

今回は関数の凸性、つまりある関数が上に凸か、下に凸か、もしくはそのどちらでもないかを判定する方法についてメモします。

1変数関数の場合

$y = f(x)$ が上に凸か下に凸かは、 $f(x)$ の2階微分を見れば分かります。すなわち、

$f(x)$ は下に凸ならば、 $f''(x)$ が常に0以上
$f(x)$ は上に凸ならば、 $f''(x)$ が常に0以下

例をあげると、

f(x)	f''(x)	凸性
$x^2$	$2$	下に凸
$-x^2$	$-2$	上に凸
$3x^2 + x^4$	$6 + 12x^2$	下に凸
$5$	$0$	上にも下にも凸
$x^3$	$6x$	どちらでもない？（たぶん…）

これは高校数学でも習う話で、絵を書けば納得できます。

多変数関数の場合

$f(x_1, x_2) = 3x_1^2 + 2x_2^2 + x_1x_2$ などのような多変数関数の場合は、ヘッセ行列を使って凸性を判定します。ヘッセ行列とは、(i,j)成分は $\frac{\partial^2 f}{\partial x_1}{\partial x_2}$ で表される行列です。

さきほどの関数のヘッセ行列は以下のようになります。（はてなブログの制約により行列を表示できないので、苦肉の策で以下のように書いています。行列だと思って読み替えてください） 6 1 1 4

ヘッセ行列を使うと、多変数関数の凸性が以下のように判定できます。

ヘッセ行列が半正定値（＝行列のすべての固有値が0以上） ⇔ 関数は下に凸
ヘッセ行列が半負定値（＝行列のすべての固有値が0以下） ⇔ 関数は上に凸

さきほどのヘッセ行列の固有値は $5 \pm \sqrt{2}$ で全部0以上なので、 $f(x_1, x_2) = 3x_1^2 + 2x_2^2 + x_1x_2$ は下に凸だと分かります。Googleのグラフ機能を使ってグラフを確認できます。 3xx + 2yy + x*y - Google 検索

他の関数でも試してみると以下のようになります。行列はOctave記法で表しています。

f	ヘッセ行列	ヘッセ行列の固有値	凸性
$x^2 + y^2$	[2 0; 0 2]	2(重解)	下に凸
$-x^2 -y^2$	[-2 0; 0 -2]	-2(重解)	下に凸
$x^2 -y^2$	[2 0; 0 -2]	2, -2	どちらでもない？（たぶん…）
$3x^2 + y^2 + 5xy$	[6 5; 5 2]	$4 \pm \sqrt{29}$	どちらでもない？（たぶん…）

Googleのグラフも貼っておきます。