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

数理計画用語集

SLPSQP

読み:えすえるぴーえすきゅーぴー
関連逐次二次計画法

Sequential Linear Programming Sequential Quadratic Programming の略.逐次線形二次計画法.SLPSQPは制約充足のためのフェイズと目的関数値最小化のフェイズという二つのフェイズから構成され,これらを交互に行う事でペナルティ関数無しに大域的収束性を保証する.各フェイズでは元の問題を線形計画問題,あるいは二次計画問題で近似し,それらの解を用いて探索を行う.

ここでは簡単のため,不等式制約は各変数の下限制約のみとする.制約充足のフェイズでは次の問題を繰り返し解く.

最小化 equation

条 件 equation

equationは零行列あるいはラグランジュ関数のヘッセ行列,または,その近似行列である.条件式が与えられた上下限制約のもとでのequationの一次近似になっているため,上記問題の解方向に直線探索をすると,制約の充足度を向上させることができる.また,equationをラグランジュ関数のヘッセ行列,あるいは近似行列とすれば,反復点equationが解に近い時には通常の信頼領域二次計画法と同等の反復点を生成する事になり,超一次収束する.

制約充足のフェイズが,実行可能領域への接近を目標としている事に対し,目的関数値最小化フェイズでは等式制約が定める領域の接方向へと移動し目的関数値の最小化を目指す.

具体的には,実行可能領域へ近付くステップequationと,目的関数の減少を意図した接方向へのステップequationとの組合せequationを探索方向の候補とする.equationは次の問題の解として取得する.

最小化 equation

条 件 equation

ここでは制約充足フェイズの場合と同様にequationは零行列あるいはラグランジュ関数のヘッセ行列,または,その近似行列とする.この問題はequationから始めequationが一定の制約充足度を満たすようになるまでequationを半減させつつ繰り返し解く.この内部反復により最終的に得られたequationequationとして,equationによる目的関数の減少量が,その二次近似関数の減少量と比べて十分だった場合は,equationを拡大しequationとする.逆に一定比率以上で二次近似関数の減少量の方が上回った時はequationとして,どちらでもない場合はequationとする.そして次の反復点候補equationが現在点での目的関数値equationをより減少させるのならばequation,そうでなければequationとして次の反復へと進む.

制約充足フェイズ,目的関数値最小化フェイズにおいてequationがラグランジュ関数のヘッセ行列,あるいは近似行列であった場合,各反復において二次計画問題を解くことになる.問題によっては,二次計画問題求解が高コストになる事もある.そのために,Numerical Optimizerでは,この二次計画問題を直接解くのではなく,線形計画問題と,その結果得られる等式のみの二次計画問題の解を組合せ,近似的な解を構成するという工夫をしている.