ヘッセ行列による凸性の判定

多変数関数のヘッセ行列 $\nabla^{2} f$ を求め、凸集合上のすべての点で半正定値になるか（主小行列式・固有値で）を調べて凸性を判定できる。定数や領域の端 $c$ を含む場合には、凸となる定数の範囲（例: $a$ の最大値、 $c$ の最小値）を求められる

前提

凸集合と凸関数の定義（大学数学最適化・線形計画法）
偏微分と全微分（大学数学微分積分）
2 次形式の標準形と符号（大学数学線形代数）

この技能までの道筋（74 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
凸集合と凸関数の定義（大学数学最適化・線形計画法）
合成関数の微分（数学III 微分法）
偏微分と全微分（大学数学微分積分）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
内積空間とグラム・シュミットの直交化（大学数学線形代数）
対称行列の直交対角化（大学数学線形代数）
2 次形式の標準形と符号（大学数学線形代数）

説明

多変数関数 $f$ が凸かどうかを、定義の不等式を直接扱わずに判定する方法です。2 階偏導関数を並べたヘッセ行列 $\nabla^{2} f$ を作り、それが領域のすべての点で半正定値かどうかを調べます。半正定値かどうかは、固有値の符号か主小行列式の符号で確かめます。式に定数 $a$ が含まれるときや、領域の端 $c$ が動くときには、凸になるための定数の範囲（ $a$ の最大値、 $c$ の最小値など）も求められます。

なぜそうしてよいのか

以下、 $D \subset R^{n}$ は開凸集合とします。開集合とは、各点のまわりに小さな球がまるごと含まれる集合のことです。また $f$ は $C^{2}$ 級、つまり 2 階偏導関数がすべて存在して連続であるとします。このとき偏微分の順序を交換できるので、ヘッセ行列 $\nabla^{2} f = (\frac{\partial ^{2} f}{\partial x _{i} \partial x _{j}})_{i, j}$ は対称行列です。

