コラム・特集

3.10  一般制約つき非線形問題

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

第3章 非線形最適化

3.10  一般制約つき非線形問題

この節では,実務家によって一番多く利用されている方法に焦点を当てる。

変数分離形計画
π個の決定変数x1,x2,・・・・,xnの関数ƒ(x)が,おのおのただ1つの変数を含むようなn個の関数の和になっていれば,変数分離であるという。すなわちƒ(x)= ƒ1(x1)+… …+ƒn(xn)である。

たとえばƒ(x1,x2)= (x^3-2×1^2+x1+6)+(x^4-x2)は変数分離形関数であるが,g(x1,x2)=3x^2-2x1x2+x^2は違う。

目的関数:θ (x)一 最小化
制約条件:gi(x)≦ 0, i=1からmまでは        (19)

は,θ (x),gl(x),… …,gi(x)の各関数が変数分離形であれば,変数分離形計画といわれる。変数分離形計画は,区分的線形関数で非線形の変数分離形関数を近似し,シンプレックス・アルゴリズムを使って変換された問題を解くことにより解を得る方法である。この近似をどのようにして導くかを次に述べる。

1つの決定変数yを考え,ƒ(y)は関数とする。この問題でyの下限がゼロになるように原点を移動する。等 間隔にする必要はないが,非負のyの範囲をいくつかの区分点y1,… …y^kを選んで,重複のない区間に分割する(図表14.3.4)。

t=0からk-1までに対して,点 [y^t′,ƒ(y^t)]と[y^t;1,+1,ƒ(y^t+1)]を直線で結び,区分的線形近似P(y)を得る。ƒ(y)が凸ならば常にP(y)≧ ƒ(y)であり , 近似の誤差は常に非負である。また互いに密接して区分点をとることにより ,近似 P(y)をいくら でもƒ(y)に近づけることができる。c^tを区間 [y^t,y^t+1]におけるP(y)の勾配とする。これはy=0からk-1に対してc^1=E/(y+1)-ƒ(y)]/(y+1-y^t)である。U1を t=0からk-1に関する区間[y^t,y+1]の長さとする yのどのような値に対しても ,t=0からk-1までに対する区間[y,y+1]と,区間[0,y]との重複部分の長さをξ1によって表わそう。すると,

y=ξ0+ξ1+  ・・・・・・・・・・・  +ξk-1
P(y)=c^0 ξ0+c^1ξ1+・・・c^k-1ξk-1

となる。そこでこれらの新しい変数ξ0,ξ1・・・・・・,ξk-1によって表わすと,区分的線形近似P(y)は線形関数となる。もちろん新しい変数ξ0,ξ0,・・・・・・,ξk-1は y=0からk-1に対し,0≦ ξt≦Utであり,また自分より前の変数ξ0,・・・・・・ξt-1がそれぞれその上限に等しくなっていない限り,ξt=0であるという制約を満たさなくてはならぬ。

(19)式の非線形計画において,すべての関数が変数分離形ならば,

θ(x)=θ1(x)●+・・・・・+θn(x)               (20)
g1(x)=gi1(x1)+ ・・・・・ +gin(xn)     

           i=1 からmに対して

となる。おのおののi=1からnまでに対して,xjの変動可能範囲内に区分点を選び,いま述べたような新しい変動を導入することによって,θj(xj)と gij (xj),i=1からmまで,の各関数を新しい変数による線形関数によって近似する。これらの式と(20)式を用いて,は(19)式を新しい変数による線形計画法に近似することができる。(19)式の関数が凸であり変数分離形であれば,この手法は(19)式の最適解の非常に良い近似を与えている。

線形近似法
(15)式の一般非線形計画を考えてみよう。この手法は1961年にGririthとStewartによって提案された。繰り返し数力に応じて点x^kが与えられたとする。この手法では 関数θ (x),gi(x),hi (x)をそれぞれx^k点での線形近似式に置き換えて,次のような線形計画問題を作り出す。

ここでujは各ノに関する,ある正の限界である。この線形近似は一般には,ほんの局所的に,すなわち近似点x^kの回りの小さな近傍でだけ成り立っているにすぎない。したがって,このx^kの近傍に決定点の動きを限定するため,ある限界を変数に与えておく 。そのために,(21)式の線形計画問題を解くにあたっては,現在のx^k点から,ほんの小さな刻み幅で動くにすぎない。このようなわけで, この手法は「刻み幅の小さい傾斜法」とよばれている。

シンプレックス法を使って(21)式の線形計画問題を解き, 最適解x^k+1が得られたとしよう。x^k+1に対しても再びその手順を繰り返し,その点が許容に近づき,次の刻みとの間で点の変化が小さくなったときに,アルゴリズムは終了する。

この手法は,一般には収束するという確証はないが, 実際の問題を解く上ではなかなか有効であることが報告されている。特に多変数を含んでおり,たぶんいくつかの線形制約の中に,ほんのわずかの非線形制約を含むような問題を解く場合に最も有効となる。これを使うにあたっては,良いLPコードさえあればよいのだから非常に簡単である変数に対して導された限界が,アルゴリズムの成功にたいへん影響してくる。ujが非常に小さければゆっくり進行する。ujが大きければ,現在点から動くときに線形近似が不正確になってしまい,結果として大きな非許容性をもつ点にいってしまうおそれがある。

