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

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

降下法の枠組みと，厳密直線探索，バックトラッキング直線探索の概要をまとめる

数学 数理最適化

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

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

ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめる - エンジニアを目指す浪人のブログ


本記事は，Boyd and Vandenberghe(2004)の9章2節の内容をまとめたものです．降下法(descent method)という枠組みについて説明していきます．

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

目次

{\displaystyle \; } 0. 準備

{\displaystyle \; } 1. 降下法
{\displaystyle \;\;\; } 1.1. 降下法の枠組み
{\displaystyle \;\;\; } 1.2. 厳密直線探索
{\displaystyle \;\;\; } 1.3. バックトラッキング直線探索



[ 0. 準備 ]

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



[ 1. 降下法 ]

[ 1.1. 降下法の枠組み ]

勾配降下法(gradient descent method)やニュートン法(newton's method)などのアルゴリズムは，降下法という枠組みに含まれると考えることができます．そのようなアルゴリズムは，以下で表現される最小化列(minimizing sequence) {\displaystyle \{ x^{(k)}\}, k= 0,1,\ldots } を生成するものです．{\displaystyle t^{(k)} \gt 0 } です(ただし {\displaystyle x^{(k)} } が最適点 {\displaystyle x^* } に等しい場合は除きます)．

(1.1.1){\displaystyle \;\;\; x^{(k + 1)} = x^{(k)} + t^{(k)} \Delta x^{(k)} }

{\displaystyle \Delta x^{(k)} \in \mathbb{R}^n } はステップ(step)あるいは探索方向(search direction)といいます(ノルム {\displaystyle 1 } である必要はありませんが)．{\displaystyle k= 0,1,\ldots } は反復回数(iteration number)です．スカラー {\displaystyle t^{(k)} \ge 0} は反復 {\displaystyle k } でのステップサイズ(step size)あるいはステップ長(step length)といいます({\displaystyle \left\| \Delta x^{(k)} \right\| = 1 } である場合を除いて {\displaystyle t^{(k)} \neq \left\| x^{(k+1)} - x^{(k)} \right\| } となりますが)．なお(1.1.1)の代わりに，添え字をおとした以下を用いることもあります．

(1.1.2){\displaystyle \;\;\; x^{+} = x + t \Delta x }


降下法とは，以下が成り立つすべての方法のことをいいます．

(1.1.3){\displaystyle \;\;\; f(x^{(k+1)}) \lt f(x^{(k)}), \;\;\; x^{(k)} \in S \cap \{ x^* \}^c , \;\; k = 0, 1, \ldots }

これより以下が成り立ちます．

(1.1.4){\displaystyle \;\;\; x^{(k)} \in (S \cap \{ x^* \}^c) \subseteq \mathrm{dom} \ f, \;\; k = 0, 1, \ldots }

{\displaystyle f } は(二階)微分可能と凸を仮定している関数なので、冒頭の過去記事(ラグランジュ関数)(0.9)より以下を得ます．

(1.1.5){\displaystyle \;\;\; f(y) \ge f(x) + \nabla f(x)^T (y - x) }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow f(y) \ge f(x^{(k)}) + \nabla f(x^{(k)})^T (y - x^{(k)}) }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow f(y) - f(x^{(k)}) \ge \nabla f(x^{(k)})^T (y - x^{(k)}) }

