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

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

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

数学 数理最適化

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

制約なし凸最適化問題の目的関数に強凸性を仮定することの意味について考える - エンジニアを目指す浪人のブログ

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

制約なし凸最適化問題に対する最急降下法と，ノルム選択，目的関数に強凸性を仮定するときの収束解析をまとめる - エンジニアを目指す浪人のブログ

正定値行列の逆行列は正定値であることの証明をメモする - エンジニアを目指す浪人のブログ

係数行列が対称行列の二次関数が凸関数(あるいは狭義凸関数)であるための必要十分条件はその係数行列が半正定値(あるいは正定値)であることを証明する - エンジニアを目指す浪人のブログ

係数行列が半正定値の二次関数が最小値をもつための必要十分条件は勾配が零ベクトルであることを証明する - エンジニアを目指す浪人のブログ

二次ノルムの定義をメモする - エンジニアを目指す浪人のブログ


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

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

目次

{\displaystyle \; } 0. 準備

{\displaystyle \; } 1. ニュートンステップの定義と解釈
{\displaystyle \;\;\; } 1.1. 定義
{\displaystyle \;\;\; } 1.2. 目的関数の二次近似の最適点
{\displaystyle \;\;\; } 1.3. ヘッセ行列ノルムの意味での最急降下ステップ
{\displaystyle \;\;\; } 1.4. 一次の最適性条件の一次近似の解

{\displaystyle \; } 2. ニュートンステップの性質
{\displaystyle \;\;\; } 2.1. アフィン不変性
{\displaystyle \;\;\; } 2.2. ニュートンデクリメント

{\displaystyle \; } 3. ニュートン法
{\displaystyle \;\;\; } 3.1. アルゴリズム
{\displaystyle \;\;\; } 3.2. アフィン不変性



[ 0. 準備 ]

冒頭の過去記事(制約なし凸最適化問題の目的関数)[ 0. 準備 ]と同じです．

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



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

はじめにニュートンステップを定義し，その後に三つの解釈を示していきます．


[ 1.1. 定義 ]

以下をニュートンステップ(Newton step)といいます．

(1.1.1){\displaystyle \;\;\; \Delta x_{\mathrm{nt}} = - \nabla^2 f(x)^{-1} \nabla f(x), \;\;\; x \in \mathrm{dom} \ f }

目的関数 {\displaystyle f(x) } は凸で二階微分可能であると仮定しているので，ヘッセ行列 {\displaystyle \nabla^2 f(x) } は半正定値です(文献[5]にあります)．{\displaystyle \nabla^2 f(x) } は正定値と仮定すると，冒頭の過去記事(正定値行列の逆行列)事実.より {\displaystyle \nabla^2 f(x)^{-1} } は正定値です． したがって {\displaystyle \Delta x_\mathrm{nt} } は {\displaystyle \nabla f(x) = 0 } でないかぎり降下方向(冒頭の過去記事(降下法の枠組み)(1.1.6)にあります)であることがわかります．

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

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lt 0 \;\;\;\;\;\; \because \nabla^2 f(x)^{-1} } は正定値


[ 1.2. 目的関数の二次近似の最適点 ]

{\displaystyle f } の {\displaystyle x } のまわりのテイラー展開の二次近似 {\displaystyle \hat{f} } は以下です．{\displaystyle v } の二次関数です．

(1.2.1){\displaystyle \;\;\; f(x + v) \approx \hat{f}(x + v) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v \;\;\; \because } テイラーの定理(文献[6])

冒頭の過去記事(係数行列が対称行列)定理1.より {\displaystyle \hat{f} } は凸です．さらに冒頭の過去記事(係数行列が半正定値)定理3.より，{\displaystyle v = \Delta x_\mathrm{nt} } のとき最小値をとります．すなわちニュートンステップは {\displaystyle f } の {\displaystyle x } のまわりの二次近似を最小化するために {\displaystyle x } に加えるべきものです．概念を図示すると以下です．

f:id:seetheworld1992:20201206172034p:plain

この解釈はニュートンステップへの洞察を与えます．関数 {\displaystyle f(x) } が二次関数であれば，{\displaystyle x + \Delta x_\mathrm{nt} } は {\displaystyle f } の最適点 {\displaystyle x^* } に一致します．関数 {\displaystyle f(x) } が二次関数に近い関数であれば，{\displaystyle x + \Delta x_\mathrm{nt} } は {\displaystyle x_* } の非常に良い近似値です．{\displaystyle f } は二階微分可能を仮定しているので，{\displaystyle x } が {\displaystyle x^* } に近いとき {\displaystyle \hat{f} } は {\displaystyle f } の正確な近似になっています． したがって，点 {\displaystyle x } が最適点 {\displaystyle x^* } に近いとき {\displaystyle x + \Delta x_\mathrm{nt} } は {\displaystyle x^* } の非常に良い見積もりになります．次節とその次の節でも，この直観が正しいことを示していきます．


