逐次二次計画法

Optimization algorithm

逐次二次計画法（SQP）は、制約付き非線形最適化のための反復法であり、ラグランジュ・ニュートン法としても知られています。SQP法は、目的関数と制約条件が2回連続微分可能であるものの、必ずしも凸ではない数学的問題に用いられます。

SQP法は、一連の最適化部分問題を解きます。各部分問題は、制約条件の線形化を条件として、目的関数の二次モデルを最適化するものです。問題に制約条件がない場合、この方法は目的関数の勾配がゼロになる点を求めるニュートン法に帰着します。問題に等式制約のみがある場合、この方法は問題の一次最適条件、すなわちカルシュ・キューン・タッカー条件にニュートン法を適用することと等価です。

アルゴリズムの基礎

基本的なSQPアルゴリズムを示す概要図

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

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

ここで、、、およびです。 ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m_{I}}}$ ${\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m_{E}}}$

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

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

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

等式制約の場合

問題に不等式制約がない場合（つまり、）、1次最適条件（KKT条件とも呼ばれる）は、ニュートン法を用いて反復的に解くことができる非線形方程式の集合です。ニュートン法は、現在の反復 においてKKT条件を線形化し、ニュートンステップ について次の式を与えます。 ${\displaystyle m_{I}=0}$ ${\displaystyle \nabla {\mathcal {L}}(x,\sigma )=0}$ ${\displaystyle \left[x_{k},\sigma _{k}\right]^{T}}$ ${\displaystyle \left[d_{x},d_{\sigma }\right]^{T}}$

${\displaystyle {\begin{bmatrix}d_{x}\\d_{\sigma }\end{bmatrix}}=-[\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})]^{-1}\nabla _{x}{\mathcal {L}}(x_{k},\sigma _{k})=-{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})&\nabla g(x_{k},\sigma _{k})\\\nabla g^{T}(x_{k},\sigma _{k})&0\end{bmatrix}}^{-1}{\begin{bmatrix}\nabla f(x_{k})+\sigma _{k}\nabla g(x_{k})\\g(x_{k})\end{bmatrix}}}$、

ここで、はラグランジアンのヘッセ行列、はそれぞれ主変位と双対変位である。ラグランジアンヘッセ行列は明示的に逆行列化されず、代わりに線形方程式が解かれることに注意されたい。 ${\displaystyle \nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})}$ ${\displaystyle d_{x}}$ ${\displaystyle d_{\sigma }}$

ラグランジュ・ヘッセ行列が正定値行列でない場合、ニュートンステップは存在しないか、局所的最小値ではなく局所的最大値または鞍点となる停留点を特徴付ける可能性があります。この場合、ラグランジュ・ヘッセ行列は正規化される必要があります。例えば、結果の行列が正定値行列となるように、恒等関数の倍数を加えることができます。 ${\displaystyle \nabla ^{2}{\mathcal {L}}(x_{k},\sigma _{k})}$

プライマル-デュアル変位を取得するための別の方法は、現在の反復で元の問題のローカル二次モデルを構築して解くことです。

${\displaystyle {\begin{array}{rl}\min \limits _{d_{x}}&f(x_{k})+\nabla f(x_{k})^{T}d_{x}+{\frac {1}{2}}d_{x}^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})d_{x}\\\mathrm {s.t.} &g(x_{k})+\nabla g(x_{k})^{T}d_{x}=0.\end{array}}}$

この二次問題の最適条件は、元の問題の線形化されたKKT条件に対応する。上記の式の項は、演算子の下で定数であるため省略できる点に注意されたい。 ${\displaystyle f(x_{k})}$ ${\displaystyle \min \limits _{d}}$

不平等制約の場合

不等式制約（）が存在する場合、前のセクションで導入された局所二次モデルの定義を自然に拡張することができます。 ${\displaystyle m_{I}>0}$

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

SQPアルゴリズム

SQPアルゴリズムは最初の反復から開始します。各反復において、QPサブ問題が構築され、解かれます。得られたニュートンステップ方向は、現在の反復を更新するために用いられます。 ${\displaystyle (x_{0},\lambda _{0},\sigma _{0})}$ ${\displaystyle [d_{x},d_{\lambda },d_{\sigma }]^{T}}$

${\displaystyle \left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+[d_{x},d_{\lambda },d_{\sigma }]^{T}.}$

このプロセスは、何らかの収束基準が満たされるまで繰り返されます。 ${\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)
• acados (Python、MATLAB、Simulink、Octave へのインターフェイスを備えた C) は、最適制御で生じる問題構造に合わせた SQP メソッドを実装しますが、一般的な非線形プログラムにも取り組みます。

商業用

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

参照

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

注記

1. Jorge Nocedal、Stephen J. Wright (2006). 数値最適化. Springer. ISBN 978-0-387-30303-1。
2. Kraft, Dieter (1994年9月). 「アルゴリズム733: 最適制御計算のためのTOMP–Fortranモジュール」. ACM Transactions on Mathematical Software . 20 (3): 262– 281. CiteSeerX 10.1.1.512.2567 . doi :10.1145/192115.192124. S2CID  16077051. 2019年2月1日閲覧。 
3. 「NLoptアルゴリズム：SLSQP」。Read the Docs。1988年7月。 2019年2月1日閲覧。
4. KNITRO ユーザーガイド: アルゴリズム

参考文献

• 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。
• ホルヘ・ノセダル、スティーブン・J・ライト（2006年）『数値最適化』シュプリンガー社、ISBN 978-0-387-30303-1。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Sequential_quadratic_programming&oldid=1302265667"