逐次線形二次計画法

逐次線形二次計画法( SLQP ) は、目的関数と制約が 2 回連続微分可能な非線形最適化問題に対する反復法です。逐次二次計画法( SQP )と同様に、SLQP は一連の最適化サブ問題を解くことで進行します。2 つのアプローチの違いは次のとおりです。

• SQPでは、各サブ問題は2次計画問題であり、目的関数の2次モデルは制約の線形化に従う。
• SLQPでは、各ステップで2つのサブ問題が解かれる。アクティブセットを決定するために使用される線形計画法（LP）と、合計ステップを計算するために使用される等式制約二次計画法（EQP）である。

この分解により、SLQP は大規模な最適化問題に適しており、効率的な LP および EQP ソルバーが利用可能で、これらの問題は本格的な二次計画よりも簡単に拡張できます。

これは準ニュートン法と関連しているものの、異なるものと考えられる。

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

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}}$

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

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),}$

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

SLQP の LP フェーズでは、次の線形計画が解かれます。

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}$

この問題の最適値におけるアクティブ セット、つまり で 0 に等しい制約の集合をと表します。 およびの要素に対応するおよびのサブベクトルをとで表します。 ${\displaystyle {\cal {A}}_{k}}$${\displaystyle d_{\text{LP}}^{*}}$${\displaystyle d_{\text{LP}}^{*}}$${\displaystyle b_{{\cal {A}}_{k}}}$${\displaystyle c_{{\cal {A}}_{k}}}$${\displaystyle b}$${\displaystyle c}$${\displaystyle {\cal {A}}_{k}}$

SLQP の EQP フェーズでは、ステップの 検索方向は次の等式制約付き二次計画法を解くことによって得られます。${\displaystyle d_{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 {s.t.} &b_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}}$

上記の目的関数の項は定数であるため、最小化問題では省略できることに注意してください。 ${\displaystyle f(x_{k})}$

• ニュートン法
• セカント法
• 逐次線形計画法
• 逐次二次計画法

• Jorge Nocedal および Stephen J. Wright (2006)。数値最適化。Springer。ISBN 0-387-30303-0。