[ 1.3. ヘッセ行列ノルムの意味での最急降下ステップ ]

二次ノルムの意味での最急降下法(冒頭の過去記事(制約なし凸最適化問題に対する最急降下法)[ 2.2. 二次ノルム ])で以下を考えます．

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

このとき冒頭の過去記事(制約なし凸最適化問題に対する最急降下法)(2.2.2)はニュートンステップ(1.1.1)に一致します．すなわち，ニュートンステップは {\displaystyle \nabla^2 f(x) }-二次ノルムの意味での最急降下ステップです．二次ノルムは以下です．

(1.3.2){\displaystyle \;\;\; \left\| u \right\|_{ \nabla^2 f(x) } = (u^T \nabla^2 f(x) u)^{1/2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| \nabla^2 f(x)^{1/2} u \right\|_2 }

このことはニュートンステップがよい探索方向で，{\displaystyle x } が {\displaystyle x^* } に近いとき非常によい探索方向であることのもう一つの解釈を与えます．

最急降下法は座標変換後のヘッセ行列の条件数が小さいときに上手くいきます(冒頭の過去記事(制約なし凸最適化問題に対する最急降下法)[ 3.2. 二次ノルムと座標変換 ]にあります)．とくに {\displaystyle x^* } の近くで {\displaystyle P = \nabla^2 f(x^*) } は非常に良い選択です．したがって {\displaystyle x } が {\displaystyle x^* } に近いとき {\displaystyle \nabla^2 f(x) \approx \nabla^2 f(x^*) } なのでニュートンステップは非常に良い探索方向であることを説明できます．概念を図示すると以下です．

f:id:seetheworld1992:20201206172613p:plain


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

一次の最適性条件 {\displaystyle \nabla f(x^*) = 0 } の {\displaystyle x } のまわりのテイラー展開の一次近似 {\displaystyle \hat{f} } は以下です．

(1.4.1){\displaystyle \;\;\; \nabla f(x + v) \approx \nabla f(x) + \nabla^2 f(x) v \;\;\; \because } テイラーの定理(文献[6])

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

この解は {\displaystyle v = \Delta x_\mathrm{nt} } です．したがって，ニュートンステップは一次の最適性条件の {\displaystyle x } のまわりの一次近似をゼロにするために {\displaystyle x } に加えるべきものです．したがって，点 {\displaystyle x } が最適点 {\displaystyle x^* } に近いとき(このとき最適性条件はほぼ成り立ちます)，{\displaystyle x + \Delta x_\mathrm{nt} } は {\displaystyle x^* } の非常に良い近似です．

この解釈は {\displaystyle n = 1 } すなわち {\displaystyle f : \mathbb{R} \to \mathbb{R} } のときとくに簡単になります．最小化問題の解 {\displaystyle x^* } は {\displaystyle f'(x^*)= 0 } をみたします．すなわち， {\displaystyle f } が凸で {\displaystyle f' } は単調増加であることから {\displaystyle x^* } は {\displaystyle f'} がゼロとなる点です．解 {\displaystyle x^* } の近似 {\displaystyle x } が与えられると {\displaystyle f' } の一次近似を得ることができ，その一次近似 {\displaystyle \hat{f} } がゼロとなる点は {\displaystyle x + \Delta x_\mathrm{nt} } です．概念を図示すると以下です．

f:id:seetheworld1992:20201206173746p:plain



[ 2. ニュートンステップの性質 ]

[ 2.1. アフィン不変性 ]

ニュートンステップの重要な特徴は座標の線形変換の影響を受けないことです．このことは，ニュートンステップはアフィン不変(affine invariant)である，といいます．{\displaystyle n \times n } 正則行列 {\displaystyle T } とします．関数 {\displaystyle \bar{f} : \mathbb{R}^n \to \mathbb{R} } を以下で定義します．

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

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

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

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

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

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

したがって {\displaystyle \bar{f} } の {\displaystyle y } におけるニュートンステップは以下です．

(2.1.5){\displaystyle \;\;\; \Delta y_\mathrm{nt} = - \left( \nabla^2 \bar{f}(y) \right)^{-1} \nabla \bar{f}(y) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \left( T^T \nabla^2 f( x ) \ T \right)^{-1} T^T \nabla f( x ) \;\;\; \because } (2.1.3)(2.1.4)

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

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

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

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

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

(2.1.6){\displaystyle \;\;\; y + \Delta y_\mathrm{nt} = T^{-1} x + T^{-1} \Delta x_\mathrm{nt} \;\;\; \because } (2.1.1)(2.1.5)

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


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

以下の量を {\displaystyle x } でのニュートンデクリメント(newton decrement)といいます．

(2.2.1){\displaystyle \;\;\; \lambda (x) = \left[ \nabla f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) \right]^{1/2} }

