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

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

制約なし凸最適化問題に対するニュートン法の，目的関数に強凸性，そのヘッセ行列にリプシッツ連続性を仮定するときの収束解析をまとめる

数学 数理最適化

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

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

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

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

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

目的関数に強凸性を仮定するときのニュートンデクリメントの不等式を証明する - エンジニアを目指す浪人のブログ

強凸関数のヘッセ行列と逆行列の，最大固有値，最小固有値，スペクトルノルムの不等式を証明する - エンジニアを目指す浪人のブログ


制約なし凸最適化問題に対するニュートン法(Newton's method)の収束解析についてまとめておくことにしました．Boyd and Vandenberghe(2004)の9章5節(の3)をベースにしています．

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

目次

{\displaystyle \; } 0. 準備
{\displaystyle \;\;\; } 0.1. 準備
{\displaystyle \;\;\; } 0.2. 目的関数の強凸性
{\displaystyle \;\;\; } 0.3. 目的関数のヘッセ行列のリプシッツ連続性

{\displaystyle \; } 1. ニュートン法の収束解析
{\displaystyle \;\;\; } 1.1. 定理
{\displaystyle \;\;\; } 1.2. 減衰ニュートンフェーズ
{\displaystyle \;\;\; } 1.3. 二次収束フェーズ
{\displaystyle \;\;\; } 1.4. 計算複雑さ
{\displaystyle \;\;\; } 1.5. 欠点
{\displaystyle \;\;\; } 1.6. 減衰ニュートンフェーズの証明
{\displaystyle \;\;\; } 1.7. 二次収束フェーズの証明
{\displaystyle \;\;\; } 1.8. 定理の証明


[ 0. 準備 ]

[ 0.1. 準備 ]

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

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

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


[ 0.2. 目的関数の強凸性 ]

目的関数 {\displaystyle f : \mathbb{R}^n \to \mathbb{R} } は(二階微分可能で)強凸であると仮定しているので，以下の不等式が成り立ちます(冒頭の過去記事(制約なし凸最適化問題の目的関数)(1.3.1)にあります)．

(0.2.1){\displaystyle \;\;\; m I \preceq \nabla^2 f(x) \preceq M I \;\;\;\;\;\; x \in S, \;\; m \gt 0, \ M \gt 0, \ m \lt M }


[ 0.3. 目的関数のヘッセ行列のリプシッツ連続性 ]

{\displaystyle f } のヘッセ行列 {\displaystyle \nabla^2 f } はリプシッツ連続(文献[6]にあります)であると仮定します．

(0.3.1){\displaystyle \;\;\; \left\| \nabla^2 f(x) - \nabla^2 f(y) \right\|_2 \le L \left\| x - y \right\|_2 \;\;\;\;\;\; x,y \in S, \;\; L \ge 0 }

左辺の行列ノルムはスペクトルノルムです(文献[7]にあります)．定数 {\displaystyle L, - L } は {\displaystyle f } の三階微分の上界，下界と解釈できます．{\displaystyle f } が二次関数であれば {\displaystyle L } はゼロになりえます．より一般に，リプシッツ定数 {\displaystyle L } は {\displaystyle f } がどの程度よく二次関数で近似可能かを測るので，{\displaystyle L } がニュートン法の性能において決定的な役割があると期待することができます．直観的には，二次近似がゆっくり変化する(すなわち {\displaystyle L } が小さい)関数であればニュートン法はうまくいくと考えられます．



[ 1. ニュートン法の収束解析 ]

冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)[ 3.1. アルゴリズム ]のアルゴリズムの収束解析をします．このアルゴリズムでは，直線探索として冒頭の過去記事(降下法の枠組み)[ 1.3. バックトラッキング直線探索 ]のバックトラッキング直線探索を用いています．定理.や事実.の証明は後の節で行います．


[ 1.1. 定理 ]

以下の定理が成り立ちます．

'--------------------------------------------------------------------------------------------------------------------------------------------
定理.

制約なし凸最適化問題の目的関数 {\displaystyle f } は強凸，そのヘッセ行列 {\displaystyle \nabla^2 f } はリプシッツ連続であると仮定する．このときニュートン法の収束について，以下が成り立つ．

