最小化(minimization)


最適なfittingとかやろうと思ったときに、関数の最小値を求めなければならない時がある。ここでは関数の一般的な関数の最小値を求める方法について考えてみる。


関数

少なくとも関数には連続性があるとしよう。このときはコンパクト集合(compact set)である。微分可能なら、なおいい。微分可能でなくても、まあ何とかなる。


一次元での手法(methods in one dimension)



を考えてみよう。が微分可能なら、最小値となるのは となる点のどれかか、端点のどちらかである。が解きにくいなら、なんらかの方法で球根すればいい。


ブレント法(Brent’s method)


微分可能でない場合、どないするかを考えてみよう。


3点
において、 ならば、は減少してで増えてるゆうことだ。つまりは、のどっかに極小値があるはずである。この範囲を二分法みたいなんで縮めてって特定してしまおうってのがブレント法だ。


多次元での方法(methods in many dimensions)


関数 , はコンパクト集合(compact set)

とする。コンパクト性について詳しく語ると長くなるので、「有界な(無限に拡がってない)閉集合(領域の境界は含まない)」と簡単に言っておこう。詳しくは、「集合・位相」の本を見ていただくことにしよう。


あと、少なくとも関数には連続性があるとしよう。

微分可能なら、なおいい。微分可能でなくても、まあ何とかなる。


微分可能なら、のいずれかか、の境界で最小(global minimum)となる。

後者のケースにおいて、が多面体(polyhedron)ならば、の各面でまたもや同じタイプの最小化問題を考えていくことになる。(次元はひとつ減る) これは、「オブジェクト間の距離」の計算でやったやつだ。また、を解くのは球根(root−finding)問題に帰着する。


最急降下法(Steepest Descent Method)

長所)計算簡単

短所)計算時間かかる&局所解におちたりしよる。

の地点をちんたら探す。

初期値をから、 はステップ量を表すスカラ。これは勾配方向に向かって落としてくのでマイナス。


共役勾配法(Conjugate Gradient Search)

長所)収束早い

短所)局所解におちる可能性あり

勾配方向に落とし込んでいくよか、共役方向のほうが収束速い。


2つの方向の数列を用意する。ひとつは、勾配方向もひとつは共役方向

共役方向に落としていくが、ステップ量をうまいことー調整する必要が出てくる。

この、1次元の最小化はいろんな方法があるが、PolakとRibiereの公式でやってみると以下のような疑似コードになる。


// を最小化する。

x=適当な初期値; g=−gradient(E)(x); h=g;

while (1){

line.origin =x; line.direction =h;

MinimizeOn(line,x,fval);

 // ↑1次元ミニマイザ

if ( 終了条件 )return <x,fval>; // x地点でfvalが最小値

gNext = − gradient(E)(x);

c = Dot(gNext−g,gNext)/Dot(g,g);

// 定数は、前の勾配のノルム二乗によって除算されたカレントの勾配と勾配の前の変化の内積

g = gNext;

h =g+c*h;

}


その他、ニューラルネットワークをバックプロパゲーションでの学習させるときにこの手の手法を使うので、ニューラルネット関係を調べるといろいろ紹介されてたりするので、そのへんも調べてみてチョーダイ。

http://www.mathworks.com/access/helpdesk/jhelp/toolbox/nnet/backpr58.shtml



参考文献

1.『3DGame EngineDesign』 , David H.Eberly , MORGANKAUFMANNPUBLISHERS ,ISBN1−55860−593−2.

2.解析学の教科書いろいろ(;´Д`)