ひせんけいけいかくとは? わかりやすく解説

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.




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ひせんけいけいかく」の関連用語

ひせんけいけいかくのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ひせんけいけいかくのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2024 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2024 GRAS Group, Inc.RSS