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

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

等式制約あり凸最適化問題に対するニュートン法と，ニュートンステップの定義，解釈，性質をまとめる

数学 数理最適化

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

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

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

降下法の枠組みと，厳密直線探索，バックトラッキング直線探索の概要をまとめる - エンジニアを目指す浪人のブログ


等式制約あり凸最適化問題に対するニュートン法(Newton's method)のアルゴリズムとその数理的な基礎についてまとめておくことにしました．Boyd and Vandenberghe(2004)の10章2節(の1と2)をベースにしています．

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

目次

{\displaystyle \; } 0. 準備

{\displaystyle \; } 1. ニュートンステップの定義と解釈と性質
{\displaystyle \;\;\; } 1.1. 目的関数の二次近似の最適点
{\displaystyle \;\;\; } 1.2. 一次の最適性条件の一次近似の解
{\displaystyle \;\;\; } 1.3. ニュートンデクリメント
{\displaystyle \;\;\; } 1.4. 実行可能な降下方向
{\displaystyle \;\;\; } 1.5. アフィン不変性

{\displaystyle \; } 2. アルゴリズム



[ 0. 準備 ]

冒頭の過去記事(等式制約あり凸最適化問題の基礎)[ 0. 準備 ][ 1. 等式制約あり凸最小化問題 ]と同じです．

冒頭の過去記事(制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義)の内容も必要です．

冒頭の過去記事(降下法の枠組み)の内容も必要です．



[ 1. ニュートンステップの定義と解釈と性質 ]

[ 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 } です．

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

{\displaystyle f } の {\displaystyle x } のまわりのテイラー展開の二次近似 {\displaystyle \hat{f} } を考えると，問題(1.1.1)は以下で近似できます．これは {\displaystyle v } についての凸最適化問題です．また，冒頭の過去記事(等式制約あり凸最適化問題の基礎)(2.1)で表現することができ，解析的に解くことができます．

(1.1.2)
{\displaystyle \mathrm{minimize} \;\;\;\; \hat{f}(x + v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v }
{\displaystyle \mathrm{subject \; to} \;\;\ A(x+v)=b \;\;\; ( \Leftrightarrow \ Av=0 ) }


KKT行列は正則であると仮定し，等式制約あり凸二次最小化問題(1.1.2)の解析的な解としてのニュートンステップ {\displaystyle \Delta x_{\mathrm{nt}} } を定義していきます．いいかえると，ニュートンステップは {\displaystyle f } の {\displaystyle x } のまわりの二次近似 {\displaystyle \hat{f} } を最小化するために {\displaystyle x } に加えるべきものです．

KKT系は以下となります．

(1.1.3){\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} }

ニュートンステップはKKT行列が正則となる点上において(のみ)定義します．このときニュートンステップを得ることができます．

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


制約なし凸最適化問題に対するニュートン法と同様の考察ができます．関数 {\displaystyle f(x) } が二次関数であれば，{\displaystyle x + \Delta x_\mathrm{nt} } は等式制約あり問題の最適点に一致し，{\displaystyle w } は元の問題(1.1.1)の双対問題の最適点です．{\displaystyle x } が {\displaystyle x^* } に近いとき {\displaystyle \hat{f} } は {\displaystyle f } の正確な近似になっています． したがって，点 {\displaystyle x } が最適点 {\displaystyle x^* } に近いとき {\displaystyle x + \Delta x_\mathrm{nt} } は {\displaystyle x^* } の非常に良い見積もりになります．またこのとき {\displaystyle w } は双対問題の最適点 {\displaystyle \nu^* } の非常によい見積もりになります．


[ 1.2. 一次の最適性条件の一次近似の解 ]

冒頭の過去記事(等式制約あり凸最適化問題の基礎)(1.5)(1.6)にある，KKT方程式を再掲します．

(1.2.1){\displaystyle \;\;\; A x^* = b }

(1.2.2){\displaystyle \;\;\; \nabla f(x^*) + A^T \nu^* = 0 }

{\displaystyle \Delta x_\mathrm{nt}, \ w } はこの最適性条件の一次近似の解として解釈することができます．{\displaystyle x + \Delta x_\mathrm{nt},\ w } をそれぞれ {\displaystyle x^* , \ \nu^* } に代入します．また {\displaystyle \nabla f(x) } を {\displaystyle x } のまわりのテイラー展開の一次近似を {\displaystyle \hat{f} } として以下を得ます．これらはKKT系(1.1.3)と同じものです．

(1.2.3){\displaystyle \;\;\; A (x + \Delta x_\mathrm{nt}) = b }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ A \Delta x_\mathrm{nt} = 0 }

