エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

等式制約あり凸最適化問題に対するニュートン法とその等式制約を除去した問題に対するニュートン法との関係をまとめる

数学 数理最適化

本記事は以下の過去記事の内容を用います．

等式制約あり凸最適化問題の基礎をまとめる - エンジニアを目指す浪人のブログ

凸最適化問題の等式制約の除去についてまとめる - エンジニアを目指す浪人のブログ

等式制約あり凸最適化問題に対するニュートン法と，ニュートンステップの定義，解釈，性質をまとめる - エンジニアを目指す浪人のブログ

制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義，解釈，性質をまとめる - エンジニアを目指す浪人のブログ


勉強を進めていて，等式制約あり凸最適化問題に対するニュートン法とその等式制約を除去した問題に対するニュートン法の関係についてモヤモヤしてしまったので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の10章2節(の3)をベースにしています．

=================================================================================

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. KKT行列とヘッセ行列の正則性
{\displaystyle \; } 2. ニュートンステップの関係
{\displaystyle \; } 3. ニュートンデクリメントの関係


[ 0. 準備 ]

冒頭の過去記事(等式制約あり凸最適化問題の基礎)(1.1)を再掲します．{\displaystyle f : \mathbb{R}^n \to \mathbb{R}}，{\displaystyle p \times n } 行列 {\displaystyle A, \ x \in \mathbb{R}^n, \ b \in \mathbb{R}^p } です．{\displaystyle f } は凸で二階微分可能とします．{\displaystyle A } は行フルランクとします．

(0.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ Ax=b }

冒頭の過去記事(凸最適化問題の等式制約の除去)事実.より，(0.1)を以下の制約なし凸最適化問題に縮約(reduce)することができます．{\displaystyle n \times (n-p) } 行列 {\displaystyle F } の列は行列 {\displaystyle A } の零空間 {\displaystyle \mathcal{N}(A) } の基底です．

(0.2)
{\displaystyle \mathrm{minimize} \;\;\;\; \tilde{f} (z) = f (Fz + \hat{x}) \;\;\;\;\;\; \left( \{ x \in \mathbb{R}^n \ | \ Ax = b \} = \{ Fz + \hat{x} \ | \ z \in \mathbb{R}^{n-p},\ A \hat{x} = b \} \right) }

{\displaystyle \tilde{f} } の勾配とヘッセ行列は以下です．

(0.3){\displaystyle \;\;\; \nabla \bar{f}(z) = F^T \nabla f( Fz + \hat{x} ) \;\;\;\;\;\;\;\;\; \because } 連鎖律(文献[2])

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = F^T \nabla f( x ) }

(0.4){\displaystyle \;\;\; \nabla^2 \bar{f}(z) = F^T \nabla^2 f( Fz + \hat{x} ) \ F \;\;\; \because } 連鎖律(文献[2])

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = F^T \nabla^2 f( x ) \ F }


[ 1. KKT行列とヘッセ行列の正則性 ]

冒頭の過去記事(等式制約あり凸最適化問題に対するニュートン法)(1.1.3)にあるように，問題(0.1)にニュートン法を適用するときのKKT行列は以下です．

(1.1){\displaystyle \;\;\; M_{ \mathrm{KKT} } = \begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} }


等式制約あり問題のKKT行列と縮約した制約なし問題の目的関数のヘッセ行列について以下が成り立ちます．冒頭の過去記事(等式制約あり凸最適化問題の基礎)(2.9)(2.10)を用いて簡単に示すことができます．

(1.2){\displaystyle \;\;\; M_{ \mathrm{KKT} } \ は正則 \ \Leftrightarrow \ \nabla^2 \bar{f}(z) \ は正則 }


[ 2. ニュートンステップの関係 ]

冒頭の過去記事(等式制約あり凸最適化問題に対するニュートン法)(1.1.3)にあるように，問題(0.1)に対するニュートンステップのみたすKKT系は以下です．

(2.1){\displaystyle \;\;\; \begin{bmatrix} \nabla^2 f(x) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} \Delta x_{\mathrm{nt}} \\ w \end{bmatrix} = \begin{bmatrix} - \nabla f(x) \\ 0 \end{bmatrix} }


冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.1)にあるように，制約なし問題(0.2)のニュートンステップは以下です．

