多変数関数の最小値を求めるプログラム

質問

複雑な関数の最小値を求めるためのプログラムを製作しています。

4つの独立な変数からなる関数を最小にする変数を探し出したいのですが、
効率の良いプログラムがなかなか作れません。
これまで試してみたのは、まずある適当な変数の組み合わせを任意に決め、
それを基準にそこから変数を少しだけずらしたとき、
関数の値が元よりも小さくなったら、ずらした変数を新たな基準として
より小さな関数値になる変数を探していく……
というものですが、どうも関数が複雑な曲線を描いているらしく、
極値を数多く持っているようで、この手法ではすぐ極値につかまってしまい、
最小値にたどりつけません。
結局、変数の取りうる組み合わせを全てしらみつぶしに調べる方法にしたのですが、
充分な精度をもたせるためには膨大な計算量が必要となってしまいまったく実用的でありません。

このような多変数関数の最小値を求めるために有効なアルゴリズムはありませんでしょうか？

回答No.2

Interest · ベストアンサー

最適化問題と呼ばれる話です。
最小化（または最大化）したい関数を「目的関数」といい、
目的関数の変数に対する拘束条件を表した式を「制約条件式」といいます。

目的関数、制約条件の性質によって解法が異なります。
典型的なものでは、
(a) 目的関数が線形で制約条件式も線形（これを線形計画問題といいます）なら「シンプレックス法」
http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E8%A8%88%E7%94%BB%E6%B3%95
(b) 目的関数も制約条件式も非線形なら（これを非線形計画問題といいます）「ニュートン法」、「共役勾配法」など。
(c) 制約条件が離散値をとるなら（これを整数計画問題や組み合わせ最適化問題といいます）・・・解法がいろいろありすぎるほどあります（汗）

基本的な考え方はどれも同じで、

> まずある適当な変数の組み合わせを任意に決め、
> それを基準にそこから変数を少しだけずらしたとき、
> 関数の値が元よりも小さくなったら、ずらした変数を新たな基準として
> より小さな関数値になる変数を探していく……

を数学的にちゃんとやってるだけのこと。

で、近年は計算機の力を使ってガラガラポンで答えを出してしまおうと言う手法がもてはやされて、

(d) 探索空間の中からランダムに変数の値をとって来て近似最適解を求めようとするモンテカルロ法や、
(e) 局所解に陥ったら乱数で適度に変数の値を微小に揺らして局所解から脱出する機会をあたえるシミュレーテッド・アニーリング法
(f) 変数の値の組み合わせ方を遺伝子の塩基配列に見立てて、ランダムに交差を行い、優秀な遺伝子（より最適解に近いもの）をのこすジェネティックアルゴリズム

などの方法で組み合わせ問題をといてしまおうという考え方があります。

いずれにしても、問題の性質によって使うべき手法が決まります。(b)～(f)は必ず最適解が求まると言う保証がないのでお気をつけください。

力技でよければ、解空間を全探索すれば必ず最適解が求まりますが、これは現実的じゃないですからお勧めしません。

お礼

遅くなりましたがお礼申し上げます。
回答ありがとうございました。
モンテカルロ法は知っていましたが、なるほど、ランダムに計算するというのは
実はそれなりに効率の良い方法なんですね。
解空間の全探索は試したことがあるんですが、
一つの解を求めるのに数十時間かかってしまいました。
ある意味で信頼性は一番高いのですが、やっぱり現実的じゃないですね。

回答No.4

chirubou

このような場合、必ず最小値が求まるというアルゴリズムは見つかっていません。

GA（遺伝的アルゴリズム）とか「焼き鈍し(SA)法」とかありますが、これらは、単純な勾配法（質問者さんが試された方法よりもう少し高速な方法、基本は同じ）よりも極地にとらわれない（可能性がある）というだけで、最小値が必ず求まる方法ではありません。ただ、運がよければ見つかるかもしれない、というだけです。

救いは変数が４つ程度ということです。新たに GA や SA を勉強するのが面倒であれば、質問者さんのアルゴリズムで、初期値を複数にしてその結果の中から最小値を選ぶ、というのでもいいような気もします。ただ、変数の数がもっと多くなると探索空間が広くなるので、この方法では難しいでしょう。

お礼

遅くなりましたがお礼申し上げます。
回答ありがとうございました。
必勝のアルゴリズムはまだ発明されていないのですね。
なんだか意外な感じがします。
初期値を複数にして、というのは試してみたのですが、
どうも、求まる解は初期値に大きく依存しているようで、
充分な精度を達成するには結構な数の初期値を試す必要があって、
結局、全探索と同じようなことになってしまいました。
どんな解空間になっているのか、一度目で見てみたいものです。

補足

みなさん、情報ありがとうございます。
一通り、紹介していただいたアルゴリズムを調べて、
挑戦してみたいと思います。
取り急ぎご連絡まで。

回答No.3

rabbit_cat

その関数が連続関数で、かつとりうる変数の範囲に制約がない（-∞から∞までとれる）なら、
Differential Evolution (DE)
というアルゴリズムがいいと思います。
遺伝的アルゴリズムの一種ですが、計算量の割にはかなり強力です。

お礼

遅くなりましたがお礼申し上げます。
回答ありがとうございました。
Differential Evolution,
日本語で言うと差分発展とか微分展開とかでしょうか？
ちょっと検索して見つけたのが以下のサイトです。
http://www.icsi.berkeley.edu/~storn/code.html
今回、自分が考えていたものは、変数が有限の範囲の制約をもっていたので、
これについては詳しく調べませんでした。
せっかく教えてくださったのに、すみません。

回答No.1

neKo_deux

遺伝的アルゴリズム(Genetic Algorithm)とかですと、こういった「だまし問題」に対しても、それなりの計算時間で、それなりの性能を発揮します。

アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

お礼

遅くなりましたが、お礼申し上げます。
回答ありがとうございました。
なるほど、遺伝的アルゴリズムというものがあるんですね。
自分はC言語をやっていますので、以下のサイトが参考になりました。
http://www6.plala.or.jp/mnagaku/cmag/ac19999/