コラム・特集

3.5 非線形計画での基本的な用語

IEハンドブック

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

第3章 非線形最適化

3.5 非線形計画での基本的な用語

すべての関数はいたるところで微分可能で,その偏微分が連続であると仮定する。これらの偏微分のうちいくつかが連続でない場合には,問題は「なめらかではない最適化問題」と呼ばれ,特別なアルゴリズムが問題を解くために開発されている。関数のうちいくつかが実際に微分不可能ならば,問題は「微分不可能な最適化問題」と呼ばれる。このような問題に対するアルゴリズムには, 導関数を利用することができない。

微分可能関数ƒ(x)の偏微分の列ベクトルは, ▽ƒ(x)=(∂/(x)/∂ x1,・ … … , ∂ /(x )/∂xn)T によって表わされる。これはxでのƒ(x)の「勾配ベクトル」とも呼ばれる。

非線形問題をコンピュータで解くには,目 的関数と制約条件の各関数を評価するために,利用者によってサブルーチンが準備されなくてはならない。アルゴリズムが導関数を必要とするならば,それを計算するサブルーチンもまた必要となる。関数が複雑な場合には,それの偏導関数の解析的表現を求めることは難しく,それを評価するためのサブルーチンを書くことも 難しく,また誤り易い。この場合,偏導関数∂ ƒ(x)/∂xjの近似式が,

∂ƒ(x)/∂xj=ƒ(x1・・・・・、xj-1,xj+1・・・・・、xn)-ƒ(x)/e    (8)

で得られる。ここでεは十分小さい正の数である。これ は偏導関数の「差分近似」,あるいは「数値微分」と呼ばれている。記号εは「差分近似の刻み幅」として知られている。勾配の良い近似を得るにはε の注意深い選択が必要である。現在ではほとんどの実務家が,このように計算した数値微分を利用している。

関数ƒ(x)の 2次の偏導関数行列はこの関数の「ヘシアン」と呼ばれ,H [ƒ(χ)]=[∂ 2ƒ(x)/∂xi∂xj ]と表わされる。ヘシアンを評価するには,すべての二次偏導関数を計算するのにπ2個のサブルーチンが必要となる。したがって,ヘシアン行列をたびたび計算するようなアルゴリズムはあまリー般的ではない。

凸関数と凹関数
関数ƒ(x)に おいては,どの2点 x1,x2に 対しても , かつすべての0≦α≦1に対しても,

ƒ[∂x^1+(1- ∂)x^2]≦ ∂ ƒ(x^1)+(1-∂)ƒ(x^2)

が成立していれば,「凸関数」とよばれる 一変数の凸関数yが図表14.3.1に示されている。

凸関数の重要な性質として,関数の装面上にある 2点を弦で結んだとき,関数自身はこれら2点を結ぶ弦の下方に位置している 一 変数関数では,その勾配が単調増加であれば凸関数である。

関数ƒ(x) は ,

ƒ[∂x^1+(1+∂)x^2]≧ ∂ƒ(x^1)+(1-∂)+ƒ(x^1)十 (1-α )ƒ(x^2)

がすべてのx1,x2に対し0≦ α ≦1において成り立てば ,「凹関数」であるという。したがって,一ƒ(x)が凸関数であるのならば,関数ƒ(x)は凹関数である。

非線形計画においては,凸関数,凹関数の区別をはっきりせねばならぬ非線形計画問題を解くアルゴリズムのうちのいくつかは,目的関数と制約条件での適当な凸性の仮定の下でのみ,問題の解への収束を数学的に証明できる。このようなアルゴリズムを使う前には,それが確かにこの問題に有効であることを保証するために,使用者はモデルの関数が,これらの凸性の仮定を満足するかどうかを調べておく必要がある。そこで,与えられた関数が凸か凹かを調べるための手法をもつことが重要となる。