(1.1.1){\displaystyle \;\;\; f(x^{(k)}) - p^* \le \left( f( x^{0}) - p^* \right) - \gamma k \;\;\;\;\;\; \mathrm{if} \; k \le k_0 }

(1.1.2){\displaystyle \;\;\; f(x^{(k)}) - p^* \le \frac{2 m^3}{L^2} \left( \frac{1}{2} \right)^{ 2^{k - k_0} } \;\;\;\;\;\;\;\;\;\;\;\;\; \mathrm{if} \; k \ge k_0 + 1 }


ここで以下である．

(1.1.3){\displaystyle \;\;\; \gamma = \alpha \beta \eta^2 \frac{m}{M^2} \ (\gt 0) }

(1.1.4){\displaystyle \;\;\; \eta = \min \{ 1 , 3( 1 - 2 \alpha) \} \frac{m^2}{L} \ (\gt 0) }

(1.1.5){\displaystyle \;\;\; k_0 = \left\{ k \in \{ 0,1,2,\ldots \} \ \middle| \ \left[ \left\| \nabla f(x^{(k)}) \right\|_2 \ge \eta \right] \cap \left[ \left\| \nabla f(x^{(k+1)}) \right\|_2 \lt \eta \right] \right\} }

'--------------------------------------------------------------------------------------------------------------------------------------------


不等式(1.1.2)は，いちど {\displaystyle \left\| \nabla f(x) \right\|_2 \lt \eta } が成り立つとその後の収束が非常に速いことを示しています．これを二次収束(quadratic convergence)といいます．大まかにいえば，(1.1.2)は，十分大きな反復回数の後に各反復ごとに正確な桁数は倍になることを意味しています．

定理.からわかるように，ニュートン法は二つの段階からなります．第一段階はステップサイズ {\displaystyle t \lt 0 } を選択するので減衰ニュートンフェーズ(damped Newton phase)といいます．第二段階は二次収束フェーズ(quadratically convergent stage)といいます．またステップサイズ {\displaystyle t = 0 } を選択するので純粋ニュートンフェーズ(pure Newton phase)ともいいます．


[ 1.2. 減衰ニュートンフェーズ ]

以下の事実が成り立ちます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実1.

{\displaystyle \left\| \nabla f(x^{(k)}) \right\|_2 \ge \eta } のとき，{\displaystyle k \le k_0 } である．このとき以下が成り立つ．

(1.2.1){\displaystyle \;\;\; f(x^{(k+1)}) - f(x^{(k)}) \le - \gamma }

'--------------------------------------------------------------------------------------------------------------------------------------------


[ 1.3. 二次収束フェーズ ]

以下の事実が成り立ちます．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実2.

{\displaystyle \left\| \nabla f(x^{(k)}) \right\|_2 \lt \eta } のとき，{\displaystyle k \ge k_0 + 1 } である．このときバックトラッキング直線探索は {\displaystyle t^{(k)} = 1 } を選択し，以下が成り立つ．

(1.3.1){\displaystyle \;\;\; \frac{L}{2 m^2} \left\| \nabla f(x^{(k+1)}) \right\|_2 \le \left( \frac{L}{2 m^2} \left\| \nabla f(x^{(k)}) \right\|_2 \right)^2 }

'--------------------------------------------------------------------------------------------------------------------------------------------

事実2.より，二次収束フェーズに入ると減衰ニュートンフェーズに戻らないことが確認できます．

(1.3.2){\displaystyle \;\;\; \left\| \nabla f(x^{(k+1)}) \right\|_2 \le \frac{L}{2 m^2} \left\| \nabla f(x^{(k)}) \right\|_2^2 \;\;\; \because } (1.3.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lt \frac{L}{2 m^2} \eta^2 \;\;\; \because \left\| \nabla f(x^{(k)}) \right\|_2 \lt \eta }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{2\eta} \eta^2 \;\;\;\;\; \because } (1.1.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2} \eta }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lt \eta }


[ 1.4. 計算複雑さ ]

