Logo address

多変数関数の最小解

ちょいと訳あって、多変数関数の最小解を求めなくてはならなくなった。

Adaptive Nelder-Mead Method

僕が出会った問題は、あまりにもクセの強い関数なので、コンピュータで、と言うことになる。そのために急遽、最適化問題を研究することになった。いやらしい関数で、僕の知っていた普通の方法では収束しない。つまり求まらない。
そうこうしている間に Nelder-Mead Method が良いらしいことがわかった。
幸い numpy によるコードが誰かが公表していた[2]。
まだ未完成な部分があるが、しかし、そのレベルで試してみると、この方法はなかなか優秀である。この手の問題の現在のスタンダードだと言われる理由がわかる。どうしてこんなにうまく行くの? との理由はまだよくわからない部分があるらしい。

とやかく調べて行くうちに、その改良版の論文が見つかった[1]。次元が高くなると Nelder-Mead Method が遅くなる原因を明らかにし、対策を示したのがこの論文である。著者らは、これを Adaptive Nelder-Mead Method と呼んでいる。そこで提案されたアルゴリズムを numpy で実装することにした。実装するに当たって nykergoto 氏のコードを利用させてもらった。何しろ彼のコードはよくできている。そこで可能な限り彼のコードとコメントを残すことにした。ツールとしては、関数として実装する必要があるので、その部分は追加した。それから元のコードには少し気に入らない部分(分かり難い場合分け)があったので修正した。それから、もちろん、"Adaptive" となるようにコードを追加した。

完成したものを試してみると、確かに素晴らしい。

download nmm.py -- 本体

download nmm_t.py -- 使い方のサンプル

機会があれば、ちゃんとした解説を加えたい。
十分にテストを行ったつもりであるが、まだ問題があれば知らせてもらえれば幸いです。

他にソースコードがどこかにあるかを探したが、見つけるのが難しい。
見つかった唯一のソースコードは、統計ソフト R 用のもので[3]、Python によるコードは見つからない。

ここに公開したコードは、出典が添えられておれば自由に使ってよろし。もちろん責任は負わない。

修正

2020/06/15

バグの修正とコードの追加

Nelder-Mead Method は概して良く働くのであるが、ちゃんとローカルミニマムが求まる保証がない。
Adaptive Nelder-Mead Method についても同様である。
保証がないから使えないかと言えば、そうではない。保証がある関数の条件がはっきりしていないのが問題である。

Gao[1]は "uniformly convex" の条件のもとで収束性を論じている。しかしこの条件は実際のニーズからすればあまりにも強い。そして Gao が扱っているテスト関数の殆どは "convex" の条件すら満たしていない。
つまり Nelder-Mead Method はなぜこんなにうまく働くのは良くわかっていない、適用可能な関数の条件が良くわからないまま使われていると言ってよい。

筆者が扱っている問題(非常に癖の強い関数である)では、あきらかにローカルミニマムでない点を出している。そこで対策を立てた方が良いと考えた。求まった点 \(x\) がローカルミニマムであれば、\(x\) を囲むシンプレックスの頂点を \(x_1,x_2,...,x_m\) として
\begin{equation}
f(x) \le \min(f(x_1),f(x_2),...,f(x_m) \label{eq:1}
\end{equation}
の条件が成り立つべしと考えるのは自然である。そこで、これが成立していない時には警告を出すことにした。その場合次のようなメッセージを出す。

# Failed. not a local minimum: 8.29328101784887e-09 1.2983610054792913e-09
左の数字が \(f(x)\) で、右の数字が条件式(\ref{eq:1})の右辺である。
ここに挙げた条件は必要条件であり十分条件ではない。十分条件が簡単に評価できればめでたしだが簡単ではない。

条件は過剰になることもある。しばしば関数の持つ丸め誤差が条件式(\ref{eq:1})を破る。
従って警告を無視して構わないか否かの判断は利用者に任せられている。
筆者が扱っている問題は、右辺がわずかに小さいのであるが、無視できないような問題である。
そのような微妙な問題は Nelder-Mead Method では扱えないことになる。

[1] Fuchang Gao · Lixing Han: "Implementing the Nelder-Mead simplex algorithm with adaptive parameters"
(Computational Optimization and Applications · May 2012)
https://www.researchgate.net/publication/225691623_Implementing_the_Nelder-Mead_simplex_algorithm_with_adaptive_parameters

[2] nykergoto: 『Nelder Mead Method を python で実装』
https://nykergoto.hatenablog.jp/entry/2019/11/06/Nelder_Mead_Method_%E3%82%92_python_%E3%81%A7%E5%AE%9F%E8%A3%85

[3] anms: Adaptive Nelder-Mead Minimization
https://rdrr.io/rforge/pracma/man/anms.html
2019-11-06