非線形計画

【ひせんけいけいかく (nonlinear programming)】

概要

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

詳説

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

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

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

$f(x^{*})\leq f(x)\quad \forall \,x\in S$

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

$f(x^{*})\leq 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)\leq 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}\geq 0,\ F_{i}(x)\geq 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.