計算複雑さを見積もっていきます．はじめに減衰ニュートンフェーズの反復回数の上界を導出します．事実1.より，各反復で {\displaystyle f } は少なくとも {\displaystyle \gamma } 減少するので，減衰ニュートンフェーズの反復回数は以下を超過することはありません．

(1.4.1){\displaystyle \;\;\; \frac{ f(x^{(0)}) - p^* }{\gamma} }


つぎに定理.(1.1.2)より，{\displaystyle \epsilon \gt 0 } について以下が成り立ちます．

(1.4.2){\displaystyle \;\;\; \left[ \frac{2 m^3}{L^2} \left( \frac{1}{2} \right)^{ 2^{k - k_0} } \le \epsilon \right] \Rightarrow \left[ f(x^{(k)}) - p^* \le \epsilon \right] }

したがって {\displaystyle f(x^{(k)}) - p^* \le \epsilon } の十分条件をみたす二次収束フェーズの反復回数 {\displaystyle k } の下界は高々以下の回数 {\displaystyle \log_{2} \log_{2} \left( \epsilon_0 / \epsilon \right) } です．

(1.4.3){\displaystyle \;\;\; \epsilon_0 = \frac{2 m^3}{L^2} }

(1.4.4){\displaystyle \;\;\; \epsilon_0 \left( \frac{1}{2} \right)^{ 2^{k - k_0} } \le \epsilon \;\;\; \because } (1.4.2)(1.4.3)

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ \left( \frac{1}{2} \right)^{ 2^{k - k_0} } \le \epsilon / \epsilon_0 }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ \log_{2} \left( \frac{1}{2} \right)^{ 2^{k - k_0} } \le \log_{2} \left( \epsilon / \epsilon_0 \right) }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ 2^{k - k_0} \log_{2} \left( \frac{1}{2} \right) \le \log_{2} \left( \epsilon / \epsilon_0 \right) }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ 2^{k - k_0} \ge - \log_{2} \left( \epsilon / \epsilon_0 \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \log_{2} \left( \epsilon_0 / \epsilon \right) }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ \log_{2} 2^{k - k_0} \ge \log_{2} \log_{2} \left( \epsilon_0 / \epsilon \right) }

{\displaystyle \;\;\;\;\;\;\;\;\; \Leftrightarrow \ k - k_0 \ge \log_{2} \log_{2} \left( \epsilon_0 / \epsilon \right) }


{\displaystyle \log_{2} \log_{2} \left( \epsilon_0 / \epsilon \right) } は必要な精度を小さくしていくとき，極めてゆっくりと大きくなります．実用目的においては，{\displaystyle 5 } あるいは {\displaystyle 6 } と考えることができます．厳密ではありませんが，{\displaystyle f } を最小化するために必要な合計の反復回数の上界，より正確には，最適値の極めてよい近似を計算するために必要な反復回数の上界は以下といえます．

(1.4.5){\displaystyle \;\;\; \frac{ f(x^{(0)}) - p^* }{ \gamma } + \log_{2} \log_{2} \left( \epsilon_0 / \epsilon \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; \approx \frac{ f(x^{(0)}) - p^* }{ \gamma } + 6 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ M^2 }{ \alpha \beta \eta^2 m } \left( f(x^{(0)}) - p^* \right) + 6 \;\;\; \because } (1.1.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ M^2 }{ \alpha \beta \left[ \min \{ 1 , 3( 1 - 2 \alpha) \} \frac{m^2}{L} \right]^2 m } \left( f(x^{(0)}) - p^* \right) + 6 \;\;\; \because } (1.1.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{ M^2 L^2 / m^5 }{ \alpha \beta \min \{ 1 , 9( 1 - 2 \alpha)^2 \} } \left( f(x^{(0)}) - p^* \right) + 6 }


[ 1.5. 欠点 ]

本記事におけるニュートン法の収束解析は二つの大きな欠点があります．

複雑さの結果(1.4.5)は，実問題においては未知のパラメータ {\displaystyle m,M,L} を含みます．結果として必要な反復回数の上界は未知です．もちろん収束解析と複雑さの見積もりは概念的には役立つものです．