(1.2.4){\displaystyle \;\;\; \nabla f(x + \Delta x_\mathrm{nt}) + A^T w \approx \nabla f(x) + \nabla^2 f(x) \Delta x_\mathrm{nt} + A^T w }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 0 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \Leftrightarrow \ \nabla^2 f(x) \Delta x_\mathrm{nt} + A^T w = - \nabla f(x) }


[ 1.3. ニュートンデクリメント ]

等式制約あり問題のニュートンデクリメントは，冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.3)と同じく，以下とします．

(1.3.1){\displaystyle \;\;\; \lambda (x) = \left[ \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} \right]^{1/2} }

制約なし問題のときと同様に，{\displaystyle (1/2) \lambda (x)^2 } は準最適性条件 {\displaystyle f(x) - f(x^*)} の {\displaystyle f } の二次近似に基づく近似になっています．また停止基準として用いられます．

(1.3.2){\displaystyle \;\;\; f(x) - f(x^*) }

{\displaystyle \;\;\;\;\;\;\;\; \approx f(x) - \inf_{ \{ y \ | \ Ay=b \} } \hat{f}(y) }

{\displaystyle \;\;\;\;\;\;\;\; = f(x) - \inf_{ \{ v \ | \ A(x+v)=b \} } \hat{f}(x+v) }

{\displaystyle \;\;\;\;\;\;\;\; = f(x) - \hat{f}( x + \Delta x_\mathrm{nt} ) \;\;\; \because } 本記事[ 1.1. 目的関数の二次近似の最適点 ]

{\displaystyle \;\;\;\;\;\;\;\; = - \nabla f(x)^T \Delta x_\mathrm{nt} - \frac{1}{2} \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} \;\;\; \because } (1.2.1)

{\displaystyle \;\;\;\;\;\;\;\; = - \nabla f(x)^T \Delta x_\mathrm{nt} - \frac{1}{2} \lambda (x)^2 }

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

{\displaystyle \;\;\;\;\;\;\;\; = \Delta x_\mathrm{nt}^T \nabla^2 f(x) \ \Delta x_\mathrm{nt} + \Delta x_\mathrm{nt}^T A^T w - \frac{1}{2} \lambda (x)^2 }

{\displaystyle \;\;\;\;\;\;\;\; = \frac{1}{2} \lambda (x)^2 + \Delta x_\mathrm{nt}^T A^T w }

{\displaystyle \;\;\;\;\;\;\;\; = \frac{1}{2} \lambda (x)^2 + \left( A \Delta x_\mathrm{nt} \right)^T w }

{\displaystyle \;\;\;\;\;\;\;\; = \frac{1}{2} \lambda (x)^2 \;\;\; \because } (1.1.3)


制約なし問題と同様に，ニュートンデクリメントはヘッセ行列により定義された二次ノルムの意味でのニュートンステップの長さとして解釈できます．

(1.3.3){\displaystyle \;\;\; \lambda (x) = \left[ \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} \right]^{1/2} \;\;\; \because } (1.3.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| \Delta x_\mathrm{nt} \right\|_{ \nabla^2 f(x) } }


制約なし問題と同様に，ニュートンデクリメントによる {\displaystyle - \lambda (x)^2 } は {\displaystyle f } の {\displaystyle x } での方向微分として解釈できます．

(1.3.4){\displaystyle \;\;\; \left. \frac{d}{dt} f(x + \Delta x_{ \mathrm{nt} } t ) \right|_{t=0} = \nabla f(x)^T \Delta x_{ \mathrm{nt} } }

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


[ 1.4. 実行可能な降下方向 ]

{\displaystyle Ax=b } と仮定します．{\displaystyle Av=0 } のとき {\displaystyle v \in \mathbb{R}^n } を実行可能方向(feasible direction)といいます．このとき，{\displaystyle x + t v, \ t \in \mathbb{R} } の形式のあらゆる点もまた実行可能です，すなわち {\displaystyle A( x + t v )= b} です．小さい {\displaystyle t \gt 0 } について {\displaystyle f(x+tv) \lt f(x) } が成り立つとき，{\displaystyle v } を降下方向(descent direction)といいます．

