トップ > 数理計画用語集 > GRG

数理計画用語集

GRG

読み:じーあーるじー

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

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

このような発想は古くは線形計画法における単体法に起源があると言える.実際はステップ方向を決めるために上記の発想が適用されるが,ステップサイズを決める部分は主双対内点法逐次二次計画法と同様である.

準備としてスラック変数などを導入し以下の形の問題に変形する.

 変数 equation

最小化 equation

制約式 equation

このときステップ方向を以下のように求める.変数をequationのようにequation個とequation個に分ける.同様にequationequationのように分ける.この時equationとなるようにequationequationが関係付けられているとして,equationの変分を考えると equation という等式を得る.

よって equation が成り立つことで,

equation が導かれる.

よって equation に対して

equationのように選ぶことで目的関数の値を減らす方向が導かれる.

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