二つ目の欠点は，ニュートン法はアフィン不変ですが，収束解析は座標系に依存するということです．座標の線形変換により {\displaystyle m,M,L} は変化します({\displaystyle \alpha, \beta } はバックトラッキング直線探索のパラメータなので座標系には無関係です )．ニュートン法のアフィン不変性は，冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)[ 3.2. アフィン不変性 ]にあります．


[ 1.6. 減衰ニュートンフェーズの証明 ]

事実1.の証明は以下です．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実1.の証明

{\displaystyle \left\| \nabla f(x^{(k)}) \right\|_2 \ge \eta } を仮定する．{\displaystyle f } の強凸性を仮定しているので，冒頭の過去記事(制約なし凸最適化問題の目的関数)(1.2.2)で {\displaystyle y = x + t \Delta x_{\mathrm{nt}} } として以下を得る．

(1.6.1){\displaystyle \;\;\; f(x + t \Delta x_{\mathrm{nt}}) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x) + \nabla f(x)^T (t \Delta x_{\mathrm{nt}}) + \frac{M}{2} \left\| t \Delta x_{\mathrm{nt}} \right\|_2^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + t \nabla f(x)^T \Delta x_{\mathrm{nt}} + \frac{M \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 }{2} t^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - t \lambda(x)^2 + \frac{M \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 }{2} t^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x) - t \lambda(x)^2 + \frac{M }{2} t^2 \frac{\lambda (x)^2}{m} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(目的関数に強凸性を仮定するときのニュートンデクリメント)事実.(1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - t \lambda(x)^2 + \frac{M }{2m} t^2 \lambda (x)^2 }


以下を定義する．

(1.6.2){\displaystyle \;\;\; \hat{t} = m / M }

これと(1.6.1)より {\displaystyle \hat{t} } は冒頭の過去記事(降下法の枠組み)(1.3.1)のバックトラッキング直線探索の停止条件をみたすことがわかる．

(1.6.3){\displaystyle \;\;\; f(x + \hat{t} \Delta x_{\mathrm{nt}}) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x) - \hat{t} \lambda (x)^2 + \frac{M}{2m} \hat{t}^2 \lambda (x)^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - \frac{m}{2M} \lambda (x)^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - \frac{1}{2} \hat{t} \lambda (x)^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x) - \alpha \hat{t} \lambda (x)^2 \;\;\; \because 0 \lt \alpha \lt 1/2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) + \alpha \hat{t} \nabla f(x)^T \Delta x_{\mathrm{nt}} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.4)


したがってバックトラッキング直線探索は {\displaystyle t \gt \beta m / M } をみたす {\displaystyle t } を出力する．このとき以下を得る．

(1.6.4){\displaystyle \;\;\; f(x^{+}) - f(x) \le - \alpha t \lambda (x)^2 \;\;\; \because } (1.6.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le - \alpha \frac{\beta m}{M} \lambda (x)^2 \;\;\; \because t \gt \beta m / M }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le - \alpha \frac{\beta m}{M} \frac{1}{M} \left\| \nabla^2 f(x) \right\|_2^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(目的関数に強凸性を仮定するときのニュートンデクリメント)事実.(1.1)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le - \alpha \frac{\beta m}{M} \frac{1}{M} \eta^2 \;\;\; \because \left\| \nabla f(x^{(k)}) \right\|_2 \ge \eta }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \gamma \;\;\; \because } (1.1.3)

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


[ 1.7. 二次収束フェーズの証明 ]

事実2.の証明は以下です．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実2.の証明

{\displaystyle \left\| \nabla f(x^{(k)}) \right\|_2 \lt \eta } を仮定する．はじめに，このときバックトラッキング直線探索は {\displaystyle t = 1 } を出力することを証明する．

以下を定義する．

(1.7.1){\displaystyle \;\;\; \tilde{f} (t) = f( x + t \Delta x_{ \mathrm{nt} } ) }

