数理最適化の勉強メモ − 解析的な解法 / 最適性条件 / 勾配法がうまくいかない条件

今回から何回かに分けて数理最適化の勉強メモを公開してみます。

初回である今回の記事では、数理最適化の基本である連続最適化問題を解析的に解く方法、最適性条件、勾配法による最適化がうまくいかない条件などについて考えたことをまとめています。

※ 2019/09/22 : あまりに長かったため2記事に分割しました。最急降下法とニュートン法の解説は以下の記事に移っています。

kamino.hatenablog.com

はじめに

コンピュータビジョンの分野の勉強をしていると色々な場面で数理最適化のお世話になります。以前の記事で紹介したカメラキャリブレーションもそうですし、同様にBundle Adjustmentを利用するSLAM、高次元データを簡潔に記述する圧縮センシング、複雑なモデル関数で事象を表現しようと試みる深層学習など、様々な場面で数理最適化の概念が利用されています。

もちろんCV分野以外でもロケットの最適制御、ナビの経路選択、工場から店舗までの最大輸送問題、ネットワークの負荷分散などあちこちで最適化の概念は利用されています。

この記事では、そうした数理最適化の理論を理解する上で重要な解析的に解く方法と最適性条件について勉強したことをまとめてみます。

なお筆者はコンピュータビジョンが専門で、数学や数値計算の専門家ではありません。間違いがある可能性が割と高いので、お気づきの際には知らせていただけると幸いです。

1. この記事で扱う最適化問題

今回の記事では数理最適化の分野の中でも制約なし連続最適化問題（unconstrained continuous optimization）と呼ばれる問題を解くことを目標とします。

数理最適化は、究極的には「ある関数 $f(\mathbf{x}) \ : \ \mathbb{R} ^ n \rightarrow \mathbb{R}$ が最小（もしくは最大）になるような $\mathbf{x}$ を探すこと」を目的とした分野ですが、問題設定によって多くの派生分野が存在します。以下はその一部です。

離散最適化（組合せ最適化）
- $\mathbf{x}$ が $x _ 1 = 0, 1, 2, \cdots$ のように離散値を取る状況で最適解を求める
制約あり最適化
- $\mathbf{x} = [x _ 1, x _ 2, \cdots] ^ \mathrm{T}$ に対して $x _ 1 > 0$ , $x _ 1 + x _ 2 = 5$ などの条件を課した上で最適解を求める
線形最適化（線形計画問題）
- $f(\mathbf{x})$ が $\mathbf{x}$ の線形関数である制約付き最適化問題を解く
多目的最適化
- 複数の目的関数 $f _ 1(\mathbf{x}), \ f _ 2(\mathbf{x}), \ \cdots$ がある状況で最適な $\mathbf{x}$ を求める
大域的最適化
- 凹凸が激しい目的関数 $f(\mathbf{x})$ において最も値が低く（もしくは高く）なるような $\mathbf{x}$ を求める

それぞれの派生分野では、問題の性質に応じた異なるアプローチが研究されています。特に離散最適化と連続最適化では根本にある考え方がガラリと変わるため、ほぼ別分野と言ってもいいほどです。

そんな中で今回は次のような問題に的を絞って考えます。

連続最適化
- パラメータ $\mathbf{x}$ は連続値を取るベクトル
制約なし最適化
- $\mathbf{x}$ に関する制約条件はなし
非線形最適化
- 目的関数 $f(\mathbf{x})$ は非線形関数
多目的最適化ではない
- 目的関数は1つだけ
局所的最適化
- ある点の近くで最も $f(\mathbf{x})$ が小さく（もしくは大きく）なる $\mathbf{x}$ を探す
- （あらゆる $\mathbf{x}$ の中での最適解を求めることはとりあえず諦める）

1〜4の条件を満たす問題は一般に「制約なし連続最適化問題」などと呼ばれます。これを数学っぽく定式化すると以下のようになります。

$\mathbf{x}^* = \mathrm{minarg} _ {\mathbf{x}} \ f(\mathbf{x}) \\ \mathbf{x} \in \mathbb{R} ^ n, \ \ f : \mathbb{R} ^ n \rightarrow \mathbb{R}$

文にすれば「 $n$ 次元のベクトル $\mathbf{x}$ のスカラー関数 $f(\mathbf{x})$ が最小値を取るような $\mathbf{x}^*$ を求めよ」となります。 $g(\mathbf{x})$ の最大化は $-g(\mathbf{x})$ の最小化と同じことなので、この分野ではすべて最小化問題として定式化することになっています。

また5の条件の通り、局所的最適解（local minimizer）を求めることに的を絞ります。

