逐次二次計画法

逐次二次計画法( SQP ) は、準ニュートン法とも言える制約付き非線形最適化のための反復法です。SQP 法は、目的関数と制約が 2 回連続微分可能であるが、必ずしも凸ではない数学的問題に使用されます。

SQP 法は、一連の最適化サブ問題を解きます。各サブ問題は、制約の線形化を条件として目的の 2 次モデルを最適化します。問題に制約がない場合、この方法は、目的の勾配が消える点を見つけるニュートン法に簡略化されます。問題に等式制約のみがある場合、この方法は、問題の 1 次最適条件、またはKarush-Kuhn-Tucker 条件にニュートン法を適用することと同等です。

次の形式の 非線形計画問題を考えてみましょう。

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{subject to}}&h(x)\geq 0\\&g(x)=0.\end{array}}}$

この問題のラグランジアンは^{[1]である。}

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)+\lambda h(x)+\sigma g(x),}$

ここで、 およびはラグランジュ乗数です。 ${\displaystyle \lambda}$${\displaystyle \sigma}$

標準的なニュートン法では、次の式を反復して解を求めます。ここで、 はヘッセ行列を表します。 ${\displaystyle \nabla {\mathcal {L}}(x,\lambda ,\sigma )=0}$${\displaystyle \nabla _{xx}^{2}}$

${\displaystyle {\begin{bmatrix}x_{k+1}\\\lambda _{k+1}\\\sigma _{k+1}\end{bmatrix}}={\begin{bmatrix}x_{ k}\\\lambda _{k}\\\sigma _{k}\end{bmatrix}}-\アンダーブレース{{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}&\nabla h&\nabla g\\\nabla h^{T}&0&0\\\nabla g^{T} &0&0\end{bmatrix}}^{-1}} _{\nabla ^{2}{\mathcal {L}}}\アンダーブレース{\begin{bmatrix}\nabla f+\lambda _{k}\nabla h+\sigma _{k}\nabla g\\h\\g\end{bmatrix}} _{\nabla {\mathcal {L}}}}$。

しかし、行列は一般に特異であるため（したがって逆行列が不可能）、ニュートンステップを直接計算することはできません。代わりに、基本的な逐次二次計画アルゴリズムは、二次計画サブ問題 の解として、反復における適切な探索方向を定義します。${\displaystyle \nabla^{2}{\mathcal{L}}}$ ${\displaystyle d_{k}=\left(\nabla _{xx}^{2}{\mathcal {L}}\right)^{-1}\nabla {\mathcal {L}}}$${\displaystyle d_{k}}$${\displaystyle (x_{k},\lambda _{k},\sigma _{k})}$

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2 }}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {st} &h(x_{k})+\nabla h(x_{k})^{T}d\geq 0\\&g(x_{k})+\nabla g(x_{k})^{T}d=0.\end{配列}}}$

ここで、2 次形式はラグランジアンのヘッセ行列で形成されます。上記の式の項は演算子の下で定数であるため、最小化問題では省略できることに注意してください。 ${\displaystyle f(x_{k})}$${\displaystyle \min \limits _{d}}$

まとめると、SQP アルゴリズムは、まず初期反復 を選択してから、 と を計算することから始まります。次に、QP サブ問題が構築され、解かれて、を使用して親問題の反復を更新するために使用されるニュートン ステップ方向が見つかります。このプロセスは、親問題が収束テストを満たすまで繰り返されます。 ${\displaystyle (x_{0},\lambda _{0},\sigma _{0})}$${\displaystyle \nabla^{2}{\mathcal{L}}(x_{0},\lambda_{0},\sigma_{0})}$${\displaystyle \nabla {\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})}$${\displaystyle d_{0}}$${\displaystyle \left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+d_{k}}$${\displaystyle k=0,1,2,\ldots }$

SQP アルゴリズムの実際の実装は、上記の基本バージョンよりもはるかに複雑です。SQP を実際のアプリケーションに適応させるには、次の課題に対処する必要があります。

• 実行不可能な QP サブ問題の可能性。
• QP サブ問題で悪いステップが生成されます。つまり、ターゲットを削減できないか、制約違反が増加するステップです。
• ターゲット/制約が二次/線形モデルから大きく逸脱したために反復が中断されました。

これらの課題を克服するために、通常はさまざまな戦略が採用されます。

• 制約付きソリューションへの進捗状況を評価するメリット関数、またはフィルター メソッドの使用。
• 二次モデルと実際のターゲット間の偏差を管理するには、領域またはライン検索方法を信頼します。
• 実行不可能なサブ問題を処理するための特別な実行可能性回復フェーズ、または実行不可能性を徐々に減らすためのL1ペナルティ付きサブ問題の使用

これらの戦略はさまざまな方法で組み合わせることができ、多様な SQP メソッドが実現します。

• 逐次線形計画法
• 逐次線形二次計画法
• 拡張ラグランジアン法

SQP メソッドは、 MATLABやGNU Octaveなどのよく知られた数値環境に実装されています。また、オープン ソースを含む多数のソフトウェア ライブラリも存在します。

• SciPy (科学的 Python の事実上の標準) には、scipy.optimize.minimize(method='SLSQP') ソルバーがあります。
• NLopt（C/C++実装、Julia、Python、R、MATLAB/Octaveを含む多数のインターフェース付き）、最適制御パッケージの一部としてDieter Kraftによって実装され、SG Johnsonによって修正された。^{[2] [3]}
• ALGLIB SQP ソルバー (C++、C#、Java、Python API)

商業

• ラボビュー
• KNITRO ^[4] (C、C++、C#、Java、Python、Julia、Fortran)
• NPSOL (フォートラン)
• SNOPT (Fortran)
• NLPQL (Fortran)
• マテリアライズド
• スアンシュ（ジャワ）

• ニュートン法
• セカント法
• モデル予測制御

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). 数値最適化: 理論と実践の側面。Universitext (1997 年フランス語版の翻訳の第 2 版)。ベルリン: Springer -Verlag。pp. xiv+490。doi :10.1007 / 978-3-540-35447-5。ISBN 978-3-540-35445-1. MR  2265882。
• Jorge Nocedal および Stephen J. Wright (2006)。数値最適化。Springer。ISBN 978-0-387-30303-1。

• NEOS ガイドの逐次二次計画法