逐次二次計画法

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

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

基本アルゴリズム[編集]

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

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

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

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

式中で${\displaystyle \lambda }$および${\displaystyle \sigma }$はラグランジュの未定乗数を表す。以下のような${\displaystyle x_{k}}$通常の二次計画問題を解くことで、適切な探索方向${\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(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}$

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

参考資料[編集]

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

外部リンク[編集]

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

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）