コラム・特集

3.6 直線最小化アルゴリズム

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

第3章 非線形最適化

3.6 直線最小化アルゴリズム

直線最小化問題は一変数λの全直線上で,あるいは特定の区間ℓ≦λ≦u上で,一変数λの関数ƒ(λ)を最小化する問題である。多変数の非線形計画アルゴリズムでは,直線最小化問題をサブルーチンとして繰り返し使用している場合が多い。

ƒ(λ)が凹で,ℓとuが有限であれば,最小点はℓかuであって,このどちらかがƒ(x )の最小値を与える。ƒ(λ)が凹でなければ,局所的最小の近傍においては, 関数ƒ(λ)が放物線で近似できるという考え方に立って, 関数近似に基づいた手法が用いられる。いったん,良い放物線P(λ)が曲線のあてはめによって決まれば,P(λ) の最小が,元の関数ƒ(λ)の最小の近似として利用できる。

この手法は初期点λ0から始まる。初めに「最小に対する括弧」と呼ばれる,最小点を含む有限区間を見つける。正の探索幅Zを選ぶ.ƒ(λ0)と λ1=λ0+Δ に対するƒ(λ1) とを計算する。ƒ(λ1) <ƒ(λ0)ならば,λが増加する方向が正しい探索方向となる。さもなければ方向を逆にするために,ΔをΔで置き変えて,次に述べる処理に進む。 r=2,3,… …に対し て,λr =λr-1+2^r-1Δを定義し,ƒ(λr+1 ),r=2,3,… …が減少を続ける 限り ,λの上界に達するか,ƒ(λr+1)>ƒ(λr)となるようなkがrに対して見つかるまで計算を続ける。この場合,ƒ(λk)<ƒ(λ r-1),ƒ(λr+1)>ƒ(λr)を満足するようなλk-1,λk,λk+1を得る。

4点 ,λk-1,λk, (λk十λk+1)/2,λk+1の中で,λk-1かλk+1のどちらかを除く。この場合,ƒ(λ)の最小値を与える2点 [λk, (λ k+λk+1)/2」をのうちから遠いほうの点を取り除くことにする。残った点をλa,λb,λcと置く(ここでƒa<ƒb<ƒc)。これらの点は等距離にあり,ƒ(λb)≦ƒ(λ c),ƒ(λc)≦ ƒ(λa)である。このλaからλc までの区間が最小点を挟んでいる。

最小点を挟むλa,λb,λc が得られたら,λ=λa,λb,λcにおいてƒ(λ)=P(λ)となるように,二次関数P(λ) =α0+α1λ十α2λ^2の係数α0,α1,α2を決める。P(λ) は二次関数なので,その最小点は容易に解析的に計算できる。この最小点はλ*=λb+δ であることが確かめられる。ここで

lδlが,ある定められた許容誤差よりも小さければ,アルゴリズムは終りで ,λ*が最小点として受け入れられる。さもなければ,ƒ(λ)に最小値を与えた2点 (λb, λ*}を新たな初期点として,短縮された探索幅を用いて全手順を繰り返す。実際にはƒ(λ)の局所的最小の近くに到達するのに,ほんの2~3回の繰り返しで十分である。

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

関連記事一覧

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

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

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

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