凸性の定義の不等式に出てくるのは、2 点 $p, q$ を結ぶ線分上の値だけです。そこで点 $p \in D$ と方向 $v$ を固定し、直線に制限した 1 変数関数 $g (t) = f (p + t v)$ を考えます（ $t$ は $p + t v \in D$ となる区間を動きます）。 $v = q - p$ 、 $t \in [0, 1]$ とすれば定義の不等式そのものになるので、「 $f$ が凸」と「すべての $p, v$ について $g$ が凸」は同じことです。連鎖律より $g^{'} (t) = \sum_{i} v_{i} f_{x_{i}} (p + t v)$ で、もう一度微分すると
$g^{''} (t) = i, j \sum v_{i} v_{j} f_{x_{i} x_{j}} (p + t v) = v^{T} \nabla^{2} f (p + t v) v$
となります。1 変数では「区間で $g^{''} \geq 0$ ⇔ 凸」でした。よって、すべての $x \in D$ とすべての $v$ で $v^{T} \nabla^{2} f (x) v \geq 0$ 、つまり $\nabla^{2} f (x)$ が半正定値なら $f$ は凸です。逆に、ある点 $x_{0}$ で $v^{T} \nabla^{2} f (x_{0}) v < 0$ となる $v$ があるとします。2 階偏導関数は連続なので、 $x_{0}$ の近くの $t$ でも $g^{''} (t) < 0$ です。 $g$ はそこで凸でないので、 $f$ も凸ではありません。まとめると、 $D$ 上で $f$ が凸 ⇔ $D$ のすべての点で $\nabla^{2} f$ が半正定値、が成り立ちます。

半正定値かどうかは、2 次形式の符号として調べます。対称行列 $H$ を直交行列 $P$ で対角化し、 $w = P^{T} v$ とおくと $v^{T} H v = \sum λ_{i} w_{i}^{2}$ になります。したがって、半正定値 ⇔ 固有値がすべて $\geq 0$ です。同じ番号の行と列を選んで作る小行列式を主小行列式といいます。 $2 \times 2$ の $H = (a b b c)$ では、主小行列式は $a, c, a c - b^{2}$ の 3 つで、「半正定値 ⇔ $a \geq 0, c \geq 0, a c - b^{2} \geq 0$ 」が次のように示せます。固有方程式は $λ^{2} - (a + c) λ + (a c - b^{2}) = 0$ で、 $H$ は対称なので 2 つの固有値 $λ_{1}, λ_{2}$ は実数です。解と係数の関係から、 $λ_{1} λ_{2} = a c - b^{2} = det H$ 、 $λ_{1} + λ_{2} = a + c$ です。(⇒) 半正定値なら $a = e_{1}^{T} H e_{1} \geq 0$ 、 $c = e_{2}^{T} H e_{2} \geq 0$ で、 $det H = λ_{1} λ_{2} \geq 0$ です。(⇐) $det H > 0$ の場合を考えます。このとき $a c > b^{2} \geq 0$ なので $a, c > 0$ です。2 つの固有値は同符号で、和 $a + c > 0$ なのでともに正です。 $det H = 0$ の場合は、一方の固有値が $0$ で、もう一方は $a + c \geq 0$ です。どちらの場合も固有値はすべて $\geq 0$ となります。一般の $n$ 次対称行列でも「半正定値 ⇔ すべての主小行列式が $\geq 0$ 」が成り立ちますが、ここではこれを定理として使います。

手順

領域 $D$ が開凸集合であること、 $f$ が $C^{2}$ 級であることを確認する。
2 階偏導関数をすべて求め、ヘッセ行列 $\nabla^{2} f (x) = (f_{x_{i} x_{j}} (x))$ を作る（対称行列になる）。
半正定値の条件を書く。固有値がすべて $\geq 0$ 、またはすべての主小行列式が $\geq 0$ のどちらかを使う。2 変数なら $f_{xx} \geq 0, f_{y y} \geq 0, f_{xx} f_{y y} - f_{x y}^{2} \geq 0$ の 3 つ。
その条件が $D$ のすべての点 $x$ で成り立つかを調べる。 $x$ を動かしたときの最小値で考えるとよい。
定数 $a$ や端 $c$ を含む場合は、「すべての $x \in D$ で条件が成立」を $a$ （または $c$ ）の不等式に直し、その範囲から最大値・最小値を読み取る。

例題

実数の定数 $a$ に対し $f (x, y) = x^{2} + a x y + 4 y^{2} + y^{4}$ とする。 $f$ が $R^{2}$ 全体で凸関数となるような $a$ の最大値を求めよ。

例題の解答

手順 1： $R^{2}$ は開凸集合であり、 $f$ は多項式なので $C^{2}$ 級である。

手順 2： $f_{x} = 2 x + a y$ 、 $f_{y} = a x + 8 y + 4 y^{3}$ である。よって $f_{xx} = 2$ 、 $f_{x y} = f_{y x} = a$ 、 $f_{y y} = 8 + 12 y^{2}$ となり、
$\nabla^{2} f = (2 a a 8 + 12 y^{2}) .$

手順 3：半正定値の条件は次の 3 つである。 $2 \geq 0$ 、 $8 + 12 y^{2} \geq 0$ 、 $det = 2 (8 + 12 y^{2}) - a^{2} = 16 + 24 y^{2} - a^{2} \geq 0$ 。

手順 4：はじめの 2 つはつねに成り立つ。3 つ目の $16 + 24 y^{2} - a^{2}$ は $y = 0$ で最小値 $16 - a^{2}$ をとる。したがって、すべての $(x, y)$ で条件が成り立つ ⇔ $16 - a^{2} \geq 0$ である。

手順 5： $a^{2} \leq 16$ 、すなわち $- 4 \leq a \leq 4$ のとき $f$ は凸になる。 $∣ a ∣ > 4$ なら点 $(0, 0)$ で行列式が負になり、半正定値でないので凸ではない。よって $a$ の最大値は $4$ である。

答え: $4$

よくある誤り

半正定値の判定を、左上から順に取る小行列式（首座小行列式）だけで済ませてしまう誤り。たとえば $H = (00 0 - 1)$ の首座小行列式は $0, 0$ でともに $\geq 0$ だが、 $v = (0, 1)$ で $v^{T} H v = - 1 < 0$ となり、半正定値ではない。正しくは、 $f_{y y}$ のような対角成分も含めて、すべての主小行列式が $\geq 0$ であることを確かめる。
ある 1 点（たとえば $y = 1$ の点）だけでヘッセ行列を調べてしまう誤り。例題で $y = 1$ だけを見ると $det = 40 - a^{2}$ となり、誤って $a \leq 40$ と答えてしまう。正しくは、領域のすべての点で調べる。例題では $y$ を動かしたときの最小値 $16 - a^{2}$ （ $y = 0$ のとき）で判定し、 $a \leq 4$ となる。
凸の条件を正定値（ $v \neq = 0$ で $v^{T} H v > 0$ ）と取り違える誤り。例題で $a^{2} < 16$ として $a = 4$ を除外してしまう。凸性に必要十分なのは半正定値（ $\geq 0$ ）なので、 $a = 4$ も含まれる。なお、正定値は狭義凸の十分条件にすぎない。 $f (x, y) = x^{4} + y^{4}$ は狭義凸だが、原点でのヘッセ行列は零行列である。
領域を確認せずに判定してしまう誤り。たとえば $f (x, y) = x^{3} + y^{2}$ は $\nabla^{2} f = (6 x 0 02)$ なので、 $x > 0$ の開凸集合では凸だが、 $R^{2}$ 全体では凸ではない。また、領域が凸集合でなければ、凸関数の定義そのものが使えない。正しくは、まず領域が凸集合であることを確認し、その領域の点だけでヘッセ行列の符号を調べる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

凸計画と KKT 条件の十分性（大学数学最適化・線形計画法）