単純な関数が凸か凹か,あるいはいずれでもないかを見分けることは可能である。しかし,多変数の複雑な関数に対しては,凸関数か,凹関数か,いずれでもないかを調べるのはたいへんに難しい。関数が2回連続微分可能のとき,ヘシアン行列が,すべてのxに対して正半定符号を持てば凸である。任意の与えられた点xに対して,ヘシアン行列が正半定であるか否かを,ピボット法によって効率よく調べることができるが,すべての決定点にこのチェックを繰り返すのは,明らかに実際的なことではない。もしヘシアン行列がある点xにおいて正定ならば,少なくとも点xにおいては,関数が局所的に凸であると言うことができる。同様にして,ヘシアン行列が点xにおいて負定ならば,関数は点xで局所的に凹である。ほとんどの場合,実際上これで十分効果的に調べることができる。

最適解のさまざまな形
θ (x)が 目的関数である,非線形計画問題の許容解の集合をKとする。Kに属するすべてのxに対してθ(x) ≦θ(x)ならば,K内の点xはK上のθ (x)に関して「大域的(あるいは絶対的)最小」と呼ばれる。またxの近傍のKに属するすべてのxに対して,θ (x)≦ θ(x) であるならば「局所的(あるいは相対的)最小」という (図表14.3.2参照)。大域的最大と局所的最大も同様に定義できる。

 

局所的最小に対する最適必要条件
これらの条件は,非線形計画でのすべての局所的最小が,満足しなければならない数学的条件である。非線形計画理論の発展での初期段階では,14.3.4で述べたような,各種の非線形計画問題に対して,最適必要条件を導き出すための研究努力が積み重ねられてきた。これらの条件は(想定されたものか,あるいは)提案されている 決定点が局所的最小かどうかを調べる際に,たいへん有効である(これらの条件を満足し ないのならば,局所的最小でさえもないと結論づけることができる)。また,これらの条件に基づくアルゴリズムもある。この章で取り上げたどの非線形計画問題に対しても,最も簡潔で有益な最適必要条件が次に与えられている。

制約条件なしの最小化問題に対する条件
xが(1)式に対する局所的最小ならば、

 ▽ θ (x)=0                    (9)

が成り立たねばならない。(9)式は(1)式に対する「一次の最適必要条件」として知られている。θ (x)が2回微分可能であれば,xが(1)式に対する局所的最小であるためのもうひとつの必要条件は,x [θ(x)]が正半定符号をもつことであり,いいかえれば,θ (x)が点xで局所的に凸であることである。

(9)式はn個の未知数を含むn本の連立方程式となる点に留意しよう。そこで,非線形方程式を解くためのアルゴリズムがあれば,(9)式にそのアルゴリズムを適用して, (1)式の制約条件なしの最小化問題を解くことができる。

等式制約つき非線形問題に対する条件
(4)式を考えてみよう。この問題での局所的最小に対する必要条件を求めるには,制約条件式に対して,「制約想定」とよばれる いくつかの簡単な数学的条件が必要である。もし点xが,これらの条件の成り立っている式(4)に関して許容であり,かつxが(4)式において局所的最小であるならば, xとともに,

∂θ(x)/∂xj-p∑t-1πt・∂ht(x)/∂xj=0  j-1 からn まで  (10)

を満足するようなラグランジュ乗数戸=(π1,……,πp ) が存在する。これらの条件は,(4)式に対する「一次の最適必要条件」として知られている。

(4)式での決定変数への制約,hi(x)=0 (t は1からPまで)と,(10)式の最適必要条件とは,n+P個の未知数 (n個の決定変数xj(j=1からnまで)と,(4)式の各制約条件に1つずつ対応したP個のラグランジュ乗数πt (t=1からpまで))を含むような,π+p本の連立方程式を与える。非線形方程式を解くアルゴリズムを使って,この連立方程式を解くことにより,(4)式が解けることになる。これは(4)式のような非線形問題を解くための「ラグランジュ乗数法」として知られている。

一般の制約つき非線形問題に対する条件
(5)式の非線形問題を考えてみよう 。xが (5)式の局所的最小となる許容解であり,かつ正則点であるならば,xとともに,

∂θ(x)/∂xj-m∑i-1・πi(∂gi(x)/∂xj)-p∑t=1・μt・πi(∂ht(x)/∂xj=0  j-1 からn まで  (11)

πi ≧ 0 すべてのt=1からmに対して
π igi(x)=0 すべてのt=1からmに対して

を満足するようなラグランジュ乗数π=(π i),μ =(μi)が存在する。

(11)式の最後の制約条件式は「最適性に対する相補性スラック条件」として知られている。これらの条件は,(5)式に対する「最適性に関する一次の必要条件」として知られている。また1951年の研究でKuhnと Tuckerにより発表されたので,通常は「Kuhn―Tuckerの最適必要条件」として知られている。しかし 最近になって1939年にW Karushの修士論文の中で,最初に発表されていたことがわかった。そこで,現在では「Karush―Kuhn―Tuckerの最適必要条件」とよばれている。(6)式に対する許容解万は,ラグランジュ乗数ベクトル万,戸 が存在し,x,π,μが(11)式を満足するならば,「 Karuch―Kuhn―Tucker点」(KKT点,定常点)とよばれる。

(8)式のような一般の非線形計画問題は,θ (x)が凸であり,各iについてgi(x )が凹であり,すべてのtに対してh1(x )がアフィン関数(すなわち,与えられた定数%, α1… … … α n に対しα0+α1×1+α 2×2+・・・ αn xnの形の関数)であるならば,「凸計画問題」であると言われている。凸計画問題においては,すべての局所的最小は大域的最小であり,どのKKT点 も大域的最小点である。「非凸計画問題」においては,この性質が成り立たないこともある。そのために非凸計画では,たくさんの局所的最小 (これらは大域的最小ではない)が存在する場合があり,このような問題においては,難しいことではあるが,すべての局所的最小を実際に列挙し尽さない限り,大域的最小を見つけるのは難しいしたがって一般には,非凸計画問題を解くさいに,現実にわれわれができることといえば,降下法により得られるKKT 点すなわち局所的最小点を求めることぐらいである。

これまでに述べたように,非線形計画問題に対するアルゴリズムが正しく働くということの数学的証明は,通常解かれるべき非線形計画が,凸計画問題であるという仮定に基づいている。実際の応用では,こ れらの凸性の仮定が成り立たない場合がある。この仮定が成り立っているか否かを調べることさえ難しい。多くの現実のモデルは非凸になり勝ちであり,実務家は通常凸性のチェックに計算時間を浪費することは好まない。そこで,とりあえずその問題にアルゴリズムを使ってみる傾向になり ,良いアルゴリズムも実際にはほとんどの問題で,局所的最小やKKT点を見つけ出すだけである。

非線形計画問題の収束の速さ
一般には,線形計画や,組み合わせ最適化問題を解くアルゴリズムは,有限アルゴリズムになる傾向がある。これに反して,非線形計画アルゴリズムは一般に有限にはならない傾向にあり,そのようなアルゴリ ズムに対してわれわれが望みうることは,せいぜい極限でその問題の局所的最適に収東するような点列を作り出すことだけである。そこで非線形計画アルゴリズムが実際に役に立つためには収束の速いものでなくてはならない。この収束の速さは実際に数学的に評価することができる。最近では急速に収束することが期待できる,非線形計画のいくつかのアルゴリズムが得られている。これらのアルゴリズムを使って,ほんの少ない計算回数で,局所的最小の十分近くまで到達することができ,特にアルゴリズムが 最適解の近くにあると分かっている点から始まった場合にはなおさらである。

次の節では,現在使われている最も 有望なアルゴリズムの基礎となっている,中心の考え方に焦点を当てる。さらに詳細については他の出典を参照されたい。

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

関連記事一覧

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

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

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

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