ニュートンデクリメントはニュートン法の解析において重要な役割があり，また停止基準として用いられます．{\displaystyle (1/2) \lambda (x)^2 } は準最適性条件(suboptimality condition) {\displaystyle f(x) - p^* } の {\displaystyle f } の二次近似に基づく近似になっています．

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

{\displaystyle \;\;\;\;\;\;\;\; \approx f(x) - \inf_{y} \hat{f}(y) }

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

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

{\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 \left( - \nabla^2 f(x)^{-1} \nabla f(x) \right) - \frac{1}{2} \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} }

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

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

{\displaystyle \;\;\;\;\;\;\;\; = \lambda (x)^2 - \frac{1}{2} \left( - \nabla^2 f(x)^{-1} \nabla f(x) \right)^T \ \nabla^2 f(x) \ \left( - \nabla^2 f(x)^{-1} \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\; = \lambda (x)^2 - \frac{1}{2} \left( \nabla^2 f(x)^{-1} \nabla f(x) \right)^T \nabla f(x) }

{\displaystyle \;\;\;\;\;\;\;\; = \lambda (x)^2 - \frac{1}{2} \nabla f(x)^T \left( \nabla^2 f(x)^{-1} \right)^T \nabla f(x) }

{\displaystyle \;\;\;\;\;\;\;\; = \lambda (x)^2 - \frac{1}{2} \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) \;\;\; \because \nabla^2 f(x)^T = \nabla^2 f(x) }

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


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

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

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| \Delta x_\mathrm{nt} \right\|_{ \nabla^2 f(x) } \;\;\; \because } 冒頭の過去記事(二次ノルムの定義)定義.


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

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

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

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

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


ニュートンデクリメントはニュートンステップと同様にアフィン不変です．

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

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left[ T^{-1} \Delta x_{ \mathrm{nt} } \right]^T \left[ T^T \nabla^2 f(x) \ T \right] \left[ T^{-1} \Delta x_{ \mathrm{nt} } \right] \;\;\; \because } (2.1.4)(2.1.5)

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

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

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



[ 3. ニュートン法 ]

[ 3.1. アルゴリズム ]

ニュートン法のアルゴリズムを以下に示します．このアルゴリズムは {\displaystyle t = 1 } のときの純粋ニュートン法(pure Newton method)と区別して減衰ニュートン法(damped Newton method)ということもあります．

f:id:seetheworld1992:20201206182846p:plain

これは降下法(冒頭の過去記事(降下法の枠組み)にあります)において探索方向にニュートンステップを用いるものです．違いは停止基準が更新の後ではなく探索方向の計算の後に判定される点のみです．


[ 3.2. アフィン不変性 ]

アルゴリズムを初期点 {\displaystyle y^{(0)} = T^{-1} x^{(0)} } から開始すると，(2.1.6)より以下を得ます．

(3.2.1){\displaystyle \;\;\; y^{(k)} = T^{-1} x^{(k)}, \;\;\; k \in \{ 0,1,2,\ldots \} }

いいかえると，反復を繰り返しても同じ線形変換により関係づけられます．(2.2.5)より，停止基準も変わりません．点列 {\displaystyle \{ x^{(k)} \}_{k=0,1,\cdots} } と {\displaystyle \{ y^{(k)} \}_{k=0,1,\cdots} } は等価であり，収束のふるまいも同じです．したがって，ニュートン法は座標変換の影響を受けないことがわかります．このことは，勾配法が座標変換に大きな影響を受けることと対照的です．


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

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



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Stanford University Stephen Boyd先生のノート https://web.stanford.edu/class/ee364a/lectures/unconstrained.pdf
[3] Carnegie Mellon University Ryan Tibshirani先生のノート https://www.stat.cmu.edu/~ryantibs/convexopt/lectures/newton.pdf
[4] The University of Texas at Austin Constantine Caramanis先生らのノート http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_6_Scribe_Notes.final.pdf
[5] Wikipedia Convex function のページ https://en.wikipedia.org/wiki/Convex_function
[6] Wikipedia Taylor's theorem のページ https://en.wikipedia.org/wiki/Taylor%27s_theorem
[7] Stanford University Stephen Boyd先生のノート http://210.43.0.57/moocresource/data/20100601/U/stanford201001009/review7_single.pdf