局所的最適解とは、パラメータ $\mathbf{x}$ に対する目的関数 $f(\mathbf{x})$ のグラフを描いたとき谷の底になっている部分、つまり目的関数の値が近傍よりも小さくなっている領域のことをいいます。一方、対象領域の中で目的関数 $f(\mathbf{x})$ が最も小さい値を取る領域、つまり局所的最適解の中でも最も値が小さい解は大域的最適解（global minimizer）と呼ばれます。

制約なし連続最適化問題の局所的最適解を求めるアルゴリズムは、すべての連続最適化の手法の基礎となります。制約あり最適化や大域的最適化を考えるときもこの考え方から派生させていくことになるため、まずはこの解法をしっかり抑えるべきです。

2. 解析的な解法の例

コンピュータサイエンスを勉強している人にとっては「最適化問題＝コンピュータに解かせるもの」というイメージが先行するかもしれませんが、簡単な形の目的関数が相手であれば解析的に最適解を求めることができます。

この章では最適解を解析的に求める方法をおさらいしておきます。雰囲気としてはセンター数学Ⅱによく出題されていた最大値・最小値を求める問題を多変数関数に拡張したような感じです。

2.1. 問題設定

例として2変数関数 $f(x, y) = x ^ 4 -4x ^ 3 -14x ^ 2 + 12xy + 6y ^ 2$ について考えてみます。知りたい最適解はこの関数の値が局所的に最も低くなっているような点です。

2.2. 1階導関数に関する条件

まず $f(\mathbf{x})$ が $C ^ 2$ 級（2回連続微分可能）なので、1階微分と2階微分が定義できることがわかります（定義できないときの話は次の章で触れます）。

次に谷底の部分の性質を考えてみると $x$ 方向と $y$ 方向ともに傾きが軸と平行、つまり微分値が $0$ であるはずだということに気付きます。このように勾配が $0$ になる点のことを停留点（stationary point）と呼びます。最適解は停留点の性質を満たすはずです。

そこで目的関数の1階導関数（勾配ベクトル）を計算してみます。

$\begin{bmatrix} f' _ x \\ f' _ y\end{bmatrix} = \begin{bmatrix} 4x ^ 3-12x ^ 2-28x+12y \\ 12y + 12 x\end{bmatrix}$

これがゼロベクトルになるような点を求めると $(x,y) = (0, 0), (5, -5), (-2, 2)$ の3組が停留点であるとわかります。

f:id:kamino-dev:20190917110255p:plain:w700 — 停留点をプロットした様子

3Dグラフはこちら : https://kamino410.github.io/cv-snippets/optmz_blog/stat_points.html

ところがグラフにプロットしてみると、目的の谷底の部分に当たるのは $(5, -5), (-2, 2)$ だけで、 $(0,0)$ は求めている答えでないことがわかります。

実は単に停留点を求めた場合、そこには極小点の他に極大点と鞍点（saddle point）が含まれます。

極大点は文字通り、目的関数を最大化するような点のことです。鞍点は、馬の鞍の頂点のように、ある方向から見れば極大点、別の方向からみれば極小点になっているような点のことです。今回の $(0, 0)$ は鞍点に相当します。

2.3. 2階導関数に関する条件

そこで今度は求めた停留点の中から極小点だけを選び出す方法について考えます。

極小点/極大点/鞍点を区別するための手立てとして2階微分の情報を利用する方法があります。グラフ上をある一定方向に辿ったとき、勾配がマイナス → $0$ → プラスの順に変化していれば、つまり2階微分が正であるなら、（その方向に見たときには）その場所は谷になっているといえます。ということはあらゆる方向に2階微分を計算してそれが正になるなら、その場所はどの方向から見ても谷になっているとわかります。

あらゆる方向の2階微分が正であることは、ヘッセ行列 $\mathrm{H} = \nabla ^ 2 f(\mathbf{x})$ が正定値行列であることと同値であると証明できます。またある行列が正定値行列であることは固有値がすべて正であることと同値です。つまりヘッセ行列の固有値がすべて正であるような点は極小点であることがわかります。

そこで先ほど求めた3つの停留点それぞれのヘッセ行列とその固有値を計算してみます。ヘッセ行列は

$\begin{bmatrix}12x ^ 2 - 24x-28 & 12 \\ 12 & 12 \end{bmatrix}$

ですので、各停留点における特性方程式と固有値は

	特性方程式	固有値
$(0, 0)$	$\lambda ^ 2+4\lambda-30 = 0$	$-2\pm\sqrt{34}$
$(5, -5)$	$\lambda ^ 2-41\lambda+105$	$41/2 \pm \sqrt{1261}/2$
$(-2, 2)$	$\lambda ^ 2-20\lambda+42$	$10 \pm \sqrt{58}$