(1.7.2){\displaystyle \;\;\; \Rightarrow \ \tilde{f}' (t) = \Delta x_{ \mathrm{nt} }^T \ \nabla f( x + t \Delta x_{ \mathrm{nt} } ) \;\;\; \because } 連鎖律(文献[9])

(1.7.3){\displaystyle \;\;\; \Rightarrow \ \tilde{f}'' (t) = \Delta x_{ \mathrm{nt} }^T \ \nabla^2 f( x + t \Delta x_{ \mathrm{nt} } ) \Delta x_{ \mathrm{nt} } \;\;\; \because } 連鎖律(文献[9])


{\displaystyle t \ge 0 } について以下を得る．

(1.7.4){\displaystyle \;\;\; \left| \tilde{f}'' (t) - \tilde{f}'' (0) \right| }

{\displaystyle \;\;\; = \left| \Delta x_{ \mathrm{nt} }^T \ \nabla^2 f( x + t \Delta x_{ \mathrm{nt} } ) \Delta x_{ \mathrm{nt} } - \Delta x_{ \mathrm{nt} }^T \ \nabla^2 f( x ) \Delta x_{ \mathrm{nt} } \right| \;\;\; \because } (1.7.3)

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

{\displaystyle \;\;\; \le \left\| \Delta x_{\mathrm{nt}} \right\|_2 \ \left\| \left[ \nabla^2 f (x + t \Delta x_{\mathrm{nt}} ) - \nabla^2 f (x ) \right] \Delta x_{\mathrm{nt}} \right\|_2 \;\;\; \because } コーシーシュワルツの不等式(文献[8])

{\displaystyle \;\;\; = \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \ \frac{ \left\| \left[ \nabla^2 f (x + t \Delta x_{\mathrm{nt}} ) - \nabla^2 f (x ) \right] \Delta x_{\mathrm{nt}} \right\|_2 }{ \left\| \Delta x_{\mathrm{nt}} \right\|_2 } }

{\displaystyle \;\;\; \le \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \ \sup_{ y \neq 0 } \frac{ \left\| \left[ \nabla^2 f (x + t \Delta x_{\mathrm{nt}} ) - \nabla^2 f (x ) \right] y \right\|_2 }{ \left\| y \right\|_2 } }

{\displaystyle \;\;\; = \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \ \left\| \nabla^2 f (x + t \Delta x_{\mathrm{nt}} ) - \nabla^2 f (x ) \right\|_2 \;\;\; \because } スペクトルノルムの定義(文献[7])

{\displaystyle \;\;\; \le \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \ L \left\| (x + t \Delta x_{\mathrm{nt}} ) - x \right\|_2 \;\;\; \because } リプシッツ連続性(0.3.1)

{\displaystyle \;\;\; = t L \left\| \Delta x_{\mathrm{nt}} \right\|_2^3 \;\;\; \because t \ge 0 }


(1.7.5){\displaystyle \;\;\; \Rightarrow \ \tilde{f}'' (t) \le \tilde{f}'' (0) + t L \left\| \Delta x_{\mathrm{nt}} \right\|_2^3 }

{\displaystyle \;\;\; = \lambda (x)^2 + t L \left\| \Delta x_{\mathrm{nt}} \right\|_2^3 \;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.3)

{\displaystyle \;\;\; \le \lambda (x)^2 + t L \left( \frac{ \lambda (x)^2 }{ m } \right)^{\frac{3}{2}} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(目的関数に強凸性を仮定するときのニュートンデクリメント)事実.(1.2)

{\displaystyle \;\;\; = \lambda (x)^2 + t \frac{L}{m^{3/2}} \lambda (x)^3 }


両辺を {\displaystyle 0 } から {\displaystyle t } まで積分して以下を得る．

(1.7.6){\displaystyle \;\;\; \tilde{f}' (t) \le \tilde{f}' (0) + t \lambda (x)^2 + t^2 \frac{L}{2 m^{3/2}} \lambda (x)^3 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \Delta x_{ \mathrm{nt} }^T \ \nabla f( x ) + t \lambda (x)^2 + t^2 \frac{L}{2 m^{3/2}} \lambda (x)^3 \;\;\; \because } (1.7.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - \lambda (x)^2 + t \lambda (x)^2 + t^2 \frac{L}{2 m^{3/2}} \lambda (x)^3 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.4)


両辺を {\displaystyle 0 } から {\displaystyle t } まで積分して以下を得る．

(1.7.7){\displaystyle \;\;\; \tilde{f} (t) \le \tilde{f} (0) - t \lambda (x)^2 + t^2 \frac{1}{2} \lambda (x)^2 + t^3 \frac{L}{6m^{3/2}} \lambda (x)^3 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x) - t \lambda (x)^2 + t^2 \frac{1}{2} \lambda (x)^2 + t^3 \frac{L}{6m^{3/2}} \lambda (x)^3 \;\;\; \because } (1.7.1)


{\displaystyle t = 1 } として以下を得る

(1.7.8){\displaystyle \;\;\; f( x + \Delta x_{ \mathrm{nt} } ) \le f(x) - \lambda (x)^2 + \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^3 }

{\displaystyle \;\;\; = f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^3 }

{\displaystyle \;\;\; \le f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^2 \left[ \frac{1}{m} \left\| \nabla^2 f(x) \right\|_2^2 \right]^{1/2} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(目的関数に強凸性を仮定するときのニュートンデクリメント)事実.(1.1)

{\displaystyle \;\;\; \le f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^2 \frac{1}{m^{1/2}} \left\| \nabla^2 f(x) \right\|_2 }

{\displaystyle \;\;\; \le f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^2 \frac{1}{m^{1/2}} \eta \;\;\;\;\;\; \because \left\| \nabla f(x^{(k)}) \right\|_2 \lt \eta }

{\displaystyle \;\;\; = f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^2 \frac{1}{m^{1/2}} \ \min \{ 1 , 3( 1 - 2 \alpha) \} \frac{m^2}{L} \;\;\; \because } (1.1.4)

{\displaystyle \;\;\; \le f(x) - \frac{1}{2} \lambda (x)^2 + \frac{L}{6 m^{3/2}} \lambda (x)^2 \frac{1}{m^{1/2}} \ 3( 1 - 2 \alpha) \frac{m^2}{L} }

{\displaystyle \;\;\; = f(x) - \frac{1}{2} \lambda (x)^2 + \frac{1}{6} \lambda (x)^2 \ 3( 1 - 2 \alpha) }

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

{\displaystyle \;\;\; = f(x) + \alpha \nabla f(x)^T \Delta x_{\mathrm{nt}} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.4)

したがって {\displaystyle t = 1 } は冒頭の過去記事(降下法の枠組み)(1.3.1)のバックトラッキング直線探索の停止条件をみたすことがわかる．

つぎに(1.3.1)を証明する．

(1.7.9){\displaystyle \;\;\; \left\| \nabla f(x^+) \right\|_2 = \left\| \nabla f(x + \Delta x_{\mathrm{nt}}) - 0 \right\|_2 }

{\displaystyle \;\;\; = \left\| \nabla f(x + \Delta x_{\mathrm{nt}}) - \left[ \nabla f(x) + \nabla^2 f(x) \Delta x_{\mathrm{nt}} \right] \right\|_2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.1)

{\displaystyle \;\;\; = \left\| \left[ \nabla f(x + \Delta x_{\mathrm{nt}}) - \nabla f(x) \right] - \nabla^2 f(x) \Delta x_{\mathrm{nt}} \right\|_2 }

{\displaystyle \;\;\; = \left\| \left[ \left. \nabla f(x + t \Delta x_{\mathrm{nt}}) \right|_{t=1} - \left. \nabla f( x + t \Delta x_{\mathrm{nt}} ) \right|_{t=0} \right]- \nabla^2 f(x) \Delta x_{\mathrm{nt}} \right\|_2 }

{\displaystyle \;\;\; = \left\| \int_{0}^{1} \left( \nabla f(x + t \Delta x_{\mathrm{nt}}) \right)' \ dt - \nabla^2 f(x) \Delta x_{\mathrm{nt}} \right\|_2 }

{\displaystyle \;\;\; = \left\| \int_{0}^{1} \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) \Delta x_{\mathrm{nt}} \ dt - \int_{0}^{1} \nabla^2 f(x) \Delta x_{\mathrm{nt}} \ dt \right\|_2 }

{\displaystyle \;\;\; = \left\| \int_{0}^{1} \left( \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) - \nabla^2 f(x) \right) \Delta x_{\mathrm{nt}} \ dt \right\|_2 }

{\displaystyle \;\;\; \le \int_{0}^{1} \left\| \left( \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) - \nabla^2 f(x) \right) \Delta x_{\mathrm{nt}} \right\|_2 \ dt }