{\displaystyle \;\;\;\;\;\; \Rightarrow \; \left[ \nabla f(x^{(k)})^T (y - x^{(k)}) \ge 0 \; \Rightarrow \; f(y) - f(x^{(k)}) \ge 0 \right] }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \; \left[ f(y) - f(x^{(k)}) \lt 0 \; \Rightarrow \; \nabla f(x^{(k)})^T (y - x^{(k)}) \lt 0 \right] }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \; \left[ f(y) \lt f(x^{(k)}) \; \Rightarrow \; \nabla f(x^{(k)})^T (y - x^{(k)}) \lt 0 \right] }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \; \left[ f(x^{(k+1)}) \lt f(x^{(k)}) \; \Rightarrow \; \nabla f(x^{(k)})^T (x^{(k+1)} - x^{(k)}) \lt 0 \right] }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \; \left[ f(x^{(k+1)}) \lt f(x^{(k)}) \; \Rightarrow \; \nabla f(x^{(k)})^T \left( t^{(k)} \Delta x^{(k)} \right) \lt 0 \right] \;\;\; \because } (1.1.1)

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \; \left[ f(x^{(k+1)}) \lt f(x^{(k)}) \; \Rightarrow \; \nabla f(x^{(k)})^T \ \Delta x^{(k)} \lt 0 \right] \;\;\; \because t^{(k)} \gt 0 }

これと(1.1.3)より(制約なし凸最適化問題に降下法を適用すると)探索方向 {\displaystyle \Delta x^{(k)} } について以下が成り立ちます．

(1.1.6){\displaystyle \;\;\; \nabla f(x^{(k)})^T \ \Delta x^{(k)} \lt 0, \;\;\; x^{(k)} \in S \cap \{ x^* \}^c , \;\; k = 0, 1, \ldots }

すなわち，勾配 {\displaystyle \nabla f(x^{(k)}) } ({\displaystyle x^{(k)} } から少し動いたときに {\displaystyle f } の値が最も大きくなる向きを持ちます)に対して鈍角とならなければなりません．いいかえると，{\displaystyle - \nabla f(x^{(k)}) } ({\displaystyle x^{(k)} } から少し動いたときに {\displaystyle f } の値が最も小さくなる向きを持ちます)に対して鋭角とならなければなりません．そのような方向を({\displaystyle f } の {\displaystyle x^{(k)} } での)降下方向(descent direction)といいます．


降下法の枠組みの概要は以下です．探索方向 {\displaystyle \Delta x } の決定，ステップサイズ {\displaystyle t } の選択，という二つのステップを交互に繰り返します．

f:id:seetheworld1992:20201114193716p:plain

ステップ2は直線 {\displaystyle \{ x + t \Delta x \ | \ t \in [ 0 , \infty ) \} } 上の {\displaystyle t } を選択するので直線探索(line search)といいます(より正確には半直線探索(ray search)ですが)．

実用的な降下法はこのような枠組みで説明できますが，異なる場合もあります．例えば，停止基準は大抵の場合降下方向 {\displaystyle \Delta x} の計算中あるいは直後に判定されます．停止基準は冒頭の過去記事(制約なし凸最適化問題)(1.1.6)のように {\displaystyle \eta } を正の小さい値として {\displaystyle \left\| \nabla f(x) \right\|_2 \le \eta } の形式であることが多いです．


[ 1.2. 厳密直線探索 ]

直線探索法の一つでときどき用いられるものに厳密直線探索(exact line search)があります．これは半直線 {\displaystyle \{ x + t \Delta x \ | \ t \ge 0 \} } 上の {\displaystyle f } を最小化する {\displaystyle t } を選択するものです:

(1.2.1){\displaystyle \;\;\; t^{(k)} = \mathrm{arg \ min}_{ s \ge 0 } \ f( x^{(k)} + s \Delta x^{(k)} ) }

厳密直線探索は，一変数最小化問題(1.2.1)の計算コストが，探索方向 {\displaystyle x^{(k)} } の計算コストに比べて小さい場合に使用されます．いくつかの特殊なケースのように半直線に沿った最小値が解析的に発見されることもあれば，他のケースのように効率的に計算されることもあります．



[ 1.3. バックトラッキング直線探索 ]

実際に用いられる直線探索のほとんどは非厳密(inexact)です: ステップ長 {\displaystyle t } は半直線 {\displaystyle \{ x + t \Delta x \ | \ t \ge 0 \} } 上における {\displaystyle f } を近似的に最小化する，あるいは十分小さくするものです．多くの非厳密直線探索法が提案されてきました．その中でバックトラッキング直線探索(backtracking line search)は非常に簡単で効果的なものです．二つの定数 {\displaystyle \alpha \in (0,0.5), \; \beta \in (0,1) } に依存します．