となります。

$(0,0)$ は $-2 - \sqrt{34} \lt 0$ であるため正定値行列ではないことがわかります。 $(5, -5), (-2, 2)$ の2つは両方の固有値が正なので極小点すなわち局所的最適解であることがわかります。 $f(5, -5) = -375$ , $f(-2, 2) = -32$ なので、目的関数 $f(x,y)$ の大域的最適解は $(5, -5)$ です。

以上のように、

勾配ベクトルが $0$ である
ヘッセ行列が正定値行列である

という2つの条件を活用することで解析的に局所的最適解を求めることができました。

3. 最適性条件

前章では目的関数を解析的に見ていくことで局所的最適解を求めました。しかし実際に数値最適化で扱うような目的関数は解析的に解を求められない複雑な関数であることがほとんどです。そこでコンピュータに計算させることで近似的な最適解を求める方向へと話が進んでいくわけです。

先ほど紹介した「ある $\mathbf{x}$ が局所的最適解であるための条件」は計算機向けのアルゴリズムの中でも活用されています。これらの条件は最適性条件と呼ばれています。

コンピュータ向けのアルゴリズムの話に入る前に、この章ではもう一度、数学的に厳密に最適性条件の内容を確認しておきます。

3.1. 局所的最適解の定義

まず局所的最適解の数学的定義を確認しておきます。結局のところ「ある点の関数値が近傍の点の関数値以下である」というだけの定義ですが、数学的に書くと以下のようになります。

$\|\mathbf{p}\| \leq \varepsilon$ を満たす任意の $\mathbf{p}$ について $f(\mathbf{x} ^ *) \leq f(\mathbf{x} ^ *+\mathbf{p})$ が成り立つような $\varepsilon > 0$ が存在する
⇒ $\mathbf{x} ^ *$ は局所的最適解である

3.2. 1次の必要条件

さて、先ほどお話した「最適解は停留点の性質を満たすはずだ」という条件を厳密に記述すると以下のようになります。

$\mathbf{x} ^ *$ が制約なし最小化問題の局所的最適解かつ、目的関数 $f(\mathbf{x})$ が $\mathbf{x} ^ *$ の開近傍で連続微分可能である
⇒ 勾配ベクトルが $\nabla f(\mathbf{x} ^ *) = 0$ となる

これはテイラーの定理を使えば証明できます。

ここで、この定理は局所的最適解であるための必要条件を示しているという点に注意しなければなりません。つまり「勾配ベクトルが $0$ になっても局所的最適解とは限らない（極大点や鞍点も含まれるから）」また「目的関数 $f(\mathbf{x})$ が $\mathbf{x} ^ *$ の開近傍で連続微分可能でないなら、 $\nabla f(\mathbf{x} ^ *) = 0$ でない点でも局所的最適解になりうる」という落とし穴があります。

前者については先ほど説明したとおり、2次の条件を使って極大点や鞍点を排除する方向で対処します。一方、後者は目的関数が不連続な関数であるときや、1階導関数が不連続な関数であるときに問題になってきます。

たとえば以下の図の左の関数は $x=0$ において開近傍が定義できないため $\nabla f(0) = 0$ を満たしていませんが、明らかに $x = 0$ が最適解です。また右の関数も $x=0$ において左微分係数と右微分係数が異なっている上、共に $\nabla f(\mathbf{x} ^ *) = 0$ を満たしていませんが、 $x = 0$ が最適解です。

f:id:kamino-dev:20190917053603p:plain:w700 — 不連続関数 / 1階導関数が不連続な関数の例

こうした特殊なケースで最適解を求めるためには $\nabla f(\mathbf{x}) = 0$ を満たす点（停留点）を調べるだけでは不十分であり、不連続点も個別に調べる必要があります。

3.3. 2次の必要条件

次にヘッセ行列に関する定理を厳密に記述すると以下のようになります。

$\mathbf{x} ^ *$ が制約なし最小化問題の局所的最適解かつ、目的関数 $f(\mathbf{x})$ が $\mathbf{x} ^ *$ の開近傍で2回連続微分可能である
⇒ ヘッセ行列 $\nabla ^ 2 f(\mathbf{x} ^ *)$ は半正定値行列になる

こちらもテイラーの定理を使えば証明できます。

この定理も局所的最適解であるための必要条件を示しているという点に注意しなければなりません。つまり「2回連続微分できない点でも局所的最適解である可能性がある」「局所的最適解でなくてもヘッセ行列は半正定値になりうる」という落とし穴があります。

また、条件が半正定値行列となっていることにも注意してください。半正定値ということは固有値 $0$ が含まれていても良いということであり、ある方向の2階微分係数が $0$ であってもよい、すなわち目的関数 $f(\mathbf{x})$ の値が変化しない平らな領域の中に位置する点であっても良いということです。

