非線形計画法

f を n 次元空間 R^{n} = {x = (x_{1}, x_{2}, …, x_{n}) : 各 x_{i} は実数} で定義された実数値関数、 X を R^{n} の部分集合とする。このとき、 f を最小（または、最大）にする x ∈ X を求める問題を\underline{数理計画問題}、 f を\underline{目的関数}、 X を\underline{許容領域}（\underline{実行可能領域}）と呼ぶ。ここでは、数理計画問題を形式的に

目的：f(x) ⟶ 最小化
条件：x ∈ X

と書くことにする。一般に、許容領域 X は、不等式と等式を用いて

X = {x : g_{j}(x) ≤ 0 (j = 1, 2, …, ℓ), h_{k}(x) = 0 (k = 1, 2, …, m)}

のように表す。ただし、 S は R^{n} の部分集合で、不等式や等式で表せない条件（たとえば、 S = {x : 各 x_{i} は整数}）を x に課す役割を果している。数理計画問題を解く万能手法はなく、関数 f、 g_{j}、 h_{k}、および、 S にさまざまな条件をを課す。そのような条件によって、数理計画問題は\underline{線形計画問題}、\underline{２次計画問題}、\underline{非線形計画問題}、\underline{整数計画問題}等に分類される。関数 f、 g_{j}、 h_{k} がに非線形な関数が含まれ、 S が n 次元空間 R^{n} 全体であるとき、数理計画問題は非線形計画問題と呼ばれる。

数理計画問題に対して、いくつかの解の概念がある。許容領域 X 全体で目的関数 f の最小を達成している x ∈ X を（\underline{大域的な}）\underline{最小解}、 x ∈ X のある近傍 U が存在して X ∩ U 上で目的関数 f の最小を達成している x ∈ X ∩ U を\underline{極小解}（\underline{局所的な最小解}）、 x ∈ X を\underline{許容解}（\underline{実行可能解}）と呼ぶ。明らかに、

最小解の集合⊂ 極小解の集合⊂ 許容解の集合= X

である。しかしながら、一般の非線形計画問題に対しては許容解を１つ計算することさえ難しく、通常、関数 f、 g_{j}、 h_{k} の微分可能性、凸性、線形性等の条件を課す。

R^{n} の部分集合 C に含まれる任意の x, y ∈ C を結ぶ線分全体 {(1−λ)x+λy : λ ∈ [0, 1]} が C に含まれるとき、 C を\underline{凸集合}と呼ぶ。また、任意の x, y ∈ R^{n} と λ ∈ [0, 1] に対して条件

(1 − λ)ϕ(x) + λϕ(y) ≤ ϕ((1 − λ)x + λy)

を満たすとき R^{n} 上の実数値関数 ϕ を\underline{凸関数}と呼ぶ。 f が凸関数、 X が凸集合であるとき、数理計画問題には\underline{凸計画問題}と呼ぶ。凸計画問題では最小解の集合と極小解の集合は一致する。

非線形計画問題の中で最も単純な場合が、制約条件の付かない最小化問題

目的：f(x) ⟶ 最小化
条件：x ∈ R^{n}

である。この場合、 x が極小解であるための必要条件は「x が非線形方程式系 ∇f(x) = 0 を満たす」ことである。ただし、 ∇f(x) = (∂f(x)/∂x_{1}, ∂f(x)/∂x_{2}, ⋯, ∂f(x)/∂x_{2}) で、 f のグラジェエント・ベクトルと呼ばれる。特に、関数 f が凸関数であるときには ∇f(x) = 0 は最小解であるための必要かつ十分条件となる。

制約条件の付かない非線形最小化問題に対してはさまざまな計算手法が提案されているが、以下のような反復を繰返す方法が多い。

１. 初期点 x^{0} を選ぶ（粗い近似解が分っているときにはそれを x^{0} とする）． p = 1．

２. x^{p} が十分精度の良い近似解であれば反復を止める．

３. これまでの反復で得られた情報を使って探索方向 d ∈ R^{n} を決める．

４. 探索方向 d に１次元探索を行なう．すなわち、

目的：f(x^{p} + θd) ⟶ 最小化
条件：θ ∈ R
を近似的にとき、 x^{p+1} = x^{p} + θd とする。

５. p ⟵ p + 1 として、 2 へ戻る．

上述のステップ３でどのような探索方向を選ぶかが、それぞれの方法によって異なる。 \underline{最急降下法}（\underline{グラジェント法}とも呼ばれる）では局所的に最も傾斜のきつい方向、すなわち、 −∇f(x^{p}) 方向に探索方向を選ぶ。\underline{ニュ−トン法}では点 x^{p} において目的関数 f を２次関数

f(x^{p}) + ∇f(x^{p})(x − x^{p}) + \frac{1}{2}(x − x^{p})^{T} H(x^{p})(x − x^{p})

で近似し、その最小点の方向に探索方向をとる．すなわち、 d = −H(x^{p})^{−1}∇f(x^{p})．ただし、

H(x^{p}) = ( \begin{matrix}∂^{2}f(x)/∂x_{1}∂x_{1} & ⋯ & ∂^{2}f(x)/∂x_{1}∂x_{n} \\ · & ⋯ & · \\ ∂^{2}f(x)/∂x_{n}∂x_{1} & ⋯ & ∂^{2}f(x)/∂x_{n}∂x_{n} \end{matrix} )_{x=x^{p}}

で、関数 f のヘッセ行列と呼ばれる．ここではヘッセ行列 H(x^{p}) が正定値行列であることが仮定されており、そのもとで近似２次関数には最小点が存在し、探索方向 d = −H(x^{p})^{−1}∇f(x^{p}) は目的関数 f を減少させる方向になっている。ニュ−トン法の特徴は局所的な収束速度が速いことにあるが、 (a) ２階の微係数を必要とすること、 (b) 探索方向を計算するために線形方程式 H(x^{p})d = −∇f(x^{p}) を解かなければならないこと、および、 (c) ヘッセ行列 H(x^{p}) が正定値行列でない場合には探索方向 d が降下方向になるとは限らないこと等の欠点である．これらを補った\underline{準ニュ−トン法}や\underline{共役勾配法}が広く用いられている。微分を使わない方法として\underline{シンプレックス法}がよく知られている．この方法は「変数の空間 R^{n} 内で n 次元シンプレクス（n 次元単体）を目的関数 f の値の小さい方向へ転がす」という単純な原理に基づいた手法で、工学的に有用な方法の一つである。

一般の非線形計画問題

目的：f(x) ⟶ 最小化

条件：x ∈ X = {x ∈ S : g_{j}(x) ≤ 0 (j = 1, 2, …, ℓ), h_{k}(x) = 0 (k = 1, 2, …, m)}

は、理論および手法の両面で、制約条件の付かない非線形最小化問題よりもずっと複雑である．

参考文献

[1 ] 今野浩、山下浩、非線形計画法、日科技連出版、１９８７．