コラム・特集

3.8 線形制約つき非線形最適化問題

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

第3章 非線形最適化

3.8  線形制約つき非線形最適化問題

この節では有効と思われる2つのアルゴリズムを述べる。

縮小勾配法
このクラスの問題は簡単な変換によって次の形に表わせる。

目的関数:θ (x)   →   最小化
制約条件:Ax=b           (12)
ℓ≦x≦u          

ここでAは階数mのm×n行列であり,ℓとuはおのおの変数に対する下限,上限ベクトルである。(12)式のm個の等式制約を用いてm個の変数を省去して,問題を残りn-m個の変数だけにより表わすことができる。たとえ陽にこれを行わなくても,アルゴリズムはこの事実に基づいている。このためには,(12)式の基底βに対応するπ個の従属(基底)変数を選ぶ。

xBとxDをおのおの基底変数列ベクトルと非基底変数列ベクトルとする。Dを(12)式の非基底変数の係数マトリックス[大きさはm× (n-m)]とする。

x=(xB,xD)をこの問題のある 許容解とする。c= [▽θ(x)]Tはxにおけるθ (x)の勾配ベクトルである。cBとcDをおのおの,xにおけるxB,xDに関する θ (x) の偏微分ベクトルとする。

cD=cD-cBB^-1A とする。べクトルcDはxにおける「縮少勾配ベクト ル」。xjは非基底変数ベクトルとして知られている。xjが非基底変数であるようなjに対して,

yj=-cj(cj<0でxj<uj,あるいはcj>0 でxj >ℓjのとき) =0(その他のとき)

を定義する。

yDをこれらのみを並べたベクトルであるとする。yDは非基底変数らの空間での下りの傾斜方向 のベクトルである。yB=B^-1DyDと定義し ,y=(yBβ, yD)とする,y=0ならば,現在の許容解xが局所的最小であり,アルゴリズムは終了となる。そうでなければ,x+λyが境界ℓとuの中に存在じうるλの最大値λを定め,次に0≦ λ ≦λ において,θ (x+λy )を最小化するための直線最小化問題を解く。λがこの直線最小化問題の最適解であるならば,x+λyが次の点となり,アルゴリズムはこの点をもって次のステップに移る。このアルゴリズムを効率よくするため,基底ベクトルを変更する規則が存在する。

アクティプ集合戦略に基づくアルゴリズム

(3)式を考えてみよう。どの不等式制約が,最適解において等式として成立している(アクティブである)か推測できるとすれば,問題を線形等式制約条件に対するアルゴリズムだけで解くことが可能となる。(5)式の最適解が D1x=d1とDi^x>diを満足するように,Dを次のように分割できるものと仮定しよう。

(13)式の最適解xが得られたときには,同時にこれらのベクトルが,(13)式に対する一次の最適必要条件をともに満足するような,ラグランジュ乗数ベクトルπ,μも得ることができる。xが D1-x≧diとμ1≧0を満足すれば , xが(3)式の局所的最小となり,アルゴリズムは終了する。

一方,μIの中にμI<0となるものが存在すれば,アクティブ集合の中から,i番目の不等式制約を落とすことによって,さらに良い解が得られる。このような戦略は「アクティブ集合戦略」として知られている。この戦略では,いつアクティブ集合の中に不等式制約を加え,いつアクティブ集合から不等式制約を省くべきかを決定するための規則が作られている。この戦略は等式制約として扱っている現在のアクティブ制約のもとに,θ(x)を最小化するアルゴリズムが組み合わされている。

この種のアルゴリズムは,(3)式のかたちの,大規模な非線形計画間題を解くのに有力であることが分かっている。

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

関連記事一覧

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

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

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

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