逐次線形二次計画法

逐次線形二次計画法（ちくじせんけいにじけいかくほう、英: Sequential linear-quadratic programming、略称：SLQP）とは、目的関数および制約条件を二種類の微分可能関数への近似を行う非線形計画問題に対する反復法の一種である。逐次二次計画法（SQP）に類似した解法であるが、逐次線形二次計画法では一連の最適化部分問題を解く手続きを行っている。両者の違いとしては:

• 逐次二次計画法では、各反復において解かれる部分問題が目的関数が二次関数であり、制約条件が線形の式で表される二次計画問題として記述される。
• 逐次線形二次計画法では、各反復において解かれる部分問題が有効制約を求めるための線形計画問題および各反復のステップを決定するための等式制約付き二次計画問題（EQP）の二種類の問題によって記述される。

部分問題の線形計画問題（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 }$ はラグランジュ乗数を表す。

LPフェーズ

逐次線形二次計画法の線形計画（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}}}$

ここで、${\displaystyle {\cal {A}}_{k}}$ をこの問題の最適解 ${\displaystyle d_{\text{LP}}^{*}}$ に対する（制約条件の各式において ${\displaystyle d_{\text{LP}}^{*}}$ 上でゼロとなる式の集合を表す）有効制約とする。そして、${\displaystyle b_{{\cal {A}}_{k}}}$、${\displaystyle c_{{\cal {A}}_{k}}}$ をそれぞれ ${\displaystyle {\cal {A}}_{k}}$ の要素に対応するベクトル ${\displaystyle b}$、${\displaystyle c}$ とする。

EQPフェーズ

逐次線形二次計画法の等式制約付き二次計画（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})}$ は定数の項であるため、この最小化問題において省略されることがある。

脚注

1. Nocedal & Wright 2006.

参考文献

• Jorge Nocedal; Stephen J. Wright (2006). Numerical Optimization. Springer. doi:10.1007/978-0-387-40065-5. ISBN 9780387303031. NCID BA78604474. LCCN 2006-923897. OCLC 209918411. http://www.ece.northwestern.edu/~nocedal/book/num-opt.html 

関連項目

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