ニュートンステップはつねに実行可能方向です(ただし {\displaystyle x } が最適点のときは {\displaystyle \Delta x_\mathrm{nt} = 0 } です)．じっさいに(1.1.3)より {\displaystyle A \Delta x_\mathrm{nt} = 0 } です．さらに(1.3.4)よりニュートンステップは降下方向です．


[ 1.5. アフィン不変性 ]

制約なし問題に対するニュートンステップとニュートンデクリメントと同様に，等式制約あり問題においてもそれらはアフィン不変です．

関数 {\displaystyle \bar{f} : \mathbb{R}^n \to \mathbb{R} } を定義します．冒頭の過去記事(制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義)(2.1.1)～(2.2.4)を再掲します．

(1.5.1){\displaystyle \;\;\; y = T^{-1} x }

(1.5.2){\displaystyle \;\;\; \bar{f}(y) = f(Ty) }

(1.5.3){\displaystyle \;\;\; \nabla \bar{f}(y) = T^T \nabla f( T y ) \;\;\; \because } 連鎖律(文献[2])

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

(1.5.4){\displaystyle \;\;\; \nabla^2 \bar{f}(y) = T^T \nabla^2 f( T y ) \ T \;\;\; \because } 連鎖律(文献[2])

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

以下を得ます．

(1.5.5){\displaystyle \;\;\; Ax=b }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ ATy=b \;\;\; \because } (1.5.1)


以下の最適化問題を考えます．

(1.5.6)
{\displaystyle \mathrm{minimize} \;\;\;\; \bar{f}(y) \;\;\; (= f( T y ) ) }
{\displaystyle \mathrm{subject \; to} \;\;\ ATy=b }

この最適化問題のKKT系は以下となります．

(1.5.7){\displaystyle \;\;\; \begin{bmatrix} T^T \nabla^2 f( T y ) \ T & T^T A^T \\ AT & 0 \end{bmatrix} \begin{bmatrix} \Delta y_{\mathrm{nt}} \\ \bar{w} \end{bmatrix} = \begin{bmatrix} - T^T \nabla f( T y ) \\ 0 \end{bmatrix} }

{\displaystyle x = T y} でのニュートンステップ {\displaystyle \Delta x_{\mathrm{nt}} } と比較して以下を得ます．

(1.5.8){\displaystyle \;\;\; \Delta y_{\mathrm{nt}} = T^{-1} \Delta x_{\mathrm{nt}} }

(1.5.9){\displaystyle \;\;\; \bar{w} = w }

さらに以下を得ます．点列 {\displaystyle \{ x^{(k)} \}_{k=0,1,\cdots} } と {\displaystyle \{ y^{(k)} \}_{k=0,1,\cdots} } は線形変換 {\displaystyle T } で関連づけられます．

(1.5.10){\displaystyle \;\;\; y + \Delta y_\mathrm{nt} = T^{-1} x + T^{-1} \Delta x_\mathrm{nt} \;\;\; \because } (1.5.1)(1.5.8)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = T^{-1} \left( x + \Delta x_\mathrm{nt} \right) }


ニュートンデクリメントはニュートンステップと同様にアフィン不変です．冒頭の過去記事(制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義)(2.2.5)と同様に計算できるので，ここでは結果のみ示します．

(1.5.11){\displaystyle \;\;\; \frac{1}{2} \bar{\lambda} (y)^2 = \Delta y_{ \mathrm{nt} }^T \nabla^2 \bar{f}(y) \Delta y_{ \mathrm{nt} } }

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



[ 2. アルゴリズム ]

等式制約あり凸最適化問題に対するニュートン法のアルゴリズムを以下に示します．制約なし問題とほぼ同じです．

f:id:seetheworld1992:20210110191826p:plain


この方法は({\displaystyle x^{(k)} } が最適点でないかぎり)実行可能降下方法(feasible descent method)です．冒頭の過去記事(制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義)(1.1.2)同様に以下が成り立つからです．

(2.1){\displaystyle \;\;\; f(x^{(k+1)}) \lt f(x^{(k)}) }

{\displaystyle \;\;\; \Leftrightarrow \ \nabla f(x^{(k)})^T \Delta x_\mathrm{nt}^{(k)} \lt 0 \;\;\; \because } (1.3.3)

ニュートン法はKKT行列が {\displaystyle x } で正則であることが必要です．


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

以上，等式制約あり凸最適化問題に対するニュートン法と，ニュートンステップの定義，解釈，性質をまとめました．



参考文献
[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