非線形最適化

ここでは変数 $\boldsymbol{x}$ の関数 $e(\boldsymbol{x})$ が与えられた時に、その値を最小(または最大)にする $\boldsymbol{x}^*$ を求める事を考える。

で、 $e$ が $\boldsymbol{x}$ の2次式以上になると非線形という。たぶん。

最適化問題にはよく $x_1 > 0$ とか条件が付いてくるけど、難しいので考えない。そういう問題を解く必要に迫られた人は「(非)線形計画問題」でググるといいかも。 $|\boldsymbol{x}| = 1$ 的な等式の条件ならラグランジュの未定定数だか何だかで、どうにかなるらしい。

要するに、関数が一つ与えられて、「この関数の最小値(とその時の $\boldsymbol{x}^*$ )はいくつでしょう？」という問題しか扱いませんよ、という話。

基本方針

2次や3次の方程式には解の公式ってのがあるけどその他はよく分からないので、「いま分かっている値よりいいものを探す」というのを繰り返す、繰り返し計算になる。当然、極値を求めているだけなので他にもっといい点がある可能性が存在する。なので、できるだけ極値が少ない(≒次数が低い)関数を使って、できるだけよい初期値から始めたり複数の初期値を使ったりする必要がある。処理の流れをざっくり書くと、こんな感じ。

初期値を決める(大抵、線形解法・近似解法の解)
評価する点を決める
評価して良ければ値を更新
改善の見込みが無くなれば終了。そうで無ければ2に戻る

次に評価する点をいかに効率よく探すかがポイント。

関数の値しか分からない場合

まずは $\boldsymbol{x}$ が与えられた時に $e(\boldsymbol{x})$ の値しか計算できない場合。つまり、次にどっちへいけば値が良くなるか分からない状態。

シンプレックス法

たぶん、定番の方法。線形計画問題に出てくるシンプレックス法とは無関係。

Differential Evolution

GAっぽい感じ。こんなのもあるのかぁ。ただ、いつ終わればいいかが分からない。。

関数が不連続でもよい
取り敢えず試せる
関数の評価を沢山やる必要がある

1回微分が分かる場合

最急降下法

$e(\boldsymbol{x})$ の微分 $\nabla e(\boldsymbol{x})$ は値が大きくなる方向なので、極小値を求めているなら反対方向に動かせば良い。

$\begin{array}{l} \boldsymbol{x}^{(i+1)} = \boldsymbol{x}^{(i)} + \boldsymbol{r} \\ r = - \lambda \nabla e(\boldsymbol{x}^{(i)}) \end{array}$

$\lambda (> 0)$ は適当に決める。 $-\nabla e$ に沿って動かしてみて値が小さくなる(大きくなる)ところを選べばいいかも。

どっちに進めばいいか分かるので安心
極値なら $\lambda e(\boldsymbol{x}) = 0$
あまり大きく動かせない

2回微分まで分かる場合

(ガウス・)ニュートン法

$\boldsymbol{x}$ の近くでは、更新量 $\boldsymbol{r}$ に対して以下の近似が成り立つ。

$\begin{array}{l} \nabla e(\boldsymbol{x} + \boldsymbol{r}) = \nabla e(\boldsymbol{x}) + H \boldsymbol{r} \\ H = (h_{ij}) = \frac{\partial^2}{\partial x_i \partial x_j} e \end{array}$

で、極値だと $\nabla e(\boldsymbol{x} + \boldsymbol{r}) = 0$ になるので、

$\boldsymbol{r} = - H^{-1} \nabla e(\boldsymbol{x})$

となる。

関数が二次関数でうまく近似できる時は、メチャ速
運が悪いと解が振動する

レベンバーグ・マーカート法

よく忘れるので英語表記も書いておく。Levenberg-Marquardt・・・で合ってると思う。元ネタを読んだ事が無いので、雰囲気だけ。

最急降下法とニュートン法を足して2で割ったような感じ：

$\left(H - \lambda I \right) \boldsymbol{r} = -\nabla e(\boldsymbol{x})$

更新がうまくいった時は $\lambda$ を小さくしてニュートン法に近づけて、ダメな場合は大きくして最急降下法に近づける。非線形最適化といえば、まずコレをやっておけば問題ない・・・気がする。

で、よく使う最小二乗法を考える。

$e(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{f}(\boldsymbol{x})^\text{T} \boldsymbol{f}(\boldsymbol{x})$

このとき、

$\begin{array}{l} \nabla e = (\nabla \boldsymbol{f})^\text{T} \boldsymbol{f} \\ H = (\nabla \boldsymbol{f})^\text{T} (\nabla \boldsymbol{f}) + \left( \frac{\partial^2}{\partial^2 \boldsymbol{x}} \boldsymbol{f} \right) \boldsymbol{f} \approx (\nabla \boldsymbol{f})^\text{T} (\nabla \boldsymbol{f}) \end{array}$

更新量：

$\left( (\nabla \boldsymbol{f})^\text{T} (\nabla \boldsymbol{f}) - \lambda I \right) \boldsymbol{r} = - (\nabla \boldsymbol{f})^\text{T} \boldsymbol{f}$

なので、 $\boldsymbol{f}(\boldsymbol{x}), \nabla \boldsymbol{f}(\boldsymbol{x})$ が分かるだけで計算できる。

また、実際の値の変化と予測を比べる事で2次近似の正否が見積もれる：

$s(\boldsymbol{x}, \boldsymbol{r}) = \frac{e(\boldsymbol{x} + \boldsymbol{r}) - e(\boldsymbol{x})}{(\nabla e(\boldsymbol{x}))^\text{T} \boldsymbol{r}}$

定番の方法
たまにランク落ちする事があるので、うまくやる
$\lambda$ のいい決め方があるらしい
ちゃんと考えてプログラムしないとグチャグチャに