{\displaystyle \;\;\; = \int_{0}^{1} \frac{ \left\| \left( \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) - \nabla^2 f(x) \right) \Delta x_{\mathrm{nt}} \right\|_2 }{ \left\| \Delta x_{\mathrm{nt}} \right\|_2 } \left\| \Delta x_{\mathrm{nt}} \right\|_2 \ dt }

{\displaystyle \;\;\; \le \int_{0}^{1} \sup_{y \neq 0} \frac{ \left\| \left( \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) - \nabla^2 f(x) \right) y \right\|_2 }{ \left\| y \right\|_2 } \left\| \Delta x_{\mathrm{nt}} \right\|_2 \ dt }

{\displaystyle \;\;\; = \int_{0}^{1} \left\| \nabla^2 f(x + t \Delta x_{\mathrm{nt}}) - \nabla^2 f(x) \right\|_2 \left\| \Delta x_{\mathrm{nt}} \right\|_2 \ dt \;\;\; \because } スペクトルノルムの定義(文献[7])

{\displaystyle \;\;\; \le \int_{0}^{1} L \left\| (x + t \Delta x_{\mathrm{nt}} ) - x \right\|_2 \left\| \Delta x_{\mathrm{nt}} \right\|_2 \ dt \;\;\; \because } リプシッツ連続性(0.3.1)

