逐次二次計画法
逐次二次計画法（Sequential Quadratic Programming, SQP）は、非線形最適化問題を解決するための強力な反復アルゴリズムです。特に、目的関数と制約関数がともに二階微分可能であるような問題に対して有効です。
SQPは、与えられた非線形最適化問題を、逐次的に解かれる一連の二次計画（Quadratic Programming, QP）問題に変換します。各反復において、現在の解の周辺で目的関数と制約関数を二次近似し、その近似された問題（QP問題）を解くことで、次の探索方向を決定します。このアプローチは、問題が制約なしの場合にはニュートン法に、等式制約のみを持つ場合にはカルーシュ・クーン・タッカー条件（KKT条件）に対するニュートン法に類似した定式化になります。
制約付き非線形最適化問題は一般的に以下のように表されます。
math
\begin{array}{rl}
\min \limits _{x}&f(x)\\
s.t.&b(x) \geq 0\\
&c(x)=0.\end{array}
ここで、`f(x)`は目的関数、`b(x)`は不等式制約、`c(x)`は等式制約を表します。この問題のラグランジアンは以下のように定義されます。
math
{\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x)
ここで、λとσはそれぞれ不等式制約と等式制約に対応するラグランジュ乗数です。
SQPアルゴリズムでは、現在の解`xk`における次の探索方向`dk`を決定するために、以下の二次計画問題を解きます。
math
\begin{array}{rl}
\min \limits _{d}&f(x_{k})+
abla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}
abla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\
s.t.&b(x_{k})+
abla b(x_{k})^{T}d\geq 0\\
&c(x_{k})+
abla c(x_{k})^{T}d=0.\end{array}
このQP問題では、目的関数は現在の解`xk`における目的関数の線形近似とラグランジアンの二次のヘッセ行列による近似の和です。制約条件は、元の非線形制約を線形近似したものです。この問題を解くことで、探索方向`dk`とラグランジュ乗数の更新値`λk+1`, `σk+1`が得られます。これにより、次の反復における解`xk+1`が`xk + dk`として更新されます。最適解に到達するまで、このプロセスが繰り返されます。
SQPは、その効率性と汎用性から、様々な数値計算ライブラリに実装されています。例えば、NPSOL、SNOPT、NLPQL、OPSYC、OPTIMAなどの専用ソルバーや、MATLAB、GNU Octave、PythonのSciPyライブラリにも含まれています。これにより、工学、経済学、機械学習など、幅広い分野の最適化問題に適用されています。
逐次二次計画法は、非線形最適化問題に対する強力な解法であり、その反復的なアプローチは、複雑な問題に対しても効率的な解を求めることを可能にします。特に、二階微分可能な関数を扱う場合にその能力を発揮し、現代の科学技術における最適化問題解決に不可欠なツールとなっています。
逐次二次計画法の基本原理
SQPは、与えられた非線形最適化問題を、逐次的に解かれる一連の二次計画（Quadratic Programming, QP）問題に変換します。各反復において、現在の解の周辺で目的関数と制約関数を二次近似し、その近似された問題（QP問題）を解くことで、次の探索方向を決定します。このアプローチは、問題が制約なしの場合にはニュートン法に、等式制約のみを持つ場合にはカルーシュ・クーン・タッカー条件（KKT条件）に対するニュートン法に類似した定式化になります。
アルゴリズムの詳細
制約付き非線形最適化問題は一般的に以下のように表されます。
math
\begin{array}{rl}
\min \limits _{x}&f(x)\\
s.t.&b(x) \geq 0\\
&c(x)=0.\end{array}
ここで、`f(x)`は目的関数、`b(x)`は不等式制約、`c(x)`は等式制約を表します。この問題のラグランジアンは以下のように定義されます。
math
{\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x)
ここで、λとσはそれぞれ不等式制約と等式制約に対応するラグランジュ乗数です。
SQPアルゴリズムでは、現在の解`xk`における次の探索方向`dk`を決定するために、以下の二次計画問題を解きます。
math
\begin{array}{rl}
\min \limits _{d}&f(x_{k})+
abla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}
abla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\
s.t.&b(x_{k})+
abla b(x_{k})^{T}d\geq 0\\
&c(x_{k})+
abla c(x_{k})^{T}d=0.\end{array}
このQP問題では、目的関数は現在の解`xk`における目的関数の線形近似とラグランジアンの二次のヘッセ行列による近似の和です。制約条件は、元の非線形制約を線形近似したものです。この問題を解くことで、探索方向`dk`とラグランジュ乗数の更新値`λk+1`, `σk+1`が得られます。これにより、次の反復における解`xk+1`が`xk + dk`として更新されます。最適解に到達するまで、このプロセスが繰り返されます。
実装と応用
SQPは、その効率性と汎用性から、様々な数値計算ライブラリに実装されています。例えば、NPSOL、SNOPT、NLPQL、OPSYC、OPTIMAなどの専用ソルバーや、MATLAB、GNU Octave、PythonのSciPyライブラリにも含まれています。これにより、工学、経済学、機械学習など、幅広い分野の最適化問題に適用されています。
まとめ
逐次二次計画法は、非線形最適化問題に対する強力な解法であり、その反復的なアプローチは、複雑な問題に対しても効率的な解を求めることを可能にします。特に、二階微分可能な関数を扱う場合にその能力を発揮し、現代の科学技術における最適化問題解決に不可欠なツールとなっています。
参考資料
- - 逐次線形計画
- - セカント法
- - ニュートン法
- - 二次計画問題
外部リンク
- - scipy.optimize.minimize (PythonのScipyによるSLSQPの実装を含む。制約つき問題に対して適用される)
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。