関数f(x1,x2,x3,x4,x5)が最大値となるようなx1,x2,x3,x4,x5の求め方

変数を5つもつ関数f(x1,x2,x3,x4,x5)があります。
関数f(x1,x2,x3,x4,x5)は、一言では言い表せないような複雑な式とします。

y=f(x1,x2,x3,x4,x5)としたとき、
yが最大になるようなx1,x2,x3,x4,x5はどのようにして求めればよいでしょうか？

例えば、、、

(1) x2,x3,x4,x5を適当な値に固定し、x1を変化させてyが最大となるようなx1を求める。（このときのx1をaとする）

(2) x1をaに、x3,x4,x5を適当な値に固定し、x2を変化させてyが最大となるようなx2を求める。（このときのx2をbとする）

(3) x1をaに、x2をbに、x4,x5を適当な値に固定し、x3を変化させてyが最大となるようなx3を求める。（このときのx3をcとする）

(4) x1をaに、x2をbに、x3をcに、x5を適当な値に固定し、x4を変化させてyが最大となるようなx4を求める。（このときのx4をdとする）

(5) x1をaに、x2をbに、x3をcに、x4をdに固定し、x5を変化させてyが最大となるようなx5を求める。（このときのx5をeとする）

このとき、f(a,b,c,d,e)は最大値？？
多分、違いますよね。

No.2 ベストアンサー 回答者： chirubou 回答日時： 2006/05/26 14:59

まず最初に、この「一言では言い表せないような複雑な」関数が「連続」である必要があります。

不連続の場合は初期値（「x2,x3,x4,x5を適当な値に固定し」に相当）から最大値に至る探索の道筋の手がかりがなにも無い事になってしまいますから。

次に、この方法で最大値が求まるためは、２次元で考えたとして山の頂上（y の最大値に相当）がパラメータx1,x2,x3,x4,x5の値域内でひとつだけである必要があります。山で例えると富士山（頂上の火口付近のくぼみは無視して）のような山です。そうでない場合、つまり、例えば八ヶ岳のように複数の頂上があった場合、見つかった値は最大値とは限りません。つまり八ヶ岳のひとつの頂上が見つかっただかで、これが八ヶ岳で一番高い頂上かどうかは分からないということです。こうして見つかった y の値を「局所最大値」と呼びます。確実に（局所でない大局的な）最大値を見つける方法は見つかっていません。

質問者さんの方法でも（局所）最大値は見つかりますが、多くの場合、x1~x5 をそれぞれ少しだけ値を振って（Δx）、その時の y の変化が大きい方に、より動いていく、というやり方をします。例えて言えば、山登りで霧がたち込めていて頂上が見えない場合、足下の周辺の地面だけを見て、最も傾斜が急な方向に次の一歩を踏み出す（次の x1~x5 を決める）わけです。この方法は No.1 さんのおっしゃるように「山登り法」と呼ばれており、質問者さんの方法より速く（少ない歩数で）（局所）最大値に達することができます。

歩幅の大きさにも注意が必要です。頂上や山の大きさに関係するのですが、多くの場合「一言では言い表せないような複雑な」訳で、山の大きさすら分かりません。一歩の大きさを大きくすればそれだけ速く頂上に到達できますが、頂上の正確な位置がでませんし、山よりも大きな歩幅ですと山を飛び越えてしまいますので、「十分に」小さな値にします。計算を速くするために、最初の歩幅は大きく、段々歩幅を小さくするというやり方もあります。

より詳しくは「山登り法」で検索されるといろいろと見つかると思います。

この回答へのお礼

色々と勉強になります。
実は、この関数が連続か不連続かについてですが、次のような場合は、やはり不連続なのでしょうか？
・f(x1,x2,x3,x4,x5)の値は整数
・x1,x2,x3,x5は自然数
・x4は0以上、1以下の実数
もちろん、関数なので、x1～x5が決定すれば、f(x1,x2,x3,x4,x5)もいつも同じ値になります。

たしかに、私の方法では局所最大値しか見つからないですね。（そもそも、局所最大値ですらない可能性もありますが）

局所最大値から、真の最大値を見つける工夫はあるんですかね？

たとえば、a,b,c,d,eを見つけた後、今度は、b,c,d,eを固定してaを変化させて更に大きな解がないか調べる。
⇒なければ、今度はa,c,d,eを固定してbを変化させる
⇒もっと大きな解a'があれば、x1をa'に、x3,x4,x5をc,d,eに固定して、bを変化させてみる

これを繰り返せば、もっとよい値を見つけることができないですかね？

お礼日時：2006/05/26 15:53

No.3 回答者： chirubou 回答日時： 2006/05/26 17:04

No.2 です。

> 次のような場合は、やはり不連続なのでしょうか？

基本的には不連続ですね。ただし場合によっては連続と「みなし」て同等の扱いができることもないことはないのですが、関数の実体がわからないのでこれ以上はなんとも…

> そもそも、局所最大値ですらない可能性もありますが

そもそも y が一定だったりすると最大値というものが存在しないことになってしまいます。

> 局所最大値から、真の最大値を見つける工夫はあるんですかね？

一般的に見つけることはできません。というか、もしそういう「工夫」が見つかったら、世の中大変な騒ぎになると思いますよ。

> これを繰り返せば、もっとよい値を見つけることができないですかね？

最初の初期値を全く違う場所から始めた方が、別な局所最大値を見つけられる可能性が高いと思います。最初に見つけたところの近くから始めると、同じ頂上に到達する可能性が高くなりますから。まあ、これも連続と仮定しての話ですが。

局所最大値をいくつも探すことで、本当の最大値を見つけられるか、ということですが、より良い値を見つけることができるかもしれないし、もっと悪い値しか見つけられないかもしれない、としか言えません。もっと悪いことに、山の頂きの数さえ（一般には）分からないので、いつ計算を止めていいのか分からない、ということです。最大値そのものさえ分かっていないんですから。

これ以上、一般的な事を申し上げる事はできないと思います。後は、対象となる関数の特殊性に（もしあれば）頼るしかないでしょう。

この回答へのお礼

早速のご回答、ありがとうございました。
確かに、全体像がつかめない山には登りたくないですね。
（そう考えると、世界一周を初めて成し遂げたマゼランは、改めて偉大だと思います。）

最終的には、いつ妥協するか、ということになってくると思いますので、自分で適当にyの最低ラインを設けて、それ以上になった場合、もしくは、最初の地点を変える回数の上限を決めて、その回数だけ局所最大値を見つけた場合に、見つかった局所最大値のうち最大のものを採用したいと思います。

色々とありがとうございました。

お礼日時：2006/05/26 17:19

No.1 回答者： BLUEPIXY 回答日時： 2006/05/26 13:11

プログラムのアルゴリズムとしては、

最急勾配法(山登り法)といわれるものがあります。
http://ipr20.cs.ehime-u.ac.jp/column/ga/chapter3 …
質問者の仰るような方法は、山登り法に似ていると思いますが、
＞x1を変化させてyが最大となるようなx1を求める
＞x1をaに、x3,x4,x5を適当な値に固定し、x2を変化させてyが最大となるようなx2を求める。
というような手順では、山登り法で言えば、調べているポイントが飛び飛びになりすぎて、f(a,b,c,d,e)は最大値 とはとても言えないと思います。

この回答へのお礼

なるほど、山登り法ですね。
調べてみたところ、NP困難問題の一種みたいですね。
何か決まった解法があるわけではないことが分かりました。

質問に回答して頂いてありがとうございました。

お礼日時：2006/05/26 15:26