GRG

GRG#

  • 読み: じーあーるじー

  • 英名:

Generalized Reduced Gradient method の略.日本語では一般化簡約勾配法などと呼ぶ.

線形計画問題で取り扱われていた簡約勾配法を非線形計画問題に一般化した手法である. 通常 \(h(x)=0\) で表される制約式の個数は変数よりも少ない. そこで \(n-m\) 個の変数が自由変数で,残りの変数は \(h(x)=0\) により一意に定まると考える. そうすることによって無制約の非線形計画問題として解を導出できるだろうという考え方である.

このような発想は古くは線形計画法における単体法に起源があると言える. 実際はステップ方向を決めるために上記の発想が適用されるが, ステップサイズを決める部分は主双対内点法や逐次二次計画法と同様である. 準備としてスラック変数などを導入し以下の形の問題に変形する.

(16)#\[\begin{split}\begin{array}{ll} \min & f(x) \\ \mathrm{s.t.} & h(x)=0, \ h(x) \in \mathbb{R}^n \\ & x \in \mathbb{R}^n \\ & x \ge 0 \end{array}\end{split}\]

このときステップ方向を以下のように求める. 変数を \(x=(x_B, x_N)^\top\) のように \(m\) 個と \(n-m\) 個に分ける. 同様に \(\nabla h(x)\)\(\nabla h(x) = \begin{pmatrix} (\nabla h(x))_B \\ (\nabla h(x))_N \end{pmatrix}\) のように分ける. この時 \(h(x)=0\) となるように \(x_B\)\(x_N\) が関係付けられているとして, \(h(x)\) の微分を考えると \(dh(x_B,x_N) = (\nabla h(x))_B \cdot dx_B + (\nabla h(x))_N \cdot dx_N = 0\) という等式を得る.

よって \(\partial x_B / \partial x_N = -{(\nabla h(x))_B}^{-1} \cdot (\nabla h(x))_N\) が成り立つことで, \(df/dx_N = (\nabla f(x))_N - (\nabla f(x))_B{(\nabla h(x))_B}^{-1} \cdot (\nabla h(x))_N\) が導かれる.

よって \(df/dx_N\) に対して \(d_N = - df/dx_N\) のように選ぶことで目的関数の値を減らす方向が導かれる.

厳密な手順としては \(h(x)\) の絶対値を反復ごとにチェックし,許容値を超えていたらステップ幅を小さくする, もしくは \(x_B\)\(x_N\) となっている変数のインデックスを入れ替えるという操作が必要となる.

関連