主双対内点法による非線型最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/15 13:02 UTC 版)
「内点法」の記事における「主双対内点法による非線型最適化」の解説
主双対内点法のアイディアは単純で、制約付き非線型最適化問題にも応用が可能である。ここでは単純のために制約式が全て不等式で与えられる非線型最適化問題について考える。 最小化: f ( x ) {\displaystyle f(x)} 条件: c ( x ) ≥ 0 , x ∈ R n , c ( x ) ∈ R m ( 1 ) {\displaystyle c(x)\geq 0,x\in \mathbb {R} ^{n},c(x)\in \mathbb {R} ^{m}~~~~(1)} この最適化問題の対数バリア関数は次のようになる。 B ( x , μ ) = f ( x ) − μ ∑ i = 1 m ln ( c i ( x ) ) ( 2 ) {\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\ln(c_{i}(x))~~~~(2)} ここで μ {\displaystyle \mu } は正のスカラーで、時に「バリア・パラメータ」とも呼ばれる。この μ {\displaystyle \mu } が0に収束していくと、 B ( x , μ ) {\displaystyle B(x,\mu )} が最適解に収束していく。 前述のバリア関数の勾配は g b = g − μ ∑ i = 1 m 1 c i ( x ) ∇ c i ( x ) ( 3 ) {\displaystyle g_{b}=g-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x)~~~~(3)} となる。ただし、 g {\displaystyle g} は元の関数 f ( x ) {\displaystyle f(x)} の勾配であり、 ∇ c i {\displaystyle \nabla c_{i}} は c i {\displaystyle c_{i}} の勾配を表す。 主値 x {\displaystyle x} に加えて、双対値 λ ∈ R m {\displaystyle \lambda \in \mathbb {R} ^{m}} をラグランジュ乗数として導入する。 ∀ i = 1 , … , m , c i ( x ) λ i = μ ( 4 ) {\displaystyle \forall i=1,\ldots ,m,c_{i}(x)\lambda _{i}=\mu ~~~~(4)} この条件は時に摂動相補性条件とも呼ばれる。式(4)を式(3)に適用することにより以下を得る。 g − A T λ = 0 ( 5 ) {\displaystyle g-A^{T}\lambda =0~~~~(5)} ただし、行列 A {\displaystyle A} は制約 c ( x ) {\displaystyle c(x)} のヤコビ行列である。 式(5)が表しているのは関数 f ( x ) {\displaystyle f(x)} の勾配が制約式の勾配により張られる部分空間の中に存在するということである。このとき小さな μ {\displaystyle \mu } による摂動相補性条件は、最適解が c i ( x ) = 0 {\displaystyle c_{i}(x)=0} の境界付近に存在するか、もしくは制約 c i ( x ) {\displaystyle c_{i}(x)} の勾配 g {\displaystyle g} がほとんど0であるということを表している。 式(4)および式(5)に対してニュートン法を用いて ( x , λ ) {\displaystyle (x,\lambda )} を更新していくことを考えると、その更新幅 ( p x , p λ ) {\displaystyle (p_{x},p_{\lambda })} は次の線型方程式の解として与えられる。 ( W − A T Λ A C ) ( p x p λ ) = ( − g + A T λ μ 1 − C λ ) {\displaystyle {\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}}} ただし行列 W {\displaystyle W} は関数 B ( x , μ ) {\displaystyle B(x,\mu )} のヘッセ行列であり、対角行列 Λ {\displaystyle \Lambda } は λ {\displaystyle \lambda } を対角成分に持つ。また、 C {\displaystyle C} は C i i = c i ( x ) {\displaystyle C_{ii}=c_{i}(x)} なる対角行列である。 式(1), (4), および μ > 0 {\displaystyle \mu >0} から λ ≥ 0 {\displaystyle \lambda \geq 0} がそれぞれのステップに課される。この条件を保つために、適切なステップ更新幅 α {\displaystyle \alpha } を選び、 ( x , λ ) → ( x + α p x , λ + α p λ ) {\displaystyle (x,\lambda )\rightarrow (x+\alpha p_{x},\lambda +\alpha p_{\lambda })} とすることで、最適解に向かって収束していく。
※この「主双対内点法による非線型最適化」の解説は、「内点法」の解説の一部です。
「主双対内点法による非線型最適化」を含む「内点法」の記事については、「内点法」の概要を参照ください。
- 主双対内点法による非線型最適化のページへのリンク
