コラム・特集

3.9 非線形方程式を解くアルゴリズム

第14部 インダストリアル・エンジニアリングの最適化

第3章 非線形最適化

3.9 非線形方程式を解くアルゴリズム

次のシステムを考えよう。

ht (x)=0, t=1からnまで                         (14)

3.4で述べたように ,(14)式は理論的には 次式と等価になる。

目的関数:θ(x) =n∑t=1[ht(x)]^2     →   最小化    (15)

しかしながら,制約無しのアルゴリズムにより(15)式を解いたときには,局所的最適解が得られただけかもしれず,これは(15)式の大域的最適解ではない。これでは(15)式に関する情報にはなり得ない。実際に,二乗和の形をとるθ(x)は,最小化が難しい傾向にある。そこで,最小二乗法を(14)式を解くのに利用したければ,二乗和最小化のために,特に考案されたアルゴリズムの使用が望ま れる。

(14)式を解くためのニュートン法

ht (x)はそれぞれ微分可能であると仮定する。勾配ベクトルからなる ヤコビアン行列は次のように書ける。

(14)式はn個の未知変数をもつn本の連方方程式であるから,J[h (x)]はn次の正方マトリックスである。ニユートン法は解の初期見積り値x0から始まり,点列x(r=1,2,… …)が求められる。x′を現時点の解としよう。x^rが(14)式の解に近ければ,解をx^r+yとして表わすことができる。ここでyは原点 0に近い点である。この場合,微分法の平均値定理によって,次のように近似することができる。

h(x^r+y)~h(x^r)+J[h(x^r)]y         (16)

x^r+γがに(14)式の解であるように修正ベクトルyを選ぶために,(16)式の右辺をゼロとおいて yを解く。x^rでのヤコビアン行列が正則であると仮定して,y=―{j[h (x^r )]}^-1h(x^r) ~が得られる。すると次の新しい点は,

x^r+1=x^r-{J[h(x^r)]}^-1h(x)              (17)

となる。点列x1,x2,……は(17)式を用いて再帰的に計算され,列中の点がゼロに近いh(x)に達したときにこの方法は終了し,(14)式の近似解としてその点を受け入れる。

連続法
この方法は,(14)式の形の連立方程式を解くために最近開発された。αをあらかじめ選んだ固定点であるとする。 xと0から1の間で変化するパラメータλとの関数, 

g(λ,x)=λh(x)+(1-λ)(x-a)

を定義する。λが0から1までパラメトリックに変化するときの次式の解を吟味する。

g(λ,x)=0                               (18)

点aはλ=0のときの一意解である。λ=1に対する (18)式のどんな解も(14)式の解となる。(18)式の解をパラメータλの関数としてx(λ )と表わして,アルゴリズムはx(0)=αから始まり,λ=1に 至るまで曲線x(λ)を追跡する(図表14.3.3参照)。

曲線χ (λ)を追跡するために,いくつかの手法が提案されてきた。使われた手法に従って,その解法は「連続法」あるいは「ホモトピー法」と呼ばれている。この曲線をたどるための1つの方法は,スとx(λ )を, λ(S) とx(S)というSの関数として表わし,独立したパラメータSに従う曲線の長さを使うものである。g[λ (S), x(S)]=0となり,この式をSで微分して次式が得られる。

d(ds){g [λ (s),x(s)〕 }=0
λ(0)=0
x(0)=α

この連立方程式は,常微分方程式を解くための数値計算法を使用して,数値的に解くことができる。Mangasarianは,一般の制約つきの非線形計画を,(14)式の形の連立非線形方程式を解く問題に変換する方法を検討している。この変換を使えば,どのような非線形計画についても,ここで述べたアルゴリズムによって解くことができる。

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

関連記事一覧

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

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

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

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