{\displaystyle \;\;\; = L \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \int_{0}^{1} t \ dt }

{\displaystyle \;\;\; = \frac{L}{2} \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 }

{\displaystyle \;\;\; = \frac{L}{2} \left\| - \nabla^2 f(x)^{-1} \nabla f(x) \right\|_2^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.1)

{\displaystyle \;\;\; = \frac{L}{2} \left( \frac{ \left\| \nabla^2 f(x)^{-1} \nabla f(x) \right\|_2 }{ \left\| \nabla f(x) \right\|_2 } \left\| \nabla f(x) \right\|_2 \right)^2 }

{\displaystyle \;\;\; \le \frac{L}{2} \left( \sup_{y \neq 0} \frac{ \left\| \nabla^2 f(x)^{-1} y \right\|_2 }{ \left\| y \right\|_2 } \left\| \nabla f(x) \right\|_2 \right)^2 }

{\displaystyle \;\;\; = \frac{L}{2} \left( \left\| \nabla^2 f(x)^{-1} \right\|_2 \left\| \nabla f(x) \right\|_2 \right)^2 \;\;\; \because } スペクトルノルムの定義(文献[7])

{\displaystyle \;\;\; \le \frac{L}{2} \left( \frac{1}{m} \left\| \nabla f(x) \right\|_2 \right)^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(強凸関数のヘッセ行列と逆行列の，最大固有値)事実2.(2.2)

{\displaystyle \;\;\; = \frac{L}{2 m^2} \left\| \nabla f(x) \right\|_2^2 }

{\displaystyle \;\;\; \Leftrightarrow \frac{L}{2 m^2} \left\| \nabla f(x^{+}) \right\|_2 \le \left( \frac{L}{2 m^2} \left\| \nabla f(x) \right\|_2 \right)^2 }

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


[ 1.8. 定理の証明 ]

定理.の証明は以下です．

'--------------------------------------------------------------------------------------------------------------------------------------------
定理.の証明

はじめに(1.1.1)を証明する．{\displaystyle k \le k_0 } のとき，以下を得る．

(1.8.1){\displaystyle \;\;\; f(x^{(k+1)}) \le f(x^{(k)}) - \gamma \;\;\; \because } 事実1.

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f(x^{(k-1)}) - 2 \gamma \;\;\; \because } 事実1.
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \cdot \cdot \cdot }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f(x^{(0)}) - (k+1) \gamma \;\;\; \because } 事実1.

{\displaystyle \;\;\; \Leftrightarrow \ f(x^{(k)}) \le f(x^{(0)}) - k \gamma }