一般化縮小勾配法
この方法を適用するため,問題は次の形に変換されているものとする。

とする。ここで,xn+1は付加変数であり,α は大きな正の定数である。この修正問題に対して(x01 ,……… ,x0n ,1)は許容解であり,この問題は(22)式と同形である。

αは大きな正の定数であるから,(22)式の原問題が許容であれば修正問題の最適解では,xn+1の値がゼロになるよう強制される。このようにして回式の原問題を考えるが, 初期許容解は用意されていると仮定してよい。このアゴリズムの一般ステップにおける計算は次のようになる。 xをこのステップの始めにおける許容解とする。14.3.8の縮小勾配法のように,変数は2つのベクトルに分割できる。すなわちp個の基底変数からなるベクトルxβ と,n-p個の非基底変数からなるベクトルxDである。基底変数は,(22)式の等式制約条件の中の非基底変数から暗黙裏に決まってくる。

∂ h(x)/∂xBは許容解xで評価された,χBの基底変数に対する関数ht (x )の P×P偏微 分マトリックスを示す。∂h(x)/∂xD,∂θ(x)/∂xB,,∂θ (χ)/∂xDも同様の意味である 非基底変数のベクトルχDに関するxでの縮小勾配は、

この式により 許容領域内で曲線ϒがかける。この曲線に沿って現在点xから動くことにより,さらに良い決定点が得られる。曲線Γに沿って動くにつれて,非基底変数が線形に変わったとし ても,基底変数は(23)式を連続して満足させるため,パラメータスによって非線形に変わらなければならない。これは実行するのが難しい。そこで計算は次のようにして行われる。まず現在点xにおける,曲線Γへの接線ιを求め,この接線Lに沿って直線的に点x^~1まで動かす。この点は一般に(22)式が非許容となる点である。次に,アルゴリズムは39節のニュートン法に基づく修正手順により,x^~1から許容領域内の曲線Γ上の点γまで戻る(図表14.3.5参照)。

新し い許容解x^~かxより良ければ,それをとり次に進む。ニュートン法が収束しなかったり,あるいは点γが θ(x~)>θ(x)となってしまうときには,点x^~1からLに沿ってxのほうに途中まで引き返して,ニュートン法を新しいx^~1からやり直す。アルゴリズム中の基底ベクトルと非基底ベクトルの交換を,さらに有効に行うために, 多くのルールが開発されている。

罰金法
このクラ スにはさまざまの手法があるが,すべて制約つき最適化問題を解くに当たって,これと関連はもつが, より単純な制約なし最適化問題を用い,そ れの繰返し近似によって解いている。この近似は,目的関数に制約条件を破ったときの高い費用を表わす罰金項を加えることにより実現される。この手法では,罰金項のきびしさと, したがって制約なし最小化問題の原問題への近接度とは

罰金パラメ ータrによって制御されている 。r がゼロに近づくにつれて近似は良くなってくる(図表14.3.6)。

(5)式の一般非線形問題を考えてみる。 「外点罰金法」では ,これを次のように制約なし最適化問題に変換している

ここでrは正の罰金パラメータである.(5)式が最適解 を持てば,rがゼロに近づく につれて,20式 の最適解も またb)式 の最適解に近づく ,rが非常に小さくなると , ht(x)の値がゼロから少しでも変わるか,gi(x)の値が負の範囲で少しでも変われば,P(x,r)の値に急激な増加をもたらし,20式の制約なし の最適化問題は,不安定な状態となって計算で解くことが難しくなる 。こ の問題を処理する手段の1つに,rの値をゼロに至る数列によって与え,パラメトリックに(24)式を解くものがある。(24)式の最適解をx (r)で表わす。最初にrの十分大きな値から始め,各ステップごとに,たとえば2というような正の数で割っていく 。あるステップで得られた最適解は,rを減らした次のステップでの制約なし最小化問題の初期解として使われる。このようにして,順次得られたx(r)の解は,(5)式の最適解に収東していく。

次に,よく知られた制約なし逐次最小化技法(SUMT)が代表例の「内点罰金法」がある(「障壁関数法」ともよばれる)。これらの方法は,すべての不等式制約条件が,内点として満足されている点から開始して,この性質が保たれる点の間を移動していく。これらの方法では,(5)式 は次の制約なし 問題に 変換される。

この手法もまた , rの値を減少させながら次々に問題が解かれていく 。最初の問題はi=1からmまでの,すべてのと (gi)>0を満足する初期点を用いる.gi(x) がゼロに近づくと,1/gi(x)は ∞に近づくから,m式の制約なし最小化問題では,すべての点がgi(x)>0を満足する(不等式制約のいくつかが極限において,等式で成り立っていることはあり得るが)。ゆるやかな条件のも とで,(25)式の最適解x(r)の点列は, rの値をゼロに減少させていくと(5)式の局所的最小値に収束することが示される。この方法の効率は, 38節で述べたかたちのアクティブ集合探索と結びつけることにより改良できる最近「増強ラグランジュ法」と呼ばれる罰金関数法が開発されている。これら の方法は罰金項とラグランジュ乗数項を結合したものである。これにより,罰金パラメータの項がゼロに近づくときに起こりがちの,不安定性にもとづく困難さを避けられることが報告されている。

 

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

関連記事一覧

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

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

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

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