f:id:seetheworld1992:20201114193421p:plain

停止条件は以下です．

(1.3.1){\displaystyle \;\;\; f(x + t \Delta x) \le f(x) + \alpha t \nabla f(x)^T \Delta x }

バックトラッキング直線探索はステップ長の初期値を単位長さ(すなわち {\displaystyle 1 } )とし停止条件(1.3.1)をみたすまで {\displaystyle t } を係数 {\displaystyle \beta } により減少させることから，バックトラッキングといいます．{\displaystyle \Delta x } は探索方向であることから(1.1.6)が成り立っており十分小さい {\displaystyle t } について以下を得ます．

(1.3.2){\displaystyle \;\;\; f(x + t \Delta x) \approx f(x) + t \nabla f(x)^T \Delta x \;\;\;\; \because } テイラーの定理(文献[2]にあります)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lt f(x) + \alpha t \nabla f(x)^T \Delta x \;\;\; \because \alpha \in (0,0.5), \; } (1.1.6)

したがってバックトラッキング直線探索はいずれ停止条件(1.1.3)をみたして終了します．定数 {\displaystyle \alpha } は，線形外挿によって予測される {\displaystyle f } の減少のうち、受け入れることができる割合として解釈することができます({\displaystyle \alpha } が {\displaystyle 0.5 } よりも小さいという条件は，目的関数が強凸のときにバックトラッキング直線探索が終了するための必要条件です)．

f:id:seetheworld1992:20201117073009p:plain

Figure 9.1. はバックトラッキングの説明を示します．これより停止条件(1.3.1)は {\displaystyle t \in (0,t_0 ] } のとき成り立つことが読み取れます．したがってバックトラッキング直線探索は以下のどちらかをみたす {\displaystyle t} のとき終了することがわかります．

(1.3.3){\displaystyle \;\;\; t = 1 }
(1.3.4){\displaystyle \;\;\; t \in ( \beta t_0,t_0 ] }

一つ目の場合(1.3.3)は {\displaystyle t = 1 } が(1.3.1)をみたす，すなわち {\displaystyle 1 \le t_0 } のときに起こります．したがってバックトラッキング直線探索により得られるステップ長は以下をみたします．

(1.3.5){\displaystyle \;\;\; \min \{ 1, \beta t_0 \} \le t }

{\displaystyle \mathrm{dom} \ f \neq \mathbb{R}^n } のとき，条件(1.3.1)はより注意深く解釈する必要があります．{\displaystyle x \in \left( \mathbb{R}^n \setminus \mathrm{dom} \ f \right) } のとき {\displaystyle f(x) \to \infty } とすると(つまり，そのような仮定をおくと)，(1.3.1)をみたすためには {\displaystyle x + t \Delta x \in \mathrm{dom} \ f } でなければなりません．実装では {\displaystyle x + t \Delta x \in \mathrm{dom} \ f } をみたすまで {\displaystyle t } に {\displaystyle \beta } を乗じます; それから(1.3.1)の判定を始めます．

パラメータ {\displaystyle \alpha } は通常 {\displaystyle 0.01 } から {\displaystyle 0.3 } の間で選択され，線形外挿に基づく予測値に対する {\displaystyle t } の感度を {\displaystyle 1 }% から {\displaystyle 30 }% の間の(選択した)値に減少させることを意味します．パラメータ {\displaystyle \beta } は {\displaystyle 0.1 } (非常に粗い探索に相当)から {\displaystyle 0.8 } (粗くない探索に相当)の間で選択されることが多いです．

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

以上，降下法の枠組みと，厳密直線探索，バックトラッキング直線探索の概要をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Taylor's theorem のページ https://en.wikipedia.org/wiki/Taylor%27s_theorem