例を示します。たとえば以下の関数では1階導関数は連続で $x \in [0, 1$ ] の閉区間が局所的最適解です。

f:id:kamino-dev:20190917054844p:plain:w500 — 幅を持つ局所的最適解の例

当然、 $x \in [0,1$ ] の閉区間は1次の条件（勾配ベクトルが $0$ ）を満たしています。そのうち開区間 $x \in (0,1)$ は、2階導関数は0（＝1次元のヘッセ行列が半正定値）であり、上の定理を満たしています。また $x = 0, 1$ も2階導関数が不連続になっているため2階微分係数（＝1次元のヘッセ行列）が定義できませんが局所的最適解の一部です。

もうひとつ例を示します。以下の関数では $x \in [0, 1$ ] の閉区間は1次の条件（勾配ベクトルが $0$ ）を満たしており、そのうちの開区間 $x \in (0,1)$ はヘッセ行列が半正定値であるという条件も満たしていますがこれらは明らかに鞍点であり、実際の局所的最適解は $x=2$ です。

f:id:kamino-dev:20190917101629p:plain:w500 — 幅を持つ鞍点の例

このように2階微分が定義できない点が局所的最適解になることもあるほか、関数の中に値が変化しない領域が含まれている場合は「勾配ベクトルが $0$ 」「ヘッセ行列が半正定値である」という条件だけでは局所的最適解でないものがピックアップされてしまう可能性が残るわけです。

3.4. 2次の十分条件

前節で述べたようにヘッセ行列が半正定値であるかだけでは局所的最適解であるかの判別はできませんが、これが厳に正定値であったとすればその点は確実に局所的最適解であると言うことができます。これを表現したのが以下の定理です。

目的関数 $f(\mathbf{x})$ が $\mathbf{x} ^ *$ の開近傍で2回連続微分可能であり、 $\nabla f(\mathbf{x} ^ *) = 0$ かつ $\nabla ^ 2 f(\mathbf{x} ^ *)$ が正定値行列
⇒ $\mathbf{x} ^ *$ は局所的最適解である

「勾配ベクトルが $0$ 」「ヘッセ行列が正定値」という条件では、領域的に広がっている局所的最適解は取りこぼしてしまうのですが、この条件を満たした点は確実に局所的最適解であると断言できます。

3.5. 実際の解法で使われる最適性条件

ここまで見てきたように汎用的な最適性条件を考えることはとても難しい問題です。

しかし上の議論をよく眺めてみると目的関数が「2回連続微分可能であり値が変化しない領域（1階微分係数と2階微分係数が継続的に $0$ になる領域）を持たない関数」であれば「勾配ベクトルが $0$ 」「ヘッセ行列が正定値」の2条件で正確に局所的最適解を判別できる（つまり必要十分条件になっている）ことがわかります。そして都合の良いことに工学分野で表れる多くの目的関数はこの条件を満たします。

よって最急降下法やニュートン法を含む多くの最適化手法では、上のような都合の良い関数を最適化することを前提として

勾配ベクトルが $0$
ヘッセ行列が正定値

の2条件を使って局所的最適解を探索することが多いです。

なお目的関数やその導関数に不連続点を含む関数を最適化したい場合は、不連続点の左右でそれぞれ最適解を求めてそれを比較する、もしくは連続関数で近似するといった工夫を施すことが多いです。ステップ関数をシグモイド関数で近似する話なんかは有名だと思います。

1階導関数や2階導関数が不連続な連続関数については最急降下法で無理やり最適解を求められるケースもありますが、場合によっては収束性が保証されなかったり、最適解でない答えが吐き出されたりします。

4. まとめ

ここまで局所的最適解を判別するための最適性条件について考察してきました。最後に要点をまとめておきます。

目的関数は2回連続微分可能であり、値が変化しない平らな領域（1階微分係数と2階微分係数が継続的に $0$ になる領域）を持たないのが理想的
この条件を満たす関数なら、以下2つの基準を満たすことと局所的最適解であることは同値
- 勾配ベクトルが $0$ であること（ $\nabla f(\mathbf{x} ^ *) = 0$ ）
- ヘッセ行列が正定値であること（ $\nabla ^ 2 f(\mathbf{x} ^ *)$ の固有値がすべて正）
目的関数自体やその導関数に不連続点がある場合、不連続点は上の2つの基準を満たさなくても最適解になることがあるので個別に調べる必要あり
目的関数の値が変化しない領域が存在する場合、それが極小点/極大点/鞍点のどれの集まりであるのかを個別に調べる必要あり