{\displaystyle \;\;\; \Leftrightarrow \ f(x^{(k)}) - p^* \le f(x^{(0)}) - p^* - k \gamma }


つぎに(1.1.2)を証明する．{\displaystyle k \ge k_0 + 1 } のとき，以下を得る．

(1.8.2){\displaystyle \;\;\; \frac{L}{2 m^2} \left\| \nabla f(x^{(k+1)}) \right\|_2 \le \left( \frac{L}{2 m^2} \left\| \nabla f(x^{(k)}) \right\|_2 \right)^2 \;\;\; \because } 事実2.

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \left( \left( \frac{L}{2 m^2} \left\| \nabla f(x^{(k - 1)}) \right\|_2 \right)^2 \right)^2 \;\;\; \because } 事実2.
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \left( \frac{L}{2 m^2} \left\| \nabla f(x^{(k - 1)}) \right\|_2 \right)^{2^2} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \cdot \cdot \cdot }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \left( \frac{L}{2 m^2} \left\| \nabla f(x^{(k_0 + 1)}) \right\|_2 \right)^{2^{ k - k_0 }} \;\;\;\; \because } 事実2.

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \left( \frac{L}{2 m^2} \eta \right)^{2^{ k - k_0 }} \;\;\; \because \left\| \nabla f(x^{(k_0 + 1)}) \right\|_2 \lt \eta }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \left( \frac{1}{2} \frac{1}{\eta} \eta \right)^{2^{ k - k_0 }} \;\;\; \because } (1.1.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left( \frac{1}{2} \right)^{2^{ k - k_0 }} }

{\displaystyle \;\;\;\;\;\;\;\; \Leftrightarrow \ \frac{L}{2 m^2} \left\| \nabla f(x^{(k)}) \right\|_2 \le \left( \frac{1}{2} \right)^{2^{ k - k_0 - 1 }} }

{\displaystyle \;\;\;\;\;\;\;\; \Leftrightarrow \ \left[ \frac{L}{2 m^2} \left\| \nabla f(x^{(k)}) \right\|_2 \right]^2 \le \left[ \left( \frac{1}{2} \right)^{2^{ k - k_0 - 1 }} \ \right]^2 }

{\displaystyle \;\;\;\;\;\;\;\; \Leftrightarrow \ \frac{L^2}{4 m^4} \left\| \nabla f(x^{(k)}) \right\|_2^2 \le \left( \frac{1}{2} \right)^{2^{ k - k_0 }} }

{\displaystyle \;\;\;\;\;\;\;\; \Leftrightarrow \ \frac{1}{2 m} \left\| \nabla f(x^{(k)}) \right\|_2^2 \le \frac{2 m^3}{L^2} \left( \frac{1}{2} \right)^{2^{ k - k_0 }} \;\;\;\;\;\; } (1.7.2)(※)


冒頭の過去記事(制約なし凸最適化問題の目的関数)(1.1.5)より以下を得る．

(1.8.3){\displaystyle \;\;\; f(x^{(k)}) - \ p^* \le \frac{1}{2m} \left\| \nabla f(x^{(k)}) \right\|_2^2 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{2 m^3}{L^2} \left( \frac{1}{2} \right)^{2^{ k - k_0 }} \;\;\; \because } (1.7.2)(※)

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------

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

以上，制約なし凸最適化問題に対するニュートン法の，目的関数に強凸性，そのヘッセ行列にリプシッツ連続性を仮定するときの収束解析をまとめました．



参考文献
[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] Carnegie Mellon University Ryan Tibshirani先生のノート https://www.stat.cmu.edu/~ryantibs/convexopt-F18/scribes/Lecture_14.pdf
[5] The University of Texas at Austin Constantine Caramanis先生らのノート http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_7_Scribe_Notes.final.pdf

[6] Wikipedia Lipschitz continuity のページ https://en.wikipedia.org/wiki/Lipschitz_continuity
[7] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm
[8] Wikipedia Cauchy-Schwarz inequality のページ https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
[9] Stanford University Stephen Boyd先生のノート http://210.43.0.57/moocresource/data/20100601/U/stanford201001009/review7_single.pdf