基本アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/24 20:21 UTC 版)
次のような制約つきの非線形最適化問題を考える。 min x f ( x ) s.t. b ( x ) ≥ 0 c ( x ) = 0. {\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}} この問題のラグランジアンは次のようになる。 L ( x , λ , σ ) = f ( x ) − λ T b ( x ) − σ T c ( x ) , {\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),} 式中で λ {\displaystyle \lambda } および σ {\displaystyle \sigma } はラグランジュの未定乗数を表す。以下のような x k {\displaystyle x_{k}} 通常の二次計画問題を解くことで、適切な探索方向 d k {\displaystyle d_{k}} を見つけ出すことができる。 min d f ( x k ) + ∇ f ( x k ) T d + 1 2 d T ∇ x x 2 L ( x k , λ k , σ k ) d s . t . b ( x k ) + ∇ b ( x k ) T d ≥ 0 c ( x k ) + ∇ c ( x k ) T d = 0. {\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}}} 上記の最適化問題の目的関数に含まれる f ( x k ) {\displaystyle f(x_{k})} は定数であるため、実際の最小化の際には無視することができる。
※この「基本アルゴリズム」の解説は、「逐次二次計画法」の解説の一部です。
「基本アルゴリズム」を含む「逐次二次計画法」の記事については、「逐次二次計画法」の概要を参照ください。
- 基本アルゴリズムのページへのリンク