(2.2){\displaystyle \;\;\; \Delta z_{\mathrm{nt}} = - \nabla^2 \tilde{f} (z)^{-1} \nabla \tilde{f}(z) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \left[ F^T \nabla^2 f( x ) \ F \right] \ F^T \nabla f( x ) \;\;\; \because } (0.3)(0.4)


{\displaystyle \Delta x_{\mathrm{nt}} } と {\displaystyle \Delta z_{\mathrm{nt}} } には以下の関係があります．

(2.3){\displaystyle \;\;\; \Delta x_{\mathrm{nt}} = F \Delta z_{\mathrm{nt}} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - F \left[ F^T \nabla^2 f( x ) \ F \right] \ F^T \nabla f( x ) }

{\displaystyle w } を以下とします．

(2.4){\displaystyle \;\;\; w = - (A A^T)^{-1} A \left[ \nabla f(x) + \nabla^2 f(x) \Delta x_{\mathrm{nt}} \right] }


実際に(2.3)の {\displaystyle \Delta x_{\mathrm{nt}} } と(2.4)の {\displaystyle w } がKKT系(2.1)をみたすことを示します．

(2.5){\displaystyle \;\;\; \begin{bmatrix} F^T \\ A \end{bmatrix} \left( \nabla f(x) \Delta x_{\mathrm{nt}} + A^T w + \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\; = \begin{bmatrix} F^T \nabla^2 f(x) \Delta x_{\mathrm{nt}} + F^T A^T w + F^T \nabla f(x) \\ A \nabla^2 f(x) \Delta x_{\mathrm{nt}} + A A^T w + A \nabla f(x) \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\; = \begin{bmatrix} F^T \nabla^2 f(x) \Delta x_{\mathrm{nt}} + F^T A^T w + F^T \nabla f(x) \\ 0 \end{bmatrix} \;\;\; \because } (2.4)

{\displaystyle \;\;\;\;\;\;\;\;\; = \begin{bmatrix} F^T \nabla^2 f(x) \Delta x_{\mathrm{nt}} + (AF) w + F^T \nabla f(x) \\ 0 \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\; = \begin{bmatrix} F^T \nabla^2 f(x) \Delta x_{\mathrm{nt}} + F^T \nabla f(x) \\ 0 \end{bmatrix} \;\;\; \because } {\displaystyle F } の列は {\displaystyle \mathcal{N}(A) } の基底より {\displaystyle A F = 0 }

{\displaystyle \;\;\;\;\;\;\;\;\; = 0 \;\;\; \because } (2.3)

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ \nabla f(x) \Delta x_{\mathrm{nt}} + A^T w + \nabla f(x) = 0 \;\;\; \because \begin{bmatrix} F^T \\ A \end{bmatrix} \ は正則 }

(2.6){\displaystyle \;\;\; A x_{\mathrm{nt}} = A F z_{\mathrm{nt}} \;\;\; \because } (2.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 0 \;\;\;\;\;\;\;\; \because A F = 0 }


[ 3. ニュートンデクリメントの関係 ]

{\displaystyle \tilde{f} } の {\displaystyle z } でのニュートンデクリメントは {\displaystyle f } の {\displaystyle x } でのニュートンデクリメントと同じです．

(3.1){\displaystyle \;\;\; \tilde{\lambda} (z)^2 = \Delta z_{ \mathrm{nt} }^T \nabla^2 \tilde{f}(z) \Delta z_{ \mathrm{nt} } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \Delta z_{ \mathrm{nt} }^T F^T \nabla^2 f( x ) \ F \Delta z_{ \mathrm{nt} } \;\;\; \because } (0.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = (F \Delta z_{ \mathrm{nt} })^T \nabla^2 f( x ) \ F \Delta z_{ \mathrm{nt} } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \Delta x_{ \mathrm{nt} }^T \nabla^2 f( x ) \ \Delta x_{ \mathrm{nt} } \;\;\; \because } (2.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \lambda (x)^2 }


=================================================================================

以上，等式制約あり凸最適化問題に対するニュートン法とその等式制約を除去した問題に対するニュートン法との関係をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Stanford University Stephen Boyd先生のノート http://210.43.0.57/moocresource/data/20100601/U/stanford201001009/review7_single.pdf