nonlinear programmingとは何？わかりやすく解説 Weblio辞書

OR事典

索引トップ用語の索引ランキングカテゴリー

非線形計画

読み方：ひせんけいけいかく
【英】：nonlinear programming

概要

非線形計画問題に対する数値解法, 最適性条件, 双対性理論などを研究する分野.

詳説

　変数 $x=(x_1,\dots,x_n)$ がすべて連続変数で，目的関数および制約関数が線形とは限らない数理計画問題を非線形計画問題 (nonlinear programming problem) という．非線形計画問題は一般に

$\begin{array}{lll} \min. & f(x) & \\ \mbox{s. t.} & g_i(x) \le 0 & (i=1, \ldots, m), \\ & h_j(x) = 0 & (j=1, \ldots, l), \end{array}$

と表される．この問題の実行可能集合を $S\,$ と表す．そのとき，ある実行可能解 $x^* \in S$ に対して

$f(x^*) \le f(x) \quad \forall \, x \in S$

が成り立つならば， $x^*$ を最適解，あるいは大域的最適解 (global optimal solution) という．また，ある実行可能解 $x^*$ とその適当な近傍 $N(x^*)$ に対して

$f(x^*) \le f(x) \quad \forall x \in S \cap N(x^*)$

が成り立つとき， $x^*$ を局所的最適解(local optimal solution) という．

　目的関数 $f\,$ と不等式制約関数 $g_i\,$ が凸関数，等式制約関数 $h_j\,$ がすべて1次関数であるような問題を凸計画問題 (convex programming problem) という．凸計画問題においては，任意の局所的最適解は必ず大域的最適解となる．しかしながら，凸計画問題ではない問題，すなわち非凸計画問題 (nonconvex programming problem)においては，一般に不特定多数の局所的最適解が存在し，大域的最適解を見つけるのは非常に困難であるため，局所的最適解を考察の対象とするのが普通である．また，非凸計画問題の大域的最適解を求める方法，いわゆる大域的最適化(global optimization) の方法も近年活発に研究されている [4]．

　非線形計画問題において，その最適解を特徴づける条件を一般に最適性条件 (optimality condition) という．特に，局所的最適解が満たすべき条件を最適性の必要条件といい，逆に局所的最適解であることを保証する条件を最適性の十分条件という．また，関数の勾配のみを用いる条件を1次の条件，ヘッセ行列を用いる条件を2次の条件という．よく知られたカルーシュ・キューン・タッカー条件は1次の必要条件である．

　双対性理論(duality theory) は線形計画のみならず非線形計画問題においても重要な役割を果たす．特に，ラグランジュの双対性やフェンシェルの双対性は，数理計画問題に対する解法の設計や解析において極めて有用である．

　パラメータ $u=(u_1,\dots,u_p)$ を含む非線形計画問題

$\begin{array}{lll} \min. & f(x,u) & \\ \mbox{s. t.} & g_i(x,u) \le 0 & (i=1, \ldots, m), \\ & h_j(x,u) = 0 & (j=1, \ldots,l ), \end{array}$

において，パラメータ $u\,$ の値が変化したとき，最適解や目的関数の最小値が連続的に変化するための条件や，それらの変化率などの諸性質は安定性理論 (stability theory) の名のもとで研究されている．

　非線形計画問題の最適解の計算においては，適当な出発点から始めて，最適解に収束するような点列を次々に生成する反復法 (iterative method) が一般に用いられる．制約条件をもたない制約なし最適化問題 (unconstrained optimization problem) に対しては，準ニュートン法や共役勾配法などの効率的な反復法が，一般の制約付き最適化問題 (constrained optimization problem) に対しても，逐次2次計画法や内点法など様々な反復法が開発されている．現在，非線形計画において有効とされている反復法の多くはニュートン法に基づくものである．

　非線形計画においては，目的関数と制約関数が1回または2回連続的微分可能と仮定される場合が多いが，それらの仮定を満たさない問題もしばしば現れる．そのような微分不可能最適化問題に対しても最適性理論や数値解法の研究が進められている．非線形計画全般に関する比較的新しい事柄を解説した教科書に [1],[5]} などがある．

　非線形計画問題のなかで，目的関数が2次関数，制約関数がすべて1次関数であるようなものを2次計画問題 (quadratic programming problem) と呼ぶ．特に，目的関数が凸関数である凸2次計画問題に対しては，有限回の演算で最適解を見出すことが可能である．凸2次計画問題は最も基本的な非線形計画問題であり，逐次2次計画法など一般の非線形計画問題に対する反復法の部分問題としてもしばしば現れる．

　非線形計画に関連して相補性問題(complementarity problem) と呼ばれる重要な問題のクラスがある．相補性問題とは，変数 $x=(x_1,\dots,x_n)$ と同じ次元をもつベクトル値関数 $F(x)=(F_1(x),\dots,F_n(x))$ に対して，次式を満たす $x\,$ を求める問題である．

$x_i \ge 0, \ F_i(x) \ge 0, \ x_i F_i(x) = 0 \quad (i=1,\dots,n)$

特に， $F\,$ が1次関数のとき，線形相補性問題といい，それ以外のとき，非線形相補性問題という．2次計画問題のカルーシュ・キューン・タッカー条件は線形相補性問題として表されるので，線形相補性問題に対する効率的な方法は2次計画問題に対しても有効である [2,3]．相補性問題を含むクラスに変分不等式問題と呼ばれる問題がある．相補性問題や変分不等式問題は均衡モデルの定式化において特に有用である[3]．

　最適化問題，相補性問題などの数理計画問題において，与えられた任意の点から問題の解集合への距離を評価するために用いられる関数をエラーバウンド (error bound) という．エラーバウンドが存在するためには，一般に問題が何らかの正則条件を満たす必要がある．エラーバウンドは反復法における収束判定条件の設定や収束率の解析等において重要な役割を果たす [3]．

参考文献

[1] D.P. Bertsekas, Nonlinear Programming, Athena Scientific, 1995.

[2] R.W. Cottle, J.-S. Pang and R.E. Stone, The Linear Complementarity Problem, Academic Press, 1992.

[3] F.Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes 1 and 2, Springer, 2003.

[4] R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, 2nd Edition, Kluwer Academic Publishers, 2000.

[5] J.Nocedal and S.J.Wright, Numerical Optimization, Springer, 1999.

「OR事典」の他の用語

非線形計画：	逐次2次計画法非凸計画問題非線形相補性問題非線形計画非線形計画問題鞍点定理高速微分法
組合せ最適化：	組合せ的爆発計算の複雑さ貪欲アルゴリズム連結度集合被覆問題離散最適化問題非線形計画

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

非線形計画法

(nonlinear programming から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/21 05:31 UTC 版)

非線形計画法（ひせんけいけいかくほう、英: nonlinear programming, NLP）は、制約条件群と未知の実変数群から成る一連の等式と不等式で、制約条件または目的関数の一部が非線形なものについて、目的関数を最小化または最大化するような解を求めるプロセスである。また、非線形計画法の対象となる問題を非線形計画問題と呼ぶ。

[続きの解説]

「非線形計画法」の続きの解説一覧

>> 「nonlinear programming」を含む用語の索引
nonlinear programmingのページへのリンク

nonlinear programmingとは？わかりやすく解説

非線形計画

概要

詳説

非線形計画法

「nonlinear programming」の関連用語


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの非線形計画法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

nonlinear programmingとは？ わかりやすく解説

非線形計画

概要

詳説

非線形計画法

「nonlinear programming」の関連用語

nonlinear programmingとは？わかりやすく解説