逐次二次計画法のソースを表示

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

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

==基本アルゴリズム==
次のような制約つきの非線形最適化問題を考える。

:<math>\begin{array}{rl}
\min\limits_{x} & f(x) \\
\mbox{s.t.} & b(x) \ge 0 \\
  & c(x) = 0.
\end{array}</math>

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

:<math>\mathcal{L}(x,\lambda,\sigma) = f(x) - \lambda^T b(x) - \sigma^T c(x),</math>

式中で<math>\lambda</math>および<math>\sigma</math>は[[ラグランジュの未定乗数]]を表す。以下のような<math>x_k</math>通常の二次計画問題を解くことで、適切な探索方向<math>d_k</math>を見つけ出すことができる。

:<math>\begin{array}{rl} \min\limits_{d} & f(x_k) + \nabla f(x_k)^Td + \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)^Td \ge 0 \\
  & c(x_k) + \nabla c(x_k)^T d = 0. \end{array}</math>

上記の最適化問題の目的関数に含まれる<math>f(x_k)</math>は定数であるため、実際の最小化の際には無視することができる。

==参考資料==
* [[逐次線形計画法]]
* [[セカント法]]
* [[ニュートン法]]
* [[二次計画問題]]

==外部リンク==
* [http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.optimize.minimize.html scipy.optimize.minimize]（PythonのScipyによるSLSQPの実装を含む。制約つき問題に対して適用される）

{{最適化アルゴリズム}}

{{デフォルトソート:ちくしにしけいかくほう}}
[[Category:最適化アルゴリズム]]
[[Category:数学に関する記事]]