コラム・特集

3.7 制約無しの最小化問題

IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第3章 非線形最適化

3.7 制約無しの最小化問題

(1)式の問題を考える。この節では非常に有効な2つの降下法について説明しよう。

共役傾斜法
この手法はいくつかのサイクルを 通して実行さ れる各サイクルはπ+1ステップの直線探索で構成される 。 サイクル1は選ばれた初期点x^0から始まる一般のサイクルは次のようになる。

ステップ1
x^0をのサイクルの出発点とする。y^1= -▽θ (x^0)を求める直線探索を行うことにより ,λ≧0の範囲でθ (x^0+λy^2)の最小点λ1を探し,x^1=x0+λ1y1とおき,次のステップに進む。

一般のステップk
x^k-1はこのサイクルのk-1ステップの終わりで得られた点とする。

を求める。直線探索によって,λ ≧0で,θ(x^k-1+λ ky^k) の最小点であるλkを計算する。

x^k=x^k-1+λky^kとする。▽θ (x^k)がゼロに近づけば,x^kが (1)式の局所的最小であるとして終わりとする〔この場合には,xk は(9)式の最適必要条件を近似的に満足している〕。もしk=n+1なら,このサイクルを終わる。このサイクルでの目的関数値の変化が小さければ,(1)式の局所的最小の近似値としてxkをとり,アルゴリズムを終結させる。さもなければ,初期点をxkとして次のサイクルに進む。一方, k<n+1な らば,このサイクルでの次のステップに進む。

変動測度法
この手法は擬似ニュートン法の部類に属する。

また一般には,Davidon,Fletcher,Powellによって提案されたことから 「DFP法」として知られている。この手法もまた,いくつかのサイクルで遂行され,各サイクルはn+1ステップからなる。一般のサイクルは次のようになる。

ステップ1
サイク ル が1であれば,x0がこのアルゴリズムを開始するときの初期点である。さもなければ,直前のサイクルで得られた最終点を初期点とおく D1=Iとおく。ここでIはn次の単位行列とする。

y1=-D1▽θ (x0)を求める。λ≧0で,θ (x0+λy1)の最小点λ1を計算する。 x1=x0+λ1y1とおき,次のステップに進む。

一般ステップk+1
xkとDkを,それぞれ直前のステップの終わりで得られた点とマトリックスであるとする。

Pk=xk-x^k-1,Qk=▽Q(xk)-▽θ(xk-1), y^k+1= -Dk+1▽θ (xk)を計算する。ここで、

とする。λ≧0で,θ (x^k+λ y^k+1)の最小点λk+1を探す。x^k+1=xk+λk+1y^k+1 とする。もしk+1くπ+1ならば,このサイクルの次のステップに進む。k+1=n+1ならば,初期点をx^k+1として次のサイクルに進む。

勾配ベクトルがゼロに近づいたとき,あるいはサイクル中の目的関数値の変化,あるいは解の変化が小さくなったときには,アルゴリズムは終了とする。終了の最後の点が,(1)式に対する局所的最小点の近似値となる。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー