逐次二次計画法

逐次二次計画法（ちくじにじけいかくほう、英: sequential quadratic programming）は非線形最適化のための反復解法の一つである。逐次二次計画法は目的関数と制約関数の両方が二階微分可能であるような問題に対して使われる。

逐次二次計画法は逐次的に二次の部分最適化問題を解く。それぞれの部分最適化問題は最適解に向かう探索方向を未知数とする二次計画問題になる。この際、問題に与えられている制約は探索方向に対して線形の条件に置き換えられる。問題が制約なしの最適化であるならば、勾配がゼロである点を見つけ出す一般のニュートン法と同様の定式化となる。また、問題が等式制約のみを持つ場合には、カルーシュ・クーン・タッカー条件（KKT条件）に対するニュートン法と同様の定式化となる。逐次二次計画法はNPSOLやSNOPT、NLPQL、OPSYC、OPTIMA、MATLAB、GNU Octave等、多数のプログラム関数ライブラリに実装されている。

基本アルゴリズム

次のような制約つきの非線形最適化問題を考える。

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

この問題のラグランジアンは次のようになる。

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

式中で$\lambda$および$\sigma$はラグランジュの未定乗数を表す。以下のような$x_{k}$通常の二次計画問題を解くことで、適切な探索方向$d_{k}$を見つけ出すことができる。

${\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(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}$

上記の最適化問題の目的関数に含まれる$f(x_{k})$は定数であるため、実際の最小化の際には無視することができる。

参考資料

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

外部リンク

• scipy.optimize.minimize (PythonのScipyによるSLSQPの実装を含む。制約つき問題に対して適用される)