API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
85
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 68.68 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[uplatex, dvipdfmx]{jsarticle}
  2.  
  3. %
  4. % ヘッダ類
  5. % 日付は自動的につける
  6. %
  7. \title{直線探索に関するノート} % タイトル
  8. \author{竹内 弘史} % 著者
  9.  
  10. %
  11. % パッケージ
  12. %
  13. \usepackage{amssymb, bm, amsthm}
  14. \usepackage{newtxtext, newtxmath}
  15. \usepackage{algorithm, algorithmic}
  16. \usepackage{color}
  17. \usepackage{mathrsfs}
  18. \usepackage{booktabs}
  19. \usepackage{enumerate}
  20. \usepackage{listings, jlisting}
  21. \usepackage{tikz}
  22. \usetikzlibrary{decorations.pathreplacing, shadows}
  23. % \usepackage{refcheck} % 参照確認用
  24.  
  25. %
  26. % 定理環境
  27. % sectionを親にして連番とする
  28. %
  29. \theoremstyle{definition}
  30. \newtheorem{thm}{Theorem}[section]
  31. \newtheorem{dfn}[thm]{Definition}
  32. \newtheorem{prop}[thm]{Proposition}
  33. \newtheorem{cor}[thm]{Corollary}
  34. \newtheorem{prob}[thm]{Problem}
  35. \newtheorem{lem}[thm]{Lemma}
  36. \newtheorem{note}[thm]{Note}
  37. \newtheorem{claim}{Claim}
  38.  
  39. %
  40. % 数学記号系の定義
  41. %
  42. \newcommand{\Alert}[1]{\textbf{\color{red}#1}}
  43. \newcommand{\Structure}[1]{\textbf{\color{blue}#1}}
  44.  
  45. %
  46. % 数学記号系の定義
  47. %
  48. \renewcommand{\le}{\leqslant} % 不等号再定義（デザイン変更）
  49. \renewcommand{\ge}{\geqslant} % 不等号再定義（デザイン変更）
  50. \renewcommand{\implies}{\Rightarrow} % 含意再定義（デザイン変更）
  51. \renewcommand{\iff}{\Leftrightarrow} % 同値再定義（デザイン変更）
  52.  
  53. % 数式中の改ページを許す
  54. \allowdisplaybreaks[4]
  55.  
  56. % jsarticleのための付録の表示調整
  57. %
  58. % 付録は以下のように書く
  59. % > \section{ ...通常の節... }
  60. % > ......
  61. % > \section{ ...通常の節... }
  62. % >
  63. % > % 付録開始
  64. % > \appendix
  65. % > \AppendixSection{ ...付録の節... }
  66. % > ......
  67. % > \AppendixSection{ ...付録の節... }
  68. \newcommand{\AppendixSection}[1]{
  69. \def\thesection{付録\Alph{section}} %
  70. \section{#1} %
  71. \def\thesection{\Alph{section}}}
  72.  
  73. % listings言語設定
  74. \lstdefinelanguage{Python}{
  75. % キーワード
  76. morekeywords = [1]{def, if, else, elif, for, return, raise,
  77. in, range, try, except, import, as, lambda},
  78. % クラス
  79. morekeywords = [2]{Exception, str}
  80. }
  81.  
  82. % listings設定
  83. \lstset{%
  84. language={Python},%
  85. basicstyle={\footnotesize\ttfamily},%
  86. commentstyle={\footnotesize\ttfamily},%
  87. keywordstyle={\footnotesize\bfseries},%
  88. frame={single},%
  89. numbers=left,%
  90. showstringspaces=false,%
  91. numberstyle={\scriptsize},%
  92. lineskip=-1pt}
  93.  
  94.  
  95. \begin{document}
  96.  
  97. \maketitle
  98.  
  99. \section{はじめに}
  100.  
  101. 無制約最適化問題では最急降下法をはじめとするいくつかの解法が知られている．
  102. 通常，これらの解法では，降下方向と呼ばれる目的関数の値を小さくする方向に，ステップ幅によって決まる大きさだけ近似値を逐次更新する方法がとられる．
  103. このステップ幅の調整は直線探索と呼ばれるが，最急降下法や非線形共役勾配法では，各更新におけるステップ幅がWolfe条件を満たせば，
  104. それら解法によって得られる近似解の列が，何らかの意味で最適解へ収束することが知られている．
  105.  
  106. 本稿では，\cite{Nocedal1}をもとに，Wolfe条件を満たすステップ幅の求め方を中心にまとめる．
  107.  
  108. 本稿の構成は以下のとおりである．
  109. 第2節では，無制約最適化問題の基礎事項についてまとめる．
  110. ただし，本稿で必要な範囲のみ述べる．
  111. 第3節では，Wolfe条件とそれに関連した事実についてまとめ，第4, 5節では具体的な直線探索のアルゴリズムについてまとめる．
  112. 付録ではPythonによる実装例を載せる．
  113.  
  114. \section{無制約最適化問題の基礎事項}
  115.  
  116. 本節では，最適化問題に関する基礎事項について述べる．
  117. ただし，本節で述べる内容は本稿で必要な範囲に限る．
  118. また，本稿を通して，解析学および数値解析で知られている基本的な事実は説明なく用いる．
  119.  
  120. $f:\mathbb{R}^n\to\mathbb{R}$とする．
  121. $f$を最小化する$x\in\mathbb{R}^n$を求める問題を，\Alert{無制約最適化問題}と呼ぶ．
  122. 最適化問題の対象とする関数を\Alert{目的関数}と呼ぶ．
  123. 無制約最適化問題の解法として，反復法による数値計算が広く利用されている．
  124. 具体的には，$x_0\in\mathbb{R}^n$を初期点とし，
  125. \begin{align}
  126. x_{k+1}=x_k+\alpha_kp_k,\quad k=0,1,\dots\label{eq:update}
  127. \end{align}
  128. と近似解を更新する方法である．
  129. ただし，$\alpha_k\in\mathbb{R}$, $p_k\in\mathbb{R}^n$とする．
  130.  
  131. \eqref{eq:update}における$p_k\in\mathbb{R}^n$は，近似解$x_k$を更新する方向を表すベクトルであるが，この方向は目的関数の値が小さくなるようにとることが望ましい．
  132. そこで，$p_k$は，
  133. \begin{align}
  134. \lim_{\lambda\to0}\frac{f(x_k+\lambda p_k)-f(x_k)}{\lambda}<0\label{eq:decent}
  135. \end{align}
  136. を満たす方向をとることを要求する．
  137. \eqref{eq:decent}の左辺は$f$の$x_k$における$p_k$に沿った方向微分と呼ばれ，$x_k$を$p_k$に微小変化させたときの，$x_k$の変化に対する$f$の変化の割合を表す．
  138. この値が負ならば，$x_k$を$p_k$の方向へ更新すると$f$の関数値が小さくなることが期待される．
  139. $f$が$x_k$において微分可能ならば，$f(x_k+\lambda p_k)=f(x_k)+\lambda\nabla f(x_k)^Tp_k+o(\lambda)$とTaylor展開できるため，
  140. \[ \lim_{\lambda\to0}\frac{f(x_k+\lambda p_k)-f(x_k)}{\lambda}=\nabla f(x_k)^Tp_k \]
  141. が成り立つ．
  142. ただし，$\nabla f(x)=(\partial f(x)/\partial x_1,\partial f(x)/\partial x_2,\dots,\partial f(x)/\partial x_n)^T$すなわち$f$の勾配を表し, $\cdot^T$は転置作用素を表す．
  143. したがって，更新\eqref{eq:update}において，$p_k$は$\nabla f(x_k)^Tp_k<0$を満たすようにとり，$\alpha_k$は$\alpha_k>0$の範囲で考えればよい．
  144. $\nabla f(x_k)^Tp_k<0$を満たす$p_k$は$x_k$における\Alert{降下方向}と呼ばれ，更新\eqref{eq:update}における$\alpha_k$は\Alert{ステップ幅}と呼ばれる．
  145.  
  146. 具体的な降下方向のとり方としては，$p_k=-\nabla f(x_k)$ととる方法が考えられる．
  147. このとき，$\nabla f(x_k)^Tp_k=-\|\nabla f(x_k)\|<0$を満たすため$p_k$は降下方向である．
  148. $\|p\|=1$の条件で$\nabla f(x_k)^Tp$を最小にする$p$は$p=-\nabla f(x_k)/\|\nabla f(x_k)\|$となることから，$p_k=-\nabla f(x_k)$を$x_k$における\Alert{最急降下方向}と呼ぶ．
  149.  
  150. 降下方向の具体的なとり方として最急降下方向をとればよいことを述べたが，ステップ幅の具体的なとり方については本節では言及していない．
  151. 次節以降で，近似解の列$\{x_k\}$が収束するためにステップ幅が満たすべき条件や，その具体的なとり方について述べる．
  152. 各反復における適切なステップ幅の探索を\Alert{直線探索}と呼ぶ．
  153.  
  154. なお本稿では，簡単のため，$f_k=f(x_k)$, $\nabla f_k=\nabla f(x_k)$と略記することがある．
  155.  
  156. \section{Wolfe条件}
  157.  
  158. 本節では，\cite{Nocedal1}にしたがい，ステップ幅に関する条件であるWolfe条件およびそれに関連した事実についてまとめる．
  159. \begin{dfn}
  160. $0<c_1<c_2<1$とする．
  161. $\alpha_k$に関する以下の条件\eqref{eq:wolfe1}, \eqref{eq:wolfe2}を\Alert{Wolfe条件}という．
  162. 特に，\eqref{eq:wolfe1}を\Alert{十分な降下条件}, \eqref{eq:wolfe2}を\Alert{曲率条件}という．
  163. 十分な降下条件は\Alert{Armijo条件}として知られる．
  164. \begin{align}
  165. &f(x_k+\alpha_kp_k)\le f(x_k)+c_1\alpha_k\nabla f_k^Tp_k,\label{eq:wolfe1}\\
  166. &\nabla f(x_k+\alpha_kp_k)^Tp_k\ge c_2\nabla f_k^Tp_k\label{eq:wolfe2}
  167. \end{align}
  168. また，\eqref{eq:wolfe2}を
  169. \begin{align}
  170. |\nabla f(x_k+\alpha_kp_k)^Tp_k|\le c_2|\nabla f_k^Tp_k|\label{eq:wolfe3}
  171. \end{align}
  172. に取り替えた条件を\Alert{強いWolfe条件}という．
  173. \end{dfn}
  174.  
  175. $x_k$, $p_k$を固定し，$\phi:\mathbb{R}_{>0}\to\mathbb{R}$を，
  176. \begin{align*}
  177. \phi(\alpha)=f(x_k+\alpha p_k)
  178. \end{align*}
  179. と定める．
  180. $y_k=x_k+\alpha p_k$とすると，
  181. \begin{align*}
  182. \phi'(\alpha)&=\sum_{i=1}^n\frac{\partial f}{\partial (y_k)_i}\frac{\partial (y_k)_i}{\partial\alpha}\\
  183. &=\sum_{i=1}^n\frac{\partial f}{\partial (y_k)_i}(p_k)_i\\
  184. &=\nabla f(x_k+\alpha p_k)^Tp_k
  185. \end{align*}
  186. である．
  187. $f(x_k)=\phi(0)$, $\nabla f(x_k)^Tp_k=\phi'(0)$なので，\eqref{eq:wolfe1}--\eqref{eq:wolfe3}は$\phi$を使って次のように書ける．
  188. \begin{align}
  189. &\phi(\alpha_k)\le \phi(0)+c_1\alpha_k\phi'(0),\label{eq:wolfe1_phi}\\
  190. &\phi'(\alpha_k)\ge c_2\phi'(0),\label{eq:wolfe2_phi}\\
  191. &|\phi'(\alpha_k)|\le-c_2\phi'(0).\label{eq:wolfe3_phi}
  192. \end{align}
  193. 特に$\phi'(0)=\nabla f(x_k)^Tp_k<0$である．
  194. 直線探索においては，$x_k$, $p_k$は固定して$\alpha$のみを考えるため，\eqref{eq:wolfe1_phi}--\eqref{eq:wolfe3_phi}の$\phi$による表現を多用する．
  195.  
  196. 図\ref{fig:wolfe}に十分な降下条件，曲率条件，Wolfe条件を図示する．
  197. 以下，各条件の幾何的なイメージについて補足する．
  198.  
  199. 十分な降下条件を満たすステップ幅$\alpha$の範囲は，$l(\alpha)=\phi(0)+c_1\alpha\phi'(0)$とすると，$\phi(\alpha)$が直線$l(\alpha)$より小さい値をとる$\alpha$の範囲である．
  200. $c_1$は$0<c_1<1$の範囲にとるので，$\alpha$が十分な降下条件を満たせば，$\phi(\alpha)=f(x_k+\alpha p_k)$の値が$f(x_k)$より十分小さくなるような$\alpha$がとれることが期待される．
  201.  
  202. ただし，$\alpha\approx0$でも十分な降下条件を満たしてしまうため，十分な降下条件だけでは，近似解の更新が停滞してしまう可能性がある．
  203. そこで，ある程度の大きさのステップ幅をとることを要求するため，曲率条件を考える．
  204. 曲率条件を満たす$\alpha$の範囲は，接線の傾きが正か，接線の傾きが負の場合でも$c_2\phi'(0)$より緩やかな傾きとなる$\alpha$の範囲である．
  205. $c_2$は$0<c_1<c_2<1$の範囲にとり，$\phi'(0)<0$であることから，$\phi$の導関数が連続ならば，$\alpha=0$の近傍は曲率条件を満たさない．
  206.  
  207. 十分な降下条件と曲率条件をあわせたものがWolfe条件である．
  208. 以上の議論より，Wolfe条件を満たす$\alpha$をとれば，目的関数の値が小さくなり，かつある程度の大きさのステップ幅がとれることが期待される．
  209.  
  210. 本稿では，以降の節で，目的関数や降下方向に関する適当な仮定のもとで，Wolfe条件を満たすステップ幅がとれることや，
  211. Wolfe条件を満たすステップ幅をとりながら最適化問題を更新\eqref{eq:update}に基づく反復法で解いた場合，近似解の列$\{x_k\}$が収束することを示す．
  212.  
  213. \begin{figure}[!t]
  214. \centering
  215. \begin{tikzpicture}[auto, samples=100, very thick, xscale=5.0, yscale=2.0]
  216. % 軸の明示
  217. \draw[thick, ->] (-0.25, 0)--(1.7, 0) node[right] {$\alpha$};
  218. \draw[thick, ->] (-0.01, -0.5)--(-0.01, 3.0) node[above] { };
  219.  
  220. % φ(α) = 10α^4 - 30α^3 + (115/4)α^2 - (71/8)α + 1
  221. \draw[domain=-0.13:1.55] plot(\x, {5.0*((\x-0.75)*(\x-0.75)*(2*(\x-0.75)*(\x-0.75) - 1) + 0.1*(\x-0.75)) + 123.0/128.0}) node[above] {$\phi(\alpha)$};
  222.  
  223. % l(α) = φ(0)+c_1φ'(0)α = 1 - (71/8)c_1α
  224. % c_1 = 3/142のとき，l(α) = 1 - (3/16)*α
  225. \draw[domain=-0.25:1.7, dashed, thin] plot(\x, {1.0 - 0.1875*\x});
  226. \node[above] at (0.4, 0.95) {$\quad l(\alpha)=\phi(0)+c_1\phi'(0)\alpha$};
  227.  
  228. % Armijo条件を満たす範囲の座標
  229. \node (armijo1) at (0.66, 0.89) {};
  230. \node (armijo1_xaxis) at (0.66, -0.5) {};
  231. \node (armijo2) at (1.0, 0.82) {};
  232. \node (armijo2_xaxis) at (1.0, -0.5) {};
  233. \node (armijo3) at (1.35, 0.75153) {};
  234. \node (armijo3_xaxis) at (1.35, -0.5) {};
  235.  
  236. % 垂線を下ろす
  237. \draw[thin, dotted] (armijo1) -- (armijo1_xaxis);
  238. \draw[thin, dotted] (armijo2) -- (armijo2_xaxis);
  239. \draw[thin, dotted] (armijo3) -- (armijo3_xaxis);
  240.  
  241. % Armijo条件を満たす範囲
  242. \draw[thick, <->] (0.0, -0.4) -- (0.66, -0.4);
  243. \node at (0.35, -0.4) [below] {Armijo};
  244. \draw[thick, <->] (1.0, -0.4) -- (1.35, -0.4);
  245. \node at (1.19, -0.4) [below] {Armijo};
  246.  
  247. % Wolfe条件を満たす範囲の座標
  248. \node (wolfe1) at (0.1, 0.6) {};
  249. \node (wolfe1_xaxis) at (0.1, -0.3) {};
  250. \draw[thin, dotted] (wolfe1) -- (wolfe1_xaxis);
  251.  
  252. % 曲率条件における傾きの境界値
  253. \node at (-0.1, 1.6) [left] {$c_2\phi'(0)$};
  254. \draw[thin, dashed, domain=-0.15:0.1] plot(\x, {-71/8*0.4*(\x-0.01)+0.95});
  255. \draw[thin, dashed, domain=-0.05:0.2] plot(\x, {-71/8*0.4*(\x-0.1)+0.3});
  256.  
  257. % 曲率条件を満たす範囲
  258. \draw[thick, <-] (0.1, 0.15) -- (1.68, 0.15);
  259. \node at (0.83, 0.15) [above] {Curvature};
  260.  
  261. % Wolfe条件を満たす範囲
  262. \draw[thick, <->] (0.1, -0.1) -- (0.66, -0.1);
  263. \node at (0.37, -0.1) [below] {Wolfe};
  264. \draw[thick, <->] (1.0, -0.1) -- (1.35, -0.1);
  265. \node at (1.18, -0.1) [below] {Wolfe};
  266. \end{tikzpicture}
  267. \caption{十分な降下条件 (Armijo条件), 曲率条件，Wolfe条件の図．}
  268. \label{fig:wolfe}
  269. \end{figure}
  270.  
  271. \begin{lem}\label{lem:wolfe_exists}
  272. $f:\mathbb{R}^n\to\mathbb{R}$を連続的微分可能な関数と仮定する．
  273. $p_k$を$x_k$における降下方向とし，$f$は$\{x_k+\alpha p_k\mid\alpha>0\}$において下に有界であるとする．
  274. $0<c_1<c_2<1$ならば，Wolfe条件および強いWolfe条件を満たすステップ幅$\alpha$の区間が存在する．
  275. \end{lem}
  276. \begin{proof}
  277. $\phi(\alpha)=f(x_k+\alpha p_k)$とおく．
  278. この$\phi$は$\alpha>0$において下に有界で，$0<c_1<1$より，直線$l(\alpha)=f(x_k)+\alpha c_1\nabla f_k^Tp_k$と共有点をもつ．
  279. $\alpha'>0$を，その共有点のうち最小のものとする．
  280. このとき，
  281. \begin{align}
  282. f(x_k+\alpha'p_k)=f(x_k)+\alpha'c_1\nabla f_k^Tp_k\label{eq:lem_wolfe_exists_1}
  283. \end{align}
  284. が成り立ち，$0<\alpha<\alpha'$は十分な降下条件を満たす．
  285.  
  286. $f$は微分可能なので，平均値の定理から，
  287. \begin{align}
  288. f(x_k+\alpha'p_k)-f(x_k)=\alpha'\nabla f(x_k+\alpha''p_k)^Tp_k\label{eq:lem_wolfe_exists_2}
  289. \end{align}
  290. を満たす$0<\alpha''<a'$が存在する．
  291. \eqref{eq:lem_wolfe_exists_1}, \eqref{eq:lem_wolfe_exists_2}より，$c_1<c_2$かつ$\nabla f_k^Tp_k<0$なので，
  292. \[ \nabla f(x_k+\alpha''p_k)^Tp_k=c_1\nabla f_k^Tp_k>c_2\nabla f_k^Tp_k \]
  293. が成り立つ．
  294.  
  295. $0<\alpha''<\alpha'$なので，$\alpha''$は十分な降下条件を満たし，$\nabla f(x_k+\alpha''p_k)^Tp_k>c_2\nabla f_k^Tp_k$より，$\alpha''$は曲率条件も満たす．
  296. また，$f$が連続的微分可能で，$\alpha''<\alpha'$なので，
  297. \[ f(x_k+\alpha_kp_k)<f(x_k)+c_1\alpha_k\nabla f_k^Tp_k \]
  298. となることから，$\alpha''-\delta<\alpha<\alpha''+\delta$において，
  299. \begin{align*}
  300. &f(x_k+\alpha_kp_k)\le f(x_k)+c_1\alpha_k\nabla f_k^Tp_k,\\
  301. &\nabla f(x_k+\alpha_kp_k)^Tp_k\ge c_2\nabla f_k^Tp_k
  302. \end{align*}
  303. を満たすような$\delta>0$が存在する．
  304. したがって，Wolfe条件を満たすステップ幅の区間$(\alpha''-\delta,\alpha''+\delta)$が存在することが示された．
  305. また，$\alpha'$の定め方より$f(x_k+\alpha'p_k)-f(x_k)<0$なので，\eqref{eq:lem_wolfe_exists_2}より$\nabla f(x_k+\alpha''p_k)^Tp_k<0$となり，
  306. $\nabla f(x_k+\alpha''p_k)^Tp_k>c_2\nabla f_k^Tp_k$ならば$|\nabla f(x_k+\alpha''p_k)^Tp_k|<c_2|\nabla f_k^Tp_k|$である．
  307. よって，強いWolfe条件を満たすステップ幅の区間も$(\alpha''-\delta,\alpha''+\delta)$である．
  308. \end{proof}
  309.  
  310. Wolfe条件を満たすステップ幅を用いた，更新\eqref{eq:update}による最適化問題の反復解法の収束性について述べる．
  311. \begin{thm}
  312. 初期点$x_0$, 更新式\eqref{eq:update}による近似解の列$\{x_k\}$を考える．
  313. ただし，$p_k$は降下方向で，$\alpha_k$はWolfe条件を満たすと仮定する．
  314. $f$は下に有界で，レベル集合$\mathcal{L}:=\{x\mid f(x)\le f(x_0)\}$を含む開領域$\mathcal{N}$上で連続的微分可能とする．
  315. $\nabla f$は$\mathcal{N}$上でLipschitz連続であるとする．すなわち，
  316. 任意の$x$, $\tilde{x}\in\mathcal{N}$について，
  317. \[ \|\nabla f(x)-\nabla f(\tilde{x})\|\le L\|x-\tilde{x}\| \]
  318. を満たす定数$L>0$が存在すると仮定する．
  319. このとき，$\cos\theta_k=-\nabla f_k^Tp_k/(\|\nabla f_k\|\|p_k\|)$とおくと，
  320. \[ \sum_{k\ge0}\cos^2\theta_k\|\nabla f_k\|^2<\infty \]
  321. が成り立つ．
  322. \end{thm}
  323. \begin{proof}
  324. まず，曲率条件\eqref{eq:wolfe2}と近似解の更新式\eqref{eq:update}より，
  325. \[ c_2\nabla f(x_k)^Tp_k\le\nabla f(x_k+\alpha_kp_k)^Tp_k=\nabla f(x_{k+1})^Tp_k \]
  326. なので，両辺から$\nabla f(x_k)^Tp_k$を引くと，
  327. \[ (c_2-1)\nabla f(x_k)^Tp_k\le (\nabla f(x_{k+1})-\nabla f(x_k))^Tp_k \]
  328. となる．一方，$\nabla f$はLipschitz連続なので，Cauchy-Schwarzの不等式とあわせて，
  329. \begin{align*}
  330. (\nabla f(x_{k+1})-\nabla f(x_k))^Tp_k&\le\|\nabla f(x_{k+1})-\nabla f(x_k)\|\|p_k\|\\
  331. &\le L\|x_{k+1}-x_k\|\|p_k\|\\
  332. &=L\|(x_k+\alpha_kp_k)-x_k\|\|p_k\|\\
  333. &=\alpha_kL\|p_k\|^2
  334. \end{align*}
  335. を満たす定数$L>0$が存在する．したがって，
  336. \[ (c_2-1)\nabla f(x_k)^Tp_k\le\alpha_kL\|p_k\|^2 \]
  337. となり，整理すると，
  338. \[ \alpha_k\ge\frac{c_2-1}{L}\frac{\nabla f(x_k)^Tp_k}{\|p_k\|^2} \]
  339. となる．十分な降下条件\eqref{eq:wolfe1}より，$\nabla f(x_k)^Tp_k<0$とあわせて，
  340. \begin{align*}
  341. f(x_{k+1})&\le f(x_k)+c_1\alpha_k\nabla f(x_k)^Tp_k\\
  342. &\le f(x_k)+c_1\frac{c_2-1}{L}\frac{\nabla f(x_k)^Tp_k}{\|p_k\|^2}\cdot\nabla f(x_k)^Tp_k\\
  343. &=f(x_k)-c_1\frac{1-c_2}{L}\frac{(\nabla f(x_k)^Tp_k)^2}{\|p_k\|^2}
  344. \end{align*}
  345. が得られる．ここで，$\theta_k$の定義より，$c=c_1(1-c_2)/L$とおくと，
  346. \[ f(x_{k+1})\le f(x_k)-c\cos^2\theta_k\|\nabla f(x_k)\|^2 \]
  347. となるため，
  348. \[ f(x_{k+1})\le f(x_0)-c\sum_{j=0}^k\cos^2\theta_j\|\nabla f_j\|^2 \]
  349. が成り立つ．
  350.  
  351. ここで，$f$は下に有界なので，任意の$k$に対して$(f(x_0)-f(x_{k+1}))/c<M$となる定数$M>0$が存在する．したがって，任意の$k$について，
  352. \[ \sum_{j=0}^k\cos^2\theta_j\|\nabla f(x_j)\|^2\le\frac{f(x_0)-f(x_{k+1})}{c}<M\]
  353. となるため，
  354. \[ \sum_{k=0}^{\infty}\cos^2\theta_k\|\nabla f(x_k)\|^2<\infty \]
  355. が成り立つ．
  356. \end{proof}
  357.  
  358. \begin{dfn}
  359. 目的関数$f$, $x_k$を第$k$反復の近似解，$p_k$を第$k$反復の降下方向，$\alpha_k$を第$k$反復のステップ幅として，
  360. 点列$\{x_k\}$を\eqref{eq:update}によって生成するとき，$\cos\theta_k=-\nabla f_k^Tp_k/(\|\nabla f_k\|\|p_k\|)$に対して，
  361. \[ \sum_{k\ge0}\cos^2\theta_k\|\nabla f_k\|^2<\infty \]
  362. を満たすならば，点列$\{x_k\}$は\Alert{Zoutendijk条件}を満たすという．
  363. \end{dfn}
  364.  
  365. \begin{cor}
  366. $\{x_k\}$がZoutendijk条件を満たし，かつ$\cos\theta_k=-\nabla f_k^Tp_k/(\|\nabla f_k\|\|p_k\|)\ge\delta$を満たす$\delta>0$が存在するならば，
  367. \begin{align}
  368. \lim_{k\to\infty}\|\nabla f_k\|=0\label{eq:conv}
  369. \end{align}
  370. を満たす．
  371. \end{cor}
  372. \begin{proof}
  373. $\{x_k\}$がZoutendijk条件を満たすならば，$\lim_{k\to\infty}\cos^2\theta_k\|\nabla f_k\|^2=0$である．$\cos\theta_k\ge\delta>0$より，\eqref{eq:conv}が成り立つ．
  374. \end{proof}
  375.  
  376. \begin{cor}\label{cor:1}
  377. 初期点$x_0$, 更新式\eqref{eq:update}による近似解の列$\{x_k\}$を考える．
  378. $p_k$は降下方向で，$\alpha_k$はWolfe条件を満たすと仮定する．
  379. $f$は下に有界で，レベル集合$\mathcal{L}:=\{x\mid f(x)\le f(x_0)\}$を含む開領域$\mathcal{N}$上で連続的微分可能とする．
  380. $\nabla f$は$\mathcal{N}$上でLipschitz連続とする．
  381. $\cos\theta_k=-\nabla f_k^Tp_k/(\|\nabla f_k\|\|p_k\|)\ge\delta$を満たす$\delta>0$が存在するように$p_k$をとれば，\eqref{eq:conv}が成り立つ．
  382. \end{cor}
  383. \begin{proof}
  384. 以上の結果をまとめると得られる．
  385. \end{proof}
  386.  
  387. $p_k$を最急降下方向，すなわち$p_k=-\nabla f_k$ととって\eqref{eq:update}によって近似解を逐次更新して最適化を求める方法を，\Alert{最急降下法}と呼ぶ．
  388.  
  389. \begin{cor}
  390. $x_0$を初期点とする．
  391. $f$は下に有界で，レベル集合$\mathcal{L}:=\{x\mid f(x)\le f(x_0)\}$を含む開領域$\mathcal{N}$上で連続的微分可能とする．
  392. $\nabla f$は$\mathcal{N}$上でLipschitz連続とする．
  393. このとき最急降下法により生成された近似解の列$\{x_k\}$は\eqref{eq:conv}を満たす．
  394. \end{cor}
  395. \begin{proof}
  396. $\cos\theta_k=1>0$なので系\ref{cor:1}において$\delta=1$ととれるため成り立つ．
  397. \end{proof}
  398.  
  399. Wolfe条件を満たすステップ幅をとれば，適当な仮定のもとで最急降下法が収束することが示された．
  400. また，これも適当な仮定のもとで，Wolfe条件を満たすステップ幅がとれることも示した．
  401. ただし，本節の議論では，Wolfe条件を満たすステップ幅をどのように求めるかについては述べていない．
  402. 具体的なステップ幅の探索については次節以降で述べる．
  403.  
  404. \section{補間法による十分な降下条件を満たすステップ幅の探索}
  405.  
  406. 本節では，\cite{Nocedal1}にしたがい，補間法による十分な降下条件を満たすステップ幅の具体的な求め方についてまとめる．
  407. ただし，\cite{Nocedal1}では省略されている議論も補足する．
  408. Wolfe条件を満たすステップ幅の探索については次節で述べる．
  409.  
  410. まず，十分な降下条件\eqref{eq:wolfe1}を満たすステップ幅$\alpha_k$の選び方について述べる．
  411. $\alpha$の下付き添字は，更新\eqref{eq:update}における反復回数を表していたが，本節以降では$\alpha$の下付き添字を直線探索における反復回数を表すこととする．
  412.  
  413. いま，初期推定値$\alpha_0$が与えられたと仮定する．
  414. もし，
  415. \[ \phi(\alpha_0)\le \phi(0)+c_1\alpha_0\phi'(0) \]
  416. であれば，このステップ幅は十分な降下条件を満たすので探索は終了する．
  417. そうでなければ，区間$[0,\alpha_0]$は十分な降下条件を満たすステップ幅を含む．
  418. \begin{prop}\label{prop:phi_q}
  419. 正の実数$\alpha_0$が，
  420. \begin{align}
  421. \phi(\alpha_0)>\phi(0)+c_1\alpha_0\phi'(0)\label{eq:not_wolfe1}
  422. \end{align}
  423. を満たすと仮定する．
  424. $\phi_q$を，
  425. \[ \phi_q(0)=\phi(0),\quad \phi_q'(0)=\phi'(0),\quad \phi(\alpha_0)=\phi(\alpha_0) \]
  426. を満たす2次関数とする．
  427. このとき，以下の性質が成り立つ．
  428. \begin{enumerate}
  429. \item $\phi_q$は，
  430. \begin{align}
  431. \phi_q(\alpha)=\left(\frac{\phi(\alpha_0)-\phi(0)-\alpha_0\phi'(0)}{\alpha_0^2}\right)\alpha^2+\phi'(0)\alpha+\phi(0)\label{eq:phi_q}
  432. \end{align}
  433. と表される．
  434. \item $\phi_q$は極小値をもつ．
  435. \item 極小値を与える$\alpha=\alpha_1$は
  436. \begin{align}
  437. \alpha_1=-\frac{\phi'(0)\alpha_0^2}{2(\phi(\alpha_0)-\phi(0)-\phi'(0)\alpha_0)}\label{eq:alpha_1}
  438. \end{align}
  439. で与えられる．
  440. \item $c_1\le 1/2$ならば，$0<\alpha_1<\alpha_0$が成り立つ．
  441. \end{enumerate}
  442. \end{prop}
  443. \begin{proof}
  444. まず1.を示す．
  445. $\phi_q$に関する初めの2つの条件から，$\phi_q$は実数$a$によって，
  446. \[ \phi_q(\alpha)=a\alpha^2+\phi'(0)\alpha+\phi(0) \]
  447. と表せるが，$\alpha=\alpha_0$を代入すれば，$a=(\phi_q(\alpha_0)-\phi'(0)\alpha_0-\phi(0))/\alpha_0^2=(\phi(\alpha_0)-\phi'(0)\alpha_0-\phi(0))/\alpha_0^2$となる．
  448. したがって，$\phi_q$は\eqref{eq:phi_q}と表される．
  449. よって1.が示された．
  450. 次に2.を示す．
  451. $\phi'(0)<0$と\eqref{eq:not_wolfe1}より，
  452. \[ a=\frac{\phi(\alpha_0)-\phi'(0)\alpha_0-\phi(0)}{\alpha_0^2}>\frac{\phi(\alpha_0)-c_1\phi'(0)\alpha_0-\phi(0)}{\alpha_0^2}>0 \]
  453. となり，最高次係数は0ではないので$\phi_q$は2次関数である．
  454. 特に最高次係数が正なので2次関数$\phi_q$は極小値をもつ．
  455. よって，2.が示された．
  456. 3.を示す．
  457. 極小値を与える$\alpha=\alpha_1$は，$\phi'(\alpha)=0$を満たす唯一の$\alpha$なので，$\phi'(\alpha)=2a\alpha+\phi'(0)$より，$\alpha_1=-\phi'(0)/(2a)$と表される．
  458. したがって，\eqref{eq:alpha_1}となり，3.が示された．
  459. 4.を示す．
  460. $\phi'(0)<0$より，\eqref{eq:phi_q}から，
  461. \[ \phi(\alpha_0)>\phi(0)+c_1\alpha_0\phi'(0)\ge\phi(0)+\frac{1}{2}\alpha_0\phi'(0) \]
  462. であるが，両辺から$\phi(0)+\phi'(0)\alpha$をひいてから2倍すると，
  463. \begin{align}
  464. 2(\phi(\alpha_0)-\phi(0)-\phi'(0)\alpha_0)>-\alpha_0\phi'(0)\label{eq:0_alpha1_alpha0_1}
  465. \end{align}
  466. である．
  467. $\phi'(0)<0$より\eqref{eq:0_alpha1_alpha0_1}の両辺とも正であるため，両辺を右辺で割ると，
  468. \[ 0<-\frac{\phi'(0)\alpha_0}{2(\phi(\alpha_0)-\phi(0)-\phi'(0)\alpha_0)}< 1\]
  469. が得られる．
  470. すべての辺を$\alpha_0\,(>0)$倍すれば，
  471. \[ 0<-\frac{\phi'(0)\alpha_0^2}{2(\phi(\alpha_0)-\phi(0)-\phi'(0)\alpha_0)}< \alpha_0 \]
  472. すなわち$0<\alpha_1<\alpha_0$が得られる．
  473. よって4.が示された．
  474. \end{proof}
  475.  
  476. この$\alpha_1$が
  477. \[ \phi(\alpha_1)\le \phi(0)+c_1\alpha_1\phi'(0) \]
  478. であれば，このステップ幅は十分な降下条件を満たすので探索は終了する．
  479. そうでなければ，区間$[0,\alpha_1]$は十分降下条件を満たすステップ幅を含む．
  480. $\phi$を3次関数で近似することを考える．
  481.  
  482. \begin{lem}\label{lem:phi_c}
  483. $\psi(x)=ax^3+bx^2+cx+d$, $a\not=0$, $c<0$とする．
  484. \begin{enumerate}
  485. \item このとき，
  486. \[ \gamma=\frac{-b+\sqrt{b^2-3ac}}{3a} \]
  487. は$\psi(x)$の極小点である．ただし，$b^2-3ac>0$とする．
  488. \item $a>0$または$b\ge0$ならば，$\gamma>0$である．
  489. \end{enumerate}
  490. \end{lem}
  491. \begin{proof}
  492. 1.を示す．
  493. \[ \psi'(x)=3ax^2+2bx+c,\quad \psi''(x)=6ax+2b \]
  494. であり，$\phi'(x)=0$を満たす$x$は，
  495. \[ x=\frac{-b\pm\sqrt{b^2-3ac}}{3a} \]
  496. で与えられる．
  497.  
  498. まず，$a>0$の場合，$b^2-3ac\not=0$なので，
  499. \[ \frac{-b-\sqrt{b^2-3ac}}{3a}<\frac{-b+\sqrt{b^2-3ac}}{3a} \]
  500. である．また，$x>-b/(3a)$のとき$\psi''(x)>0$つまり凸となるので，$\gamma=(-b+\sqrt{b^2-3ac})/(3a)$ ($>-b/(3a)$) は極小点である．
  501.  
  502. 次に，$a<0$の場合，$b^2-3ac>0$なので，
  503. \[ \frac{-b+\sqrt{b^2-3ac}}{3a}<\frac{-b-\sqrt{b^2-3ac}}{3a} \]
  504. である．
  505. また，$x<-b/(3a)$のとき$\psi''(x)>0$つまり凸となるので，$\gamma=(-b+\sqrt{b^2-3ac})/(3a)$ ($<-b/(3a)$) は極小点である．
  506. 以上より，1.が示された．
  507.  
  508. 2.を示す．
  509. $a>0$のとき，$b^2-3ac>b^2$より，$b$の符号に関わらず$-b+\sqrt{b^2-3ac}>0$である．
  510. よって，$\gamma>0$である．
  511. 次に，$a<0$のとき仮定より$b\ge0$であり，$b^2-3ac<b^2$より$-b+\sqrt{b^2-3ac}<0$である．
  512. よって，$\gamma=(-b+\sqrt{b^2-3ac})/(3a)>0$である．
  513. 以上より2.が示された．
  514. \end{proof}
  515.  
  516. \begin{prop}\label{prop:alpha_1}
  517. 正の実数$\alpha_0$が\eqref{eq:not_wolfe1}を満たし，\eqref{eq:alpha_1}で定まる$\alpha_1$が，
  518. \begin{align*}
  519. \phi(\alpha_1)>\phi(0)+c_1\alpha_1\phi'(0)
  520. \end{align*}
  521. を満たすと仮定する．
  522. $\phi_c$を，
  523. \[ \phi_c(0)=\phi(0),\quad \phi_c'(0)=\phi'(0),\quad \phi_c(\alpha_0)=\phi(\alpha_0),\quad \phi_c(\alpha_1)=\phi(\alpha_1) \]
  524. を満たす3次関数とする．
  525. このとき，以下の性質が成り立つ．
  526. \begin{enumerate}
  527. \item $\phi_c$は，
  528. \begin{align*}
  529. &\phi_c(\alpha)=a\alpha^3+b\alpha^2+\phi'(0)\alpha+\phi(0),\\
  530. &\begin{pmatrix}a\\b\end{pmatrix}=\frac{1}{\alpha_0^2\alpha_1^2(\alpha_1-\alpha_0)}\begin{pmatrix}\alpha_0^2&-\alpha_1^2\\-\alpha_0^3&\alpha_1^3\end{pmatrix}\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix}
  531. \end{align*}
  532. と表される．
  533. \item $b^2-3a\phi'(0)>0$を満たすとき，$\phi_c$は極値をもち，
  534. \begin{align}
  535. \alpha_2=\frac{-b+\sqrt{b^2-3a\phi'(0)}}{3a}\label{eq:alpha_2}
  536. \end{align}
  537. は$\phi_c$の極小点となる．
  538. \item $a>0$または$b\ge 0$が成り立つ．特に$c_1\le 1/2$ならば，$a<0$かつ$b\ge 0$である．
  539. \item $\phi_c'(\alpha_1)>0$ならば$0<\alpha_2<\alpha_1$である．
  540. \item $\phi(0)<\phi(\alpha_1)$ならば$0<\alpha_2<\alpha_1$である．
  541. \item $c_1\le1/2$かつ$\phi_c'(\alpha_1)<0$ならば，$-b/(3a)<\alpha_1$であることと$0<\alpha_2<\alpha_1$は同値である．
  542. \end{enumerate}
  543. \end{prop}
  544. \begin{proof}
  545. 1.を示す．
  546. まず，初め2つの条件から
  547. \[ \phi_c(\alpha)=a\alpha^3+b\alpha^2+\phi'(0)\alpha+\phi(0) \]
  548. と表せるが，残り2つの条件より，
  549. \[ \begin{pmatrix}\alpha_1^3&\alpha_1^2\\\alpha_0^3&\alpha_0^2\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi_c(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix} \]
  550. であるが，$\alpha_0\not=\alpha_1$より，
  551. \begin{align*}
  552. \begin{pmatrix}a\\b\end{pmatrix}&=\begin{pmatrix}\alpha_1^3&\alpha_1^2\\\alpha_0^3&\alpha_0^2\end{pmatrix}^{-1}\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix}\\
  553. &=\frac{1}{\alpha_0^2\alpha_1^2(\alpha_1-\alpha_0)}\begin{pmatrix}\alpha_0^2&-\alpha_1^2\\-\alpha_0^3&\alpha_1^3\end{pmatrix}\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix}
  554. \end{align*}
  555. である．
  556. 次に2.を示す．
  557. 補題\ref{lem:phi_c}.1より$c=\phi'(0)$を代入すればよい．
  558.  
  559. 3.を示す．
  560. 仮定より$\phi_c(\alpha_0)=\phi_q(\alpha_0)$なので，$a\alpha_0+b=(\phi(\alpha_0)-\phi(0)-\alpha_0\phi'(0))/(\alpha_0^2)>0$であり，$\alpha_0>0$より$a>0$または$b\ge0$である．
  561. ここで，$c_1\le1/2$かつ$a>0$と仮定して矛盾を導く．
  562. 補題\ref{prop:phi_q}.4より，$c_1\ge1/2$ならば$\alpha_1<\alpha_0$と$a\alpha_0+b>0$より，$(a\alpha_1+b)/(a\alpha_0+b)<1$である．
  563. $\alpha_1>0$と$\alpha_1$は十分な降下条件を満たさないことを使うと，
  564. \begin{align*}
  565. \frac{1}{2}&\ge c_1\\
  566. &>\frac{\phi_c(\alpha_1)-\phi_c(0)}{\phi'(0)\alpha_1}\\
  567. &=\frac{a\alpha_1^3+b\alpha_1^2+\phi'(0)\alpha_1+\phi(0)-\phi(0)}{\phi'(0)\alpha_1}\\
  568. &=\frac{a\alpha_1^2+b\alpha_1+\phi'(0)}{\phi'(0)}\\
  569. &=\frac{\alpha_1(a\alpha_1+b)+\phi'(0)}{\phi'(0)}\\
  570. &=\frac{-\phi'(0)(a\alpha_1+b)/(2(a\alpha_0+b))+\phi'(0)}{\phi'(0)}\\
  571. &=-\frac{1}{2}\frac{a\alpha_1+b}{a\alpha_0+b}+1\\
  572. &>-\frac{1}{2}\cdot1+1\\
  573. &=\frac{1}{2}
  574. \end{align*}
  575. により矛盾．
  576. よって，$c_1\le1/2$ならば$a<0$である．
  577.  
  578. 4.を示す．
  579. $\phi_c$は連続的微分可能なので$\phi_c'$は連続である．
  580. $\phi_c'(0)<0$, $\phi_c'(\alpha_1)>0$より中間値の定理から，$0<\alpha_2<\alpha_1$かつ$\phi_c'(\alpha_2)=0$を満たす$\alpha_2$が存在する．
  581.  
  582. 5.を示す．
  583. $\phi_c'(\alpha_2)=0$を満たす$0<\alpha_2<\alpha_1$が存在しないと仮定する．
  584. $\phi_c'$の連続性から，$0<\alpha<\alpha_1$ならば$\phi_c'(\alpha)<0$である．
  585. したがって，$\phi(0)=\phi_c(0)>\phi_c(\alpha_1)=\phi(\alpha_1)$だが，これは$\phi(0)<\phi(\alpha_1)$に反する．
  586.  
  587. 6.を示す．
  588. まず3.より$c_1\le1/2$より$a<0$, $b\ge0$である．
  589. このとき，補題\ref{lem:phi_c}.2より$\alpha_2>0$であり，$\alpha_2<-b/(3a)$なので，$-b/(3a)<\alpha_1$であることと$0<\alpha_2<\alpha_1$であることは同値である．
  590. \end{proof}
  591.  
  592. 命題\ref{prop:alpha_1}より，いくつかの条件において$0<\alpha_2<\alpha_1$となることが期待されるが，必ずそれが満たされるとは限らない．
  593. 具体的には以下の場合が考えられる．
  594. \begin{description}
  595. \item[Case 1.] $0<c_1<1$が，特に$c_1\ge1/2$を満たすとき，以下の条件を同時に満たす場合，$\alpha_1<\alpha_2$となる可能性がある．
  596. \begin{enumerate}
  597. \item $a>0$
  598. \item $\phi_c'(\alpha_1)<0$
  599. \item $\phi_c(0)+c_1\alpha_1\phi'(0)<\phi_c(\alpha_1)<\phi_c(0)$
  600. \end{enumerate}
  601. \item[Case 2.] $0<c_1<1$が，特に$c_1<1/2$を満たすとき，以下の条件を同時に満たす場合，必ず$\alpha_1<\alpha_2$となる．
  602. \begin{enumerate}
  603. \item $\phi_c'(\alpha_1)<0$
  604. \item $\phi_c(0)+c_1\alpha_1\phi'(0)<\phi_c(\alpha_1)<\phi_c(0)$
  605. \item $-b/(3a)<\alpha_1$
  606. \end{enumerate}
  607. \end{description}
  608. また，$a<0$のとき$b^2-3a\phi'(0)>0$でなければ，そもそも$\phi_c$は極値をもたない．
  609.  
  610. 以下の命題で，上記に対応する例を与える．
  611. 以下の命題の1.および2.と3.が上記のCase 1.およびCase 2.に対応する．
  612.  
  613. \begin{prop}
  614. \begin{enumerate}
  615. \item $\phi(0)=1$, $\phi'(0)=-1$, $\phi(1)=5$, $\phi(1/10)=923/1000$を満たす関数$\phi$は，$c_1=4/5$, $\alpha_0=1$とすると，$\alpha_0$, $\alpha_1$は十分な降下条件を満たさず，$\alpha_1<\alpha_2$である．
  616. \item $63/144<c_1<1$に対して，
  617. \[ \max\{0,1-3c_1\}<\epsilon<\min\left\{\frac{-(7-16c_1)+\sqrt{144c_1-63}}{8(1-c_1)},\frac{1}{4}\right\} \]
  618. ととると，
  619. \[ \phi(0)=1,\quad\phi'(0)=-1,\quad\phi(1)=\frac{2+\epsilon}{3}, \quad\phi\left(\frac{3}{2(2+\epsilon)}\right)=\frac{8\epsilon^3+36\epsilon^2+75\epsilon+43}{8(2+\epsilon)^3} \]
  620. を満たす関数$\phi$は，$\alpha_0=1$とすると，$\alpha_0$, $\alpha_1$は十分な降下条件を満たさず，$\alpha_1<\alpha_2$である．
  621.  
  622. \item $c_1=1/2$とすると，$\phi(0)=1$, $\phi'(0)=-1$, $\phi(1)=203/300$, $\phi(300/402)=202563/300763$を満たす関数$\phi$は，$\alpha_0=1$とすると，$\alpha_0$, $\alpha_1$は十分な降下条件を満たさず，$\alpha_1<\alpha_2$である．
  623. \end{enumerate}
  624. \end{prop}
  625. \begin{proof}
  626. 1.を示す．
  627. まず，$\phi(\alpha_0)=\phi(1)=5$, $\phi(0)+c_1\alpha_0\phi'(0)=1+(4/5)\cdot1\cdot(-1)=1/5$より，$\alpha_0$は十分な降下条件を満たさない．
  628. ここで，
  629. \begin{align*}
  630. \phi_q(\alpha)&=\left(\frac{\phi(\alpha_0)-\phi(0)-\alpha_0\phi'(0)}{\alpha_0^2}\right)\alpha^2+\phi'(0)\alpha+\phi(0)\\
  631. &=\frac{5-1-1\cdot(-1)}{1^2}\alpha^2-\alpha+1\\
  632. &=5\alpha^2-\alpha+1
  633. \end{align*}
  634. である．
  635. ここで，
  636. \[ \alpha_1=\frac{1}{10} \]
  637. であるが，
  638. \[ \phi(\alpha_1)=\phi\left(\frac{1}{10}\right)=\frac{923}{1000},\quad \phi(0)+c_1\alpha_1\phi'(0)=1+\frac{4}{5}\cdot\frac{1}{10}\cdot(-1)=\frac{920}{1000} \]
  639. なので，$\alpha_1$は十分な降下条件を満たさない．
  640. 最後に，
  641. \begin{align*}
  642. \begin{pmatrix}a\\b\end{pmatrix}&=\frac{1}{\alpha_0^2\alpha_1^2(\alpha_1-\alpha_0)}\begin{pmatrix}\alpha_0^2&-\alpha_1^2\\-\alpha_0^3&\alpha_1^3\end{pmatrix}\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix}\\
  643. &=\frac{1}{1^2(1/10)^2(1/10-1)}\begin{pmatrix}1^2&-(1/10)^2\\-1^3&(1/10)^3\end{pmatrix}\begin{pmatrix}923/1000-(1/10)\cdot(-1)-1\\5-1\cdot(-1)-1\end{pmatrix}\\
  644. &=-\frac{1000}{9}\begin{pmatrix}1&-1/100\\-1&1/1000\end{pmatrix}\begin{pmatrix}23/1000\\5\end{pmatrix}\\
  645. &=-\frac{1000}{9}\begin{pmatrix}23/1000-(1/100)\cdot5\\-23/1000+(1/1000)\cdot5\end{pmatrix}\\
  646. &=-\frac{1000}{9}\begin{pmatrix}-27/1000\\-18/1000\end{pmatrix}\\
  647. &=\begin{pmatrix}3\\2\end{pmatrix}
  648. \end{align*}
  649. より，$\phi_c(\alpha)=3\alpha^3+2\alpha^2-\alpha+1$である．
  650. ここで，
  651. \[ \alpha_2=\frac{-b+\sqrt{b^2-3a\phi'(0)}}{3a}=\frac{-2+\sqrt{2^2-3\cdot 3\cdot(-1)}}{3\cdot3}=\frac{-2+\sqrt{11}}{9}>\frac{1}{9}>\frac{1}{10}=\alpha_1 \]
  652. となり，1.が示された．
  653.  
  654. 次に2.の場合を示す．
  655. まず，$\phi(\alpha_0)=\phi(1)=(2+\epsilon)/3$である．
  656. $\phi(0)+c_1\alpha_0\phi'(0)=1+c_1\cdot1\cdot(-1)=1-c_1$であるが，
  657. \[ \phi(\alpha_0)-\phi(0)-c_1\alpha_0\phi'(0)=\frac{2+\epsilon}{3}-(1-c_1)=\frac{\epsilon-(1-3c_1)}{3}>0 \]
  658. より，$\alpha_0$は十分な降下条件を満たさない．
  659. ここで，
  660. \begin{align*}
  661. \phi_q(\alpha)&=\left(\frac{\phi(\alpha_0)-\phi(0)-\alpha_0\phi'(0)}{\alpha_0^2}\right)\alpha^2+\phi'(0)\alpha+\phi(0)\\
  662. &=\frac{(2+\epsilon)/3-1-1\cdot(-1)}{1^2}\alpha^2-\alpha+1\\
  663. &=\frac{2+\epsilon}{3}\alpha^2-\alpha+1
  664. \end{align*}
  665. であるが，ここで，
  666. \[ \alpha_1=\frac{3}{2(2+\epsilon)} \]
  667. であるが，
  668. \[ \phi(\alpha_1)=\phi\left(\frac{3}{2(2+\epsilon)}\right)=\frac{8\epsilon^3+36\epsilon^2+75\epsilon+43}{8(2+\epsilon)^3},\quad \phi(0)+c_1\alpha_1\phi'(0)=1+c_1\cdot\frac{3}{2(2+\epsilon)}\cdot(-1) \]
  669. である．
  670. いま，
  671. \begin{align*}
  672. \phi(\alpha_1)-\phi(0)-c_1\alpha_1\phi'(0)&=\frac{8\epsilon^3+36\epsilon^2+75\epsilon+43}{8(2+\epsilon)^3}-\left(1+c_1\cdot\frac{3}{2(2+\epsilon)}\cdot(-1)\right)\\
  673. &=\frac{8\epsilon^3+36\epsilon^2+75\epsilon+43}{8(2+\epsilon)^3}-1+c_1\cdot\frac{3}{2(2+\epsilon)}\\
  674. &=\frac{-3(4\epsilon^2+7\epsilon+7)}{8(2+\epsilon)^3}+c_1\cdot\frac{3}{2(2+\epsilon)}\\
  675. &=\frac{3}{2(2+\epsilon)}\left(c_1-\frac{4\epsilon^2+7\epsilon+7}{4(2+\epsilon)^2}\right)
  676. \end{align*}
  677. であるが，
  678. \[ \epsilon<\frac{-(7-16c_1)+\sqrt{144c_1-63}}{8(1-c_1)} \]
  679. より，
  680. \[ 4(1-c_1)\epsilon^2+(7-16c_1)\epsilon+(7-16c_1)<0 \]
  681. つまり，$4(2+\epsilon)^2c_1-(4\epsilon^2+7\epsilon+7)>0$が成り立つ．
  682. つまり，$\alpha_1$は十分な降下条件を満たさない．
  683. また，$c_1>63/144$であることを使った．
  684.  
  685. ここで，
  686. \begin{align*}
  687. \begin{pmatrix}a\\b\end{pmatrix}&=\frac{1}{\alpha_0^2\alpha_1^2(\alpha_1-\alpha_0)}\begin{pmatrix}\alpha_0^2&-\alpha_1^2\\-\alpha_0^3&\alpha_1^3\end{pmatrix}\begin{pmatrix}\phi(\alpha_1)-\alpha_1\phi'(0)-\phi(0)\\\phi(\alpha_0)-\alpha_0\phi'(0)-\phi(0)\end{pmatrix}\\
  688. &=-\frac{8(2+\epsilon)^3}{9(2\epsilon+1)}\begin{pmatrix}1^2&-(3/(2(2+\epsilon)))^2\\-1^3&(3/(2(2+\epsilon)))^3\end{pmatrix}\begin{pmatrix}27(1+\epsilon)/(8(2+\epsilon)^3)\\(2+\epsilon)/3\end{pmatrix}\\
  689. &=-\frac{8(2+\epsilon)^3}{9(2\epsilon+1)}\begin{pmatrix}3(1-\epsilon)(2\epsilon+1)/(8(2+\epsilon)^3)\\-9(2\epsilon+1)/(8(2+\epsilon)^3)\end{pmatrix}\\
  690. &=\begin{pmatrix}-(1-\epsilon)/3\\1\end{pmatrix}
  691. \end{align*}
  692. なので，
  693. \[ \phi_c(\alpha)=-\frac{1-\epsilon}{3}\alpha^3+\alpha^2-\alpha+1 \]
  694. であり，
  695. \[ \alpha_2=\frac{-b+\sqrt{b^2-3a\phi'(0)}}{3a}=\frac{1}{1+\sqrt{\epsilon}} \]
  696. である．
  697. $\epsilon<1/4$より，$(4\epsilon-1)(\epsilon-1)=4\epsilon^2-5\epsilon+1>0$である．
  698. すなわち，$(4\epsilon^2+4\epsilon+1)/9>\epsilon$であり，両辺の平方根をとると$(1+2\epsilon)/3>\sqrt{\epsilon}$が成り立つ．
  699. 結局$1/(1+\sqrt{\epsilon})>3/(2(2+\epsilon))$であり，
  700. \[ \alpha_2-\alpha_1=\frac{1}{1+\sqrt{\epsilon}}-\frac{3}{2(2+\epsilon)}>0 \]
  701. となる．
  702. したがって，$\alpha_2>\alpha_1$が成り立つ．
  703.  
  704. 3.は，2.において$c_1=1/2$とすると，
  705. \[ \max\left\{0,-\frac{1}{2}\right\}<\frac{1}{100}<\min\left\{1,\frac{1}{4}\right\} \]
  706. であるため，2.において$\epsilon=1/100$とおくと成り立つ．
  707. \end{proof}
  708.  
  709. 最後に，$\alpha_i$, $\alpha_{i-1}$から新しいステップ幅の候補$\alpha_{i+1}$を求める，補間多項式を用いるもうひとつの方法について述べる．
  710.  
  711. \begin{lem}
  712. $\alpha_i\not=\alpha_{i-1}$とする．
  713. 3次多項式$\psi(\alpha)$が
  714. \[ \psi(\alpha_i)=\phi(\alpha_i),\quad\psi'(\alpha_i)=\phi'(\alpha_i),\quad\psi(\alpha_{i-1})=\phi(\alpha_{i-1}),\quad\psi'(\alpha_{i-1})=\phi'(\alpha_{i-1}) \]
  715. を満たすとする．
  716. このとき，$\psi$は一意に定まり，$\psi$の極小点$\alpha_{i+1}$は，
  717. \begin{align}
  718. \alpha_{i+1}=\alpha_i-(\alpha_i-\alpha_{i-1})\left(\frac{\phi'(\alpha_i)+d_2-d_1}{\phi'(\alpha_i)-\phi'(\alpha_{i-1})+2d_2}\right).\label{eq:3.43}
  719. \end{align}
  720. と表される．
  721. ただし，
  722. \begin{align*}
  723. &d_1=\phi'(\alpha_i)+\phi'(\alpha_{i-1})-3\frac{\phi(\alpha_i)-\phi(\alpha_{i-1})}{\alpha_i-\alpha_{i-1}},\\
  724. &d_2=\sqrt{d_1^2-\phi'(\alpha_i)\phi'(\alpha_{i-1})}
  725. \end{align*}
  726. とする．
  727. \end{lem}
  728. \begin{proof}
  729. Hermite補間によって，$\alpha_i\not=\alpha_{i-1}$ならば，$\psi$は
  730. \[ \psi(\alpha)=\phi[\alpha_i]+(\alpha-\alpha_i)\phi[\alpha_i,\alpha_i]+(\alpha-\alpha_i)^2\phi[\alpha_i,\alpha_i,\alpha_{i-1}]+(\alpha-\alpha_i)^2(\alpha-\alpha_{i-1})\phi[\alpha_i,\alpha_i,\alpha_{i-1},\alpha_{i-1}] \]
  731. と一意に求まることが知られている．
  732. ただし，
  733. \begin{align*}
  734. &\phi[\alpha_i]=\alpha_i,\\
  735. &\phi[\alpha_i,\alpha_i]=\frac{\phi'(\alpha_i)}{1!},\quad\phi[\alpha_i,\alpha_{i-1}]=\frac{\phi(\alpha_i)-\phi(\alpha_{i-1})}{\alpha_i-\alpha_{i-1}},\quad\phi[\alpha_{i-1},\alpha_{i-1}]=\frac{\phi'(\alpha_{i-1})}{1!}\\
  736. &\phi[\alpha_i,\alpha_i,\alpha_{i-1}]=\frac{\phi[\alpha_i,\alpha_i]-\phi[\alpha_i,\alpha_{i-1}]}{\alpha_i-\alpha_{i-1}},\quad\phi[\alpha_i,\alpha_{i-1},\alpha_{i-1}]=\frac{\phi[\alpha_i,\alpha_{i-1}]-\phi[\alpha_{i-1},\alpha_{i-1}]}{\alpha_i-\alpha_{i-1}},\\
  737. &\phi[\alpha_i,\alpha_i,\alpha_{i-1},\alpha_{i-1}]=\frac{\phi[\alpha_i,\alpha_i,\alpha_{i-1}]-\phi[\alpha_i,\alpha_{i-1},\alpha_{i-1}]}{\alpha_i-\alpha_{i-1}}
  738. \end{align*}
  739. とする．
  740.  
  741. これを整理すると，$\psi(\alpha)=a\alpha^3+b\alpha^2+c\alpha+d$において，
  742. \begin{align*}
  743. &a=\frac{\gamma}{(\Delta\alpha_i)^2},\\
  744. &b=\frac{\beta}{\Delta\alpha_i}-\frac{3\alpha_i-\Delta\alpha_i}{(\Delta\alpha_i)^2}\gamma,\\
  745. &c=\phi'(\alpha_i)-\frac{2\alpha_i}{\Delta\alpha_i}\beta+\frac{\alpha_i(3\alpha_{i-1}+\Delta\alpha_i)}{(\Delta\alpha_i)^2}\gamma
  746. \end{align*}
  747. となる．
  748. ただし，
  749. \begin{align*}
  750. &\beta=\phi'(\alpha_i)-\frac{\Delta\phi(\alpha_i)}{\Delta\alpha_i},\\
  751. &\gamma=\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2\frac{\Delta\phi(\alpha_i)}{\Delta\alpha_i},\\
  752. &\Delta\alpha_i=\alpha_i-\alpha_{i-1},\\
  753. &\Delta\phi(\alpha_i)=\phi(\alpha_i)-\phi(\alpha_{i-1})
  754. \end{align*}
  755. とする．
  756.  
  757. 補題\ref{lem:phi_c}により，$a$の正負によらず，
  758. \[ \alpha_{i+1}=\frac{-b+\sqrt{D}}{3a},\quad D=b^2-3ac \]
  759. と表されるが，これを整理すると，
  760. \[ \alpha_{i+1}=\alpha_i-\Delta\alpha_i\frac{\beta+\gamma-\sqrt{D}}{3\gamma},\quad D=(\beta+\gamma)^2-3\gamma\phi'(\alpha_i) \]
  761. となる．
  762.  
  763. ここで，$d_1=\beta+\gamma-\phi'(\alpha_i)$, $d_2=\sqrt{D}$とおくと，
  764. \[ 3\gamma=2d_1+\phi'(\alpha_i)+\phi'(\alpha_{i-1}),\quad \beta+\gamma-\sqrt{D}=d_1-d_2+\phi'(\alpha_i) \]
  765. が成り立つ．
  766.  
  767. これらをまとめると，
  768. \begin{align}
  769. &\alpha_{i+1}=\alpha_i-(\alpha_i-\alpha_{i-1})\frac{d_1-d_2+\phi'(\alpha_i)}{2d_1+\phi'(\alpha_i)+\phi'(\alpha_{i-1})},\label{eq:3.43_0}\\
  770. &d_1=\phi'(\alpha_i)+\phi'(\alpha_{i-1})-3\frac{\phi(\alpha_i)-\phi(\alpha_{i-1})}{\alpha_i-\alpha_{i-1}},\notag\\
  771. &d_2=\sqrt{d_1^2-\phi'(\alpha_i)\phi'(\alpha_{i-1})}\notag
  772. \end{align}
  773. となる．
  774.  
  775. 最後に，\eqref{eq:3.43_0}と\eqref{eq:3.43}は等価で有ることを示す．
  776. \eqref{eq:3.43}の一番右の括弧内の分母を$(\phi'(\alpha_i)-\phi'(\alpha_{i-1})-2d_2)$倍すると，
  777. \begin{align*}
  778. &(\phi'(\alpha_i)-\phi'(\alpha_{i-1})+2d_2)(\phi'(\alpha_i)-\phi'(\alpha_{i-1})-2d_2)\\
  779. &\quad=(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))^2-(2d_2)^2\\
  780. &\quad=\phi'(\alpha_i)^2-2\phi'(\alpha_i)\phi'(\alpha_{i-1})+\phi'(\alpha_{i-1})^2-4(d_1^2-\phi'(\alpha_{i-1})\phi'(\alpha_i))\\
  781. &\quad=\phi'(\alpha_i)^2+2\phi'(\alpha_i)\phi'(\alpha_{i-1})+\phi'(\alpha_{i-1})^2-4d_1^2\\
  782. &\quad=(\phi'(\alpha_i)+\phi'(\alpha_{i-1})+2d_1)(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)
  783. \end{align*}
  784. であり，
  785. \eqref{eq:3.43}の一番右の括弧内の分子を$(\phi'(\alpha_i)-\phi'(\alpha_{i-1})-2d_2)$倍すると，
  786. \begin{align*}
  787. &(\phi'(\alpha_i)+d_2-d_1)(\phi'(\alpha_i)-\phi'(\alpha_{i-1})-2d_2)\\
  788. &\quad=(\phi'(\alpha_i)-d_1)(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))-(2(\phi'(\alpha_i)-d_1)-(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))d_2-2d_2^2\\
  789. &\quad=(\phi'(\alpha_i)-d_1)(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))-(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)d_2-2d_2^2\\
  790. &\quad=\phi'(\alpha_i)^2-\phi'(\alpha_i)\phi'(\alpha_{i-1})-d_1(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))-(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)d_2-2(d_1^2-\phi'(\alpha_i)\phi'(\alpha_{i-1})\\
  791. &\quad=\phi'(\alpha_i)^2+\phi'(\alpha_i)\phi'(\alpha_{i-1})-d_1(\phi'(\alpha_i)-\phi'(\alpha_{i-1}))-2d_1^2-(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)d_2\\
  792. &\quad=(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)(\phi'(\alpha_i)+d_1)-(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)d_2\\
  793. &\quad=(\phi'(\alpha_i)+\phi'(\alpha_{i-1})-2d_1)(\phi'(\alpha_i)-d_2+d_1)
  794. \end{align*}
  795. となる．
  796. よって，\eqref{eq:3.43_0}と\eqref{eq:3.43}は等価であり，補題が示された．
  797. \end{proof}
  798.  
  799. 以上より，補間法による十分な降下条件を満たすステップ幅の求め方は以下の手順となる．
  800. まず，ステップ幅の初期値$\alpha_0$をとる．
  801. この$\alpha_0$が十分な降下条件を満たせば探索は終了する．
  802. そうでない場合，\eqref{eq:alpha_1}によって$\alpha_1$を求める．
  803. この$\alpha_1$が十分な降下条件を満たせば探索は終了する．
  804. そうでない場合，十分な降下条件を満たすまで，\eqref{eq:alpha_2}または\eqref{eq:3.43}によって$\alpha_{i-1},\alpha_i$から$\alpha_{i+1}$を求める操作を繰り返す．
  805. ただし，$\alpha_i$が$\alpha_{i-1}$と近すぎたり，$\alpha_{i-1}$より小さすぎたりした場合は，$\alpha_i=\alpha_{i-1}/2$によってリセットすることも効果的である．
  806.  
  807. \section{強いWolfe条件を満たすステップ幅の探索}
  808.  
  809. 本節では，強いWolfe条件を満たすステップ幅の探索方法について述べる．
  810. ただし，目的関数$f$は連続的微分可能であるとする．
  811.  
  812. \begin{lem}\label{lem:strong_wolfe_1}
  813. 第$k$反復におけるステップ幅の候補$\{\alpha_i\}$が$0<\alpha_i<\alpha_{\mathrm{max}}$かつ$\alpha_{i-1}<\alpha_i$を満たすとする．
  814. ただし，$\alpha_{\mathrm{max}}>0$とする．
  815. $j<i$ならば区間$(\alpha_{j-1},\alpha_j)$は強いWolfe条件を満たすステップ幅を含まないと仮定する．
  816. $\alpha_i$が以下の3つのうち少なくとも1つの条件を満たせば，$(\alpha_{i-1},\alpha_i)$は強いWolfe条件を満たすステップ幅を含む．
  817. \begin{enumerate}
  818. \item $\alpha_i$が十分な降下条件を満たさない
  819. \item $\phi(\alpha_i)\ge\phi(\alpha_{i-1})$
  820. \item $\phi'(\alpha_i)\ge0$
  821. \end{enumerate}
  822. \end{lem}
  823. \begin{proof}
  824. 以下を満たすと仮定して，補題が成り立つことを示す．
  825. \begin{enumerate}
  826. \item $j=1,2,\dots,i-1$について，$\alpha_j$は十分な降下条件を満たす
  827. \item $j=1,2,\dots,i-1$について，$\phi(\alpha_j)<\phi(\alpha_{j-1})$
  828. \item $j=1,2,\dots,i-1$について，$\phi'(\alpha_j)<0$
  829. \end{enumerate}
  830.  
  831. まず，$\alpha_i$が十分な降下条件を満たさないと仮定する．このとき，
  832. \begin{align*}
  833. &\phi(\alpha_{i-1})\le\phi(0)+\alpha_{i-1}c_1\phi'(0),\\
  834. &\phi(\alpha_i)>\phi(0)+\alpha_ic_1\phi'(0)
  835. \end{align*}
  836. が成り立つ．
  837. したがって，$\phi(\alpha')=\phi(0)+\alpha c_1\phi'(0)$を満たす$\alpha'$が区間$(\alpha_{i-1},\alpha_i)$に存在する．
  838. 仮定より$0<\alpha<\alpha_{i-1}$は強いWolfe条件を満たすステップ幅を含まないため，補題\ref{lem:wolfe_exists}より，
  839. $(\alpha_{i-1},\alpha')\subset(\alpha_{i-1},\alpha_i)$は強いWolfe条件を満たすステップ幅を含む．
  840.  
  841. 次に，$\phi(\alpha_i)\ge\phi(\alpha_{i-1})$と仮定する．
  842. $\phi'(\alpha_{i-1})<0$より$(\alpha_{i-1},\alpha_i)$において$\phi'(\alpha)<0$であれば$\phi(\alpha_i)<\phi(\alpha_{i-1})$となるため，
  843. $\phi'(\alpha)>0$を満たす$\alpha\in(\alpha_{i-1},\alpha_i)$が存在する．$\phi$は連続的微分可能なので，強いWolfe条件を満たす$\alpha$が区間$(\alpha_{i-1},\alpha_i)$が存在する．
  844.  
  845. 最後に，$\phi'(\alpha_i)\ge0$と仮定する．$\phi'(\alpha_{i-1})<0$より，同様の議論から強いWolfe条件を満たす$\alpha$が区間$(\alpha_{i-1},\alpha_i)$が存在する．
  846.  
  847. 以上より，補題の1--3のいずれの条件を満たせば，区間$(\alpha_{i-1},\alpha_i)$は強いWolfe条件を満たすステップ幅を含む．
  848. \end{proof}
  849.  
  850. 強いWolfe条件を満たすステップ幅を含む区間$(\alpha_{i-1},\alpha_i)$について，$\alpha_{\mathrm{lo}},\alpha_{\mathrm{hi}}\in\{\alpha_i,\alpha_{i-1}\}$を，次の条件を満たすようにとる．
  851. \begin{enumerate}[\bf 条件1]
  852. \item $\alpha_{\mathrm{lo}}, \alpha_{\mathrm{hi}}$を端点とする区間に強いWolfe条件を満たすステップ幅を含む．
  853. \item $\alpha_{\mathrm{lo}}$は，これまで生成された$\alpha$の点の中で最も小さい関数値を与える．
  854. \item $\alpha_{\mathrm{hi}}$は，$\phi'(\alpha_{\mathrm{lo}})(\alpha_{\mathrm{hi}}-\alpha_{\mathrm{lo}})<0$を満たす．
  855. \end{enumerate}
  856. 強いWolfe条件を満たすステップ幅を含む区間が見つかったら，この条件1--3を満たすように，$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$を更新することで，強いWolfe条件を満たすステップ幅を含む区間を絞り込む方法が考えられる．
  857. これら条件1--3は\textbf{zoom}関数と呼ばれるアルゴリズムで用いるため，本稿では\textbf{zoom}関数における条件と呼ぶこととする．
  858.  
  859. 強いWolfe条件を満たすステップ幅の探索方法としては，次の方法が考えられる．
  860. まず，ステップ幅の候補の初期値$\alpha_0=0$, $0<\alpha_1<\alpha_{\mathrm{max}}$をとり，区間$(\alpha_{i-1},\alpha_i)$が強いWolfe条件を満たすステップ幅を含む区間となるまで，$\alpha_0<\alpha_1<\alpha_2<\dots<\alpha_i$となるように$\alpha_j$ ($j=2,3,\dots,i$) をとる．
  861.  
  862. 次に，$\alpha_{i-1},\alpha_i$から$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$を定める．
  863. $\alpha_j\in(\min\{\alpha_{\mathrm{lo}},\alpha_{\mathrm{hi}}\},\max\{\alpha_{\mathrm{hi}},\alpha_{\mathrm{lo}}\})$をとり，
  864. \textbf{zoom}関数における条件を満たすように$\alpha_{\mathrm{lo}}$または$\alpha_{\mathrm{hi}}$のいずれかと置き換える操作を繰り返し，強いWolfe条件を満たすステップ幅が存在する区間を狭める．
  865. その操作の中で$\alpha_j$が強いWolfe条件を満たせば，それをその反復におけるステップ幅として採用する．
  866.  
  867. 以上をまとめると，強いWolfe条件を満たすステップ幅を求めるアルゴリズムは，アルゴリズム\ref{algo:line_search}, \ref{algo:zoom} とまとめられる．
  868. 特にアルゴリズム\ref{algo:zoom} を\textbf{zoom}関数と呼ぶ．
  869. 各アルゴリズムにおいて，ある区間から新しいステップ幅候補を選ぶ方法に，前節の多項式補間による方法が利用できる点に注意されたい．
  870.  
  871. なお，アルゴリズム\ref{algo:zoom} の第12行目は，\cite{Nocedal1}では$\phi'_j\cdot(\alpha_{\mathrm{hi}}-\alpha_{\mathrm{lo}})$となっているが，説明を自然にするため，括弧の中を$\alpha_{\mathrm{hi}}-\alpha_j$に置き換えた．
  872. $\alpha_j\in(\min\{\alpha_{\mathrm{lo}},\alpha_{\mathrm{hi}}\},\max\{\alpha_{\mathrm{hi}},\alpha_{\mathrm{lo}}\})$なので，$\phi'_j\cdot(\alpha_{\mathrm{hi}}-\alpha_{\mathrm{lo}})\ge0$と$\phi'_j\cdot(\alpha_{\mathrm{hi}}-\alpha_j)\ge0$は同値であり，どちらでも同じ処理となる．
  873.  
  874. \begin{algorithm}[!t]
  875. \caption{強いWolfe条件を満たすステップ幅を求める直線探索アルゴリズム．}
  876. \label{algo:line_search}
  877. \begin{algorithmic}[1]
  878. \STATE $\alpha_0:=0$, choose $\alpha_1>0$ and $\alpha_{\mathrm{max}}$
  879. \STATE $\phi_0:=\phi(0)$, $\phi'_0:=\phi'(0)$
  880. \STATE $i:=1$
  881. \LOOP
  882. \STATE $\phi_i:=\phi(\alpha_i)$
  883. \IF{$\phi_i>\phi_0+c_1\alpha_i\phi'_0$ or ($\phi_i\ge\phi_{i-1}$ and $i>1$)}
  884. \RETURN $\alpha_*:=\mathbf{zoom}(\alpha_{i-1},\alpha_i)$
  885. \ENDIF
  886. \STATE $\phi'_i:=\phi'(\alpha_i)$
  887. \IF{$|\phi'_i|\le-c_2\phi'_0$}
  888. \RETURN $\alpha_*:=\alpha_i$
  889. \ENDIF
  890. \IF{$\phi'_i\ge0$}
  891. \RETURN $\alpha_*:=\mathbf{zoom}(\alpha_i,\alpha_{i-1})$
  892. \ENDIF
  893. \STATE Choose $\alpha_{i+1}\in(\alpha_i,\alpha_{\mathrm{max}})$
  894. \STATE $i:=i+1$
  895. \ENDLOOP
  896. \end{algorithmic}
  897. \end{algorithm}
  898.  
  899. \begin{algorithm}[!t]
  900. \caption{zoom関数．引数は$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$の順に与えられるとする．}
  901. \label{algo:zoom}
  902. \begin{algorithmic}[1]
  903. \STATE $\phi_0:=\phi(0)$, $\phi'_0:=\phi'(0)$
  904. \LOOP
  905. \STATE Choose $\alpha_j\in(\min\{\alpha_{\mathrm{lo}},\alpha_{\mathrm{hi}}\},\max\{\alpha_{\mathrm{lo}},\alpha_{\mathrm{hi}}\})$
  906. \STATE $\phi_j:=\phi(\alpha_j)$
  907. \IF{$\phi_j>\phi_0+c_1\alpha_j\phi'_0$ or $\phi_j\ge\phi(\alpha_{\mathrm{lo}})$}
  908. \STATE $\alpha_{\mathrm{hi}}:=\alpha_j$
  909. \ELSE
  910. \STATE $\phi'_i:=\phi'(\alpha_i)$
  911. \IF{$|\phi'_j|\le-c_2\phi'_0$}
  912. \RETURN $\alpha_*:=\alpha_j$
  913. \ENDIF
  914. \IF{$\phi'_j\cdot(\alpha_{\mathrm{hi}}-\alpha_j)\ge0$}
  915. \STATE $\alpha_{\mathrm{hi}}:=\alpha_{\mathrm{lo}}$
  916. \ENDIF
  917. \STATE $\alpha_{\mathrm{lo}}:=\alpha_j$
  918. \ENDIF
  919. \ENDLOOP
  920. \end{algorithmic}
  921. \end{algorithm}
  922.  
  923. 以下の5.1, 5.2節で，アルゴリズム\ref{algo:line_search}, \ref{algo:zoom} の手続きが妥当であることを確認する．
  924.  
  925. \subsection{アルゴリズム\ref{algo:line_search} についての補足}
  926. 本節では，アルゴリズム\ref{algo:line_search} の手続きが妥当であることを確認する．
  927.  
  928. アルゴリズム\ref{algo:line_search} は，補題\ref{lem:strong_wolfe_1}にしたがい，強いWolfe条件を満たす区間$(\alpha_{i-1},\alpha_i)$が見つかるまで$\alpha_1<\alpha_2<\dots$と$\alpha_k$を更新する．
  929. 第6, 13行目の条件式は，補題\ref{lem:strong_wolfe_1}により，区間$(\alpha_{i-1},\alpha_i)$が強いWolfe条件を満たすステップ幅を含む条件を表す．
  930. また，第10行目の条件式は，強いWolfe条件を表す．
  931. 第16行目で区間$(\alpha_i,\alpha_{\mathrm{max}})$から$\alpha_{i+1}$を選ぶことで，$\{\alpha_i\}$が単調増加列で，$\alpha_{\mathrm{max}}$より小さい値をとることが保証できる．
  932.  
  933. 第7, 14行目において，\textbf{zoom}関数を呼ぶときに渡す引数が適切であることを確認する．
  934.  
  935. \paragraph{第7行目}
  936. 補題\ref{lem:strong_wolfe_1}より$(\alpha_{i-1},\alpha_i)$は強いWolfe条件を満たすステップ幅を含む区間であり，
  937. $\phi(\alpha_0)>\phi(\alpha_1)>\dots>\phi(\alpha_{i-1})$であり，$\phi'(\alpha_{i-1})<0$であることから，$\phi'(\alpha_{i-1})(\alpha_i-\alpha_{i-1})<0$となるため，
  938. $\alpha_{\mathrm{lo}}=\alpha_{i-1}$, $\alpha_{\mathrm{hi}}=\alpha_i$として\textbf{zoom}関数を呼ぶことができる．
  939.  
  940. \paragraph{第14行目}
  941. 補題\ref{lem:strong_wolfe_1}より$(\alpha_{i-1},\alpha_i)$は強いWolfe条件を満たすステップ幅を含む区間であり，
  942. 第6行目の条件文より$\phi(\alpha_i)<\phi(\alpha_{i-1})$であり，第13行名の条件文より$\phi'(\alpha_i)(\alpha_{i-1}-\alpha_i)<0$となるため，
  943. $\alpha_{\mathrm{lo}}=\alpha_i$, $\alpha_{\mathrm{hi}}=\alpha_{i-1}$として\textbf{zoom}関数を呼ぶことができる．
  944.  
  945. 以上より，アルゴリズム\ref{algo:line_search} において設定される\textbf{zoom}関数の引数$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$は適切であり，アルゴリズム\ref{algo:line_search} の手続きは妥当であることが確認された．
  946.  
  947. \subsection{アルゴリズム\ref{algo:zoom} についての補足}
  948.  
  949. 本節では，アルゴリズム\ref{algo:zoom} の手続きが妥当であることを確認する．
  950.  
  951. アルゴリズム\ref{algo:zoom} では，既に述べたとおり，
  952. $\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$が\textbf{zoom}関数における条件1--3を満たすよう，
  953. $\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$を更新する．
  954. ただし，選んだ$\alpha_j$が強いWolfe条件を満たせば，それを返して反復を終了する．
  955. よって，第6, 13, 15行目における更新が\textbf{zoom}関数にける条件1--3を満たすことを確認すればよい．
  956.  
  957. \paragraph{第6行目}
  958. まず，$\alpha_{\mathrm{lo}}<\alpha_{\mathrm{hi}}$とする．
  959. $\alpha_j>\alpha_{\mathrm{lo}}$かつ$\phi'(\alpha_{\mathrm{lo}})<0$より，$\phi'(\alpha_{\mathrm{lo}})(\alpha_j-\alpha_{\mathrm{lo}})<0$が成り立つ．
  960. また補題\ref{lem:strong_wolfe_1}より$(\alpha_{\mathrm{lo}},\alpha_j)$は強いWolfe条件を満たすステップ幅を含む．
  961. したがって，$\alpha_{\mathrm{hi}}:=\alpha_j$としても，$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$に関する条件は満たされる．
  962. 次に，$\alpha_{\mathrm{lo}}>\alpha_{\mathrm{hi}}$とする．
  963. $\alpha_j<\alpha_{\mathrm{lo}}$かつ$\phi'(\alpha_{\mathrm{lo}})>0$より，$\phi'(\alpha_{\mathrm{lo}})(\alpha_j-\alpha_{\mathrm{lo}})<0$が成り立つ．
  964. $\phi(\alpha_j)\ge\phi(\alpha_{\mathrm{lo}})$ならば，区間$(\alpha_j,\alpha_{\mathrm{lo}})$上$\phi'(\alpha)>0$と仮定すると矛盾するため，
  965. $\phi'(\alpha)\le0$となる$\alpha\in(\alpha_j,\alpha_{\mathrm{lo}})$が存在する．
  966. $\phi'$の連続性から区間$(\alpha_j,\alpha_{\mathrm{lo}})$は強いWolfe条件を満たすステップ幅を含む．
  967. $\phi(\alpha_j)>\phi(\alpha_0)+c_1\alpha_j\phi'(\alpha_0)$とする．
  968. アルゴリズム\ref{algo:line_search} の第7, 14行目のいずれの場合でも，$\alpha_{\mathrm{lo}}$は十分な降下条件を含む．
  969. \textbf{zoom}関数内でも$\alpha_{\mathrm{lo}}$は$\alpha_j$が十分な降下条件を満たすときに$\alpha_{\mathrm{lo}}:=\alpha_j$と更新されるため，$\alpha_{\mathrm{lo}}$は常に十分な降下条件を満たす．
  970. ここで，$\alpha_j$が十分な降下条件を満たさない場合，区間$(\alpha_j,\alpha_{\mathrm{lo}})$において$\phi'(\alpha)>0$と仮定すると矛盾する場合，
  971. $\phi'(\alpha)<0$を満たす$\alpha\in(\alpha_j,\alpha_{\mathrm{lo}})$が存在する．
  972. 特に，強いWolfe条件を満たす$\alpha$が区間$(\alpha_j,\alpha_{\mathrm{lo}})$に存在する．
  973. 以上より，第6行目の更新で，$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$に関する条件は満たされる．
  974.  
  975. \paragraph{第12行目を満たす場合の第13, 15行目}
  976. $\alpha_{\mathrm{hi}}^{\mathrm{new}}:=\alpha_{\mathrm{lo}}$とし，第15行目より$\alpha_{\mathrm{lo}}^{\mathrm{new}}:=\alpha_j$とすると，$\alpha_{\mathrm{hi}}-\alpha_j$と$\alpha_{\mathrm{lo}}-\alpha_j$は符号が異なるので，
  977. \[ \phi'(\alpha_{\mathrm{lo}}^{\mathrm{new}})(\alpha_{\mathrm{hi}}^{\mathrm{new}}-\alpha_{\mathrm{lo}}^{\mathrm{new}})=\phi'(\alpha_j)(\alpha_{\mathrm{lo}}-\alpha_j)<0 \]
  978. が成り立つ．
  979. $\alpha_{\mathrm{lo}}<\alpha_{\mathrm{hi}}$のとき，第12行目の条件文を満たすならば$\phi'(\alpha_j)>0$であるが，第5行目の条件文より$\phi(\alpha_{\mathrm{lo}})>\phi(\alpha_j)$である．
  980. よって，区間$(\alpha_{\mathrm{lo}},\alpha_j)$に強いWolfe条件を満たすステップ幅を含む．
  981. $\alpha_{\mathrm{lo}}>\alpha_{\mathrm{hi}}$のとき，第12行目の条件文を満たすならば$\phi'(\alpha_j)<0$であるが，第5行目の条件文より$\phi(\alpha_j)<\phi(\alpha_{\mathrm{lo}})$である．
  982. よって，区間$(\alpha_j,\alpha_{\mathrm{lo}})$に強いWolfe条件を満たすステップ幅を含む．
  983.  
  984. \paragraph{第12行目を満たさない場合の第15行目}
  985. $\alpha_{\mathrm{hi}}^{\mathrm{new}}:=\alpha_{\mathrm{hi}}$なので，
  986. \[ \phi'(\alpha_{\mathrm{lo}}^{\mathrm{new}})(\alpha_{\mathrm{hi}}^{\mathrm{new}}-\alpha_{\mathrm{lo}}^{\mathrm{new}})=\phi'(\alpha_j)(\alpha_{\mathrm{hi}}-\alpha_j)<0 \]
  987. が保証される．
  988. また，第5行目の条件文より$\phi(\alpha_j)<\phi(\alpha_{\mathrm{lo}})$である．
  989. 上記と同様に，$\alpha_{\mathrm{lo}}<\alpha_{\mathrm{hi}}$のとき，$\phi'(\alpha_j)<0$となるため，区間$(\alpha_j,\alpha_{\mathrm{hi}})$は強いWolfe条件を満たすステップ幅を含む．
  990. $\alpha_{\mathrm{lo}}>\alpha_{\mathrm{hi}}$のとき，$\phi'(\alpha_j)>0$となるため，区間$(\alpha_{\mathrm{hi}},\alpha_j)$は強いWolfe条件を満たすステップ幅を含む．
  991. したがって，第12行目の更新でも，$\alpha_{\mathrm{lo}}$, $\alpha_{\mathrm{hi}}$に関する条件は満たされる．
  992.  
  993. 以上より，アルゴリズム\ref{algo:line_search}, \ref{algo:zoom} の妥当性が確認された．
  994.  
  995. \begin{thebibliography}{9}
  996. \bibitem{Nocedal1} J. Nocedal, S. J. Wright, Numerical Optimization, Springer, New York, 1999.
  997. \end{thebibliography}
  998.  
  999. \newpage
  1000. \appendix
  1001. \AppendixSection{Pythonによる実装例}
  1002.  
  1003. 本節では，本稿で述べたアルゴリズムのPython 3.5による実装例をソースコード\ref{lst:wolfe}に記載する．
  1004. 実装には\verb|numpy|モジュールが必要である．
  1005. \begin{lstlisting}[caption=wolfeモジュール, label=lst:wolfe]
  1006. """強いWolfe条件を満たすステップ幅を求める直線探索を含む
  1007. 最急降下法により目的関数の無制約最適化問題の最適解を求めるためのモジュール．
  1008.  
  1009. [1]を参考に実装した．
  1010.  
  1011. [1] J. Nocedal, S. J. Wright, Numerical Optimization, Springer, New York, 1999.
  1012. """
  1013. import numpy as np
  1014.  
  1015. def optimize(x0, f, df, c1=1.0e-4, c2=0.9, alpha_max=10.0,
  1016. k_max=100000, eps=1.0e-15):
  1017. """最急降下法による無制約最適化問題の最適解を返す．
  1018.  
  1019. Args:
  1020. x0: 初期点
  1021. f: 目的関数
  1022. df: 目的関数の導関数
  1023. c1: 0 < c1 < c2 < 1を満たす定数
  1024. c2: 0 < c1 < c2 < 1を満たす定数
  1025. alpha_max: 降下方向のノルムを1としたときのステップ幅 α の最大値
  1026. k_max: 最大反復回数
  1027. eps: 収束判定条件
  1028.  
  1029. Returns:
  1030. 指定された目的関数の無制約最適化問題の最適解
  1031. """
  1032. x = x0
  1033. f_k = f(x)
  1034. for k in range(k_max):
  1035. if np.linalg.norm(df(x)) < eps:
  1036. # 収束判定条件を満たしたとき，最適解を返す
  1037. return x
  1038.  
  1039. # 降下方向を最急降下方向にとる
  1040. p = -df(x)
  1041.  
  1042. # φ, φ'を定義
  1043. phi = lambda alpha, p=p: f(x + alpha*p)
  1044. dphi = lambda alpha, p=p: np.dot(df(x + alpha*p), p)
  1045.  
  1046. # 目的関数の関数値
  1047. f_k_1, f_k = f_k, f(x)
  1048.  
  1049. # ステップ幅の初期値の計算
  1050. alpha_1 = set_alpha_init(f_k, f_k_1, dphi(0)) if k > 0 else 1.0
  1051.  
  1052. # 勾配ベクトルの大きさが小さい場合でも適切なステップ幅が求まるよう
  1053. # ステップ幅の最大値を勾配ベクトルの大きさで割っておく
  1054. alpha_max_scaled = alpha_max / np.linalg.norm(p)
  1055.  
  1056. # 直線探索で強いWolfe条件を満たすステップ幅を求める
  1057. alpha = line_search(alpha_1, alpha_max_scaled, phi, dphi, c1, c2)
  1058.  
  1059. # 近似解の更新
  1060. x += alpha*p
  1061.  
  1062. raise Exception('Loop maximum exceeded.')
  1063.  
  1064.  
  1065. def line_search(alpha_1, alpha_max, phi, dphi, c1, c2, loop_max=100,
  1066. alpha_when_failure=1.0e-5):
  1067. """直線探索によって強いWolfe条件を満たすステップ幅を返す．
  1068.  
  1069. Args:
  1070. alpha_1: ステップ幅の候補の初期値
  1071. alpha_max: ステップ幅の最大値
  1072. phi: phi(α) = f(x_k + α_kp_k) となる関数
  1073. dphi: phiの導関数
  1074. c1: 0 < c1 < c2 < 1を満たす定数
  1075. c2: 0 < c1 < c2 < 1を満たす定数
  1076. loop_max: 最大反復回数
  1077. alpha_when_failure: 失敗したときに選ぶステップ幅
  1078.  
  1079. Returns:
  1080. 強いWolfe条件を満たすステップ幅
  1081. """
  1082. phi_0, dphi_0 = phi(0), dphi(0)
  1083.  
  1084. alpha_pre, alpha_i = 0.0, alpha_1
  1085. phi_i = phi_0
  1086.  
  1087. for i in range(1, loop_max+1):
  1088. # φの関数値
  1089. phi_pre, phi_i = phi_i, phi(alpha_i)
  1090.  
  1091. if phi_i > phi_0 + c1*alpha_i*dphi_0 or (i > 1 and phi_i >= phi_pre):
  1092. # 区間(alpha_pre, alpha_i)が強いWolfe条件を含む場合
  1093. alpha_lo, alpha_hi = alpha_pre, alpha_i
  1094. return zoom(alpha_lo, alpha_hi, phi, dphi, c1, c2,
  1095. alpha_when_failure=alpha_when_failure)
  1096.  
  1097. # φの導関数値
  1098. dphi_i = dphi(alpha_i)
  1099.  
  1100. if np.abs(dphi_i) <= -c2*dphi_0:
  1101. # 強いWolfe条件を満たす
  1102. return alpha_i
  1103.  
  1104. if dphi_i >= 0:
  1105. # 区間(alpha_pre, alpha_i)が強いWolfe条件を含む場合
  1106. alpha_lo, alpha_hi = alpha_i, alpha_pre
  1107. return zoom(alpha_lo, alpha_hi, phi, dphi, c1, c2,
  1108. alpha_when_failure=alpha_when_failure)
  1109.  
  1110. # (alpha_pre, alpha_i)は強いWolfe条件を含まないので，
  1111. # 区間(alpha_i, alpha_max)から新しいステップ幅の候補を選ぶ．
  1112. alpha_pre, alpha_i = alpha_i, choose_alpha(alpha_i, alpha_max, phi, dphi)
  1113.  
  1114. # 探索に失敗した場合
  1115. return alpha_when_failure
  1116.  
  1117.  
  1118. def zoom(alpha_lo, alpha_hi, phi, dphi, c1, c2, loop_max=100,
  1119. alpha_when_failure=1.0e-5):
  1120. """強いWolfe条件を満たすステップ幅を返す．
  1121.  
  1122. Args:
  1123. alpha_lo: 区間の端点
  1124. alpha_hi: 区間の端点
  1125. phi: phi(α) = f(x_k + α_kp_k) となる関数
  1126. dphi: phiの導関数
  1127. c1: 0 < c1 < c2 < 1を満たす定数
  1128. c2: 0 < c1 < c2 < 1を満たす定数
  1129. loop_max: 最大反復回数
  1130. alpha_when_failure: 失敗したときに選ぶステップ幅
  1131.  
  1132. Returns:
  1133. 強いWolfe条件を満たすステップ幅
  1134. """
  1135. phi_0, dphi_0 = phi(0), dphi(0)
  1136.  
  1137. for _ in range(loop_max):
  1138. # alpha_lo, alpha_hiに挟まれた値から
  1139. # 新しいステップ幅の候補を選ぶ．
  1140. alpha_j = choose_alpha(alpha_lo, alpha_hi, phi, dphi)
  1141.  
  1142. # φの関数値
  1143. phi_j = phi(alpha_j)
  1144.  
  1145. if phi_j > phi_0 + c1*alpha_j*dphi_0 or phi_j >= phi(alpha_lo):
  1146. alpha_hi = alpha_j
  1147.  
  1148. else:
  1149. dphi_j = dphi(alpha_j)
  1150. if np.abs(dphi_j) <= -c2*dphi_0:
  1151. # 強いWolfe条件を満たす
  1152. return alpha_j
  1153.  
  1154. if dphi_j*(alpha_hi - alpha_j) >= 0:
  1155. alpha_hi = alpha_lo
  1156.  
  1157. alpha_lo = alpha_j
  1158.  
  1159. # 探索に失敗した場合
  1160. return alpha_when_failure
  1161.  
  1162.  
  1163. def choose_alpha(alpha_i_1, alpha_i, phi, dphi, eps_alpha=1.0e-5):
  1164. """多項式補間に基づいて，新しいステップ幅の候補を生成して返す．
  1165.  
  1166. Args:
  1167. alpha_i_1: ステップ幅の候補
  1168. alpha_i: ステップ幅の候補
  1169. phi: phi(α) = f(x_k + α_kp_k) となる関数
  1170. dphi: phiの導関数
  1171. eps_alpha: αに関するしきい値
  1172.  
  1173. Returns:
  1174. 新しいステップ幅の候補
  1175. """
  1176. if np.abs(alpha_i - alpha_i_1) < eps_alpha:
  1177. # alpha_i, alpha_i_1 が近すぎる場合は，
  1178. # alpha_i, alpha_i_1 の中点を返す．
  1179. return (alpha_i + alpha_i_1) / 2
  1180.  
  1181. # 2点の関数値と導関数値 φ(α_i), φ(α_{i-1}), φ'(α_i), φ'(α_{i-1})から，
  1182. # Hermite補間によって3次関数 ψ を求め
  1183. # その極小点をもって新しいステップ幅の候補とする．
  1184. phi_i, phi_i_1 = phi(alpha_i), phi(alpha_i_1)
  1185. dphi_i, dphi_i_1 = dphi(alpha_i), dphi(alpha_i_1)
  1186. d1 = dphi_i + dphi_i_1 - 3*(phi_i - phi_i_1)/(alpha_i - alpha_i_1)
  1187.  
  1188. # 補間多項式 ψ の最高次係数
  1189. leading_coefficient = 2*d1 + dphi_i + dphi_i_1
  1190. eps_leading_coeff = 1.0e-15
  1191. if np.abs(leading_coefficient) < eps_leading_coeff:
  1192. # 補間多項式 ψ が2次以下の関数になる場合は，alpha_i, alpha_i_1 の中点を返す．
  1193. return (alpha_i + alpha_i_1) / 2
  1194.  
  1195. # 補間多項式 ψ の導関数 ψ' の判別式
  1196. discriminant = d1*d1 - dphi_i_1*dphi_i
  1197.  
  1198. if discriminant < 0:
  1199. # 補間3次多項式が極値をもたない場合は，
  1200. # alpha_i, alpha_i_1 の中点を返す．
  1201. return (alpha_i + alpha_i_1) / 2
  1202.  
  1203. d2 = np.sqrt(discriminant)
  1204. alpha_new = alpha_i - (alpha_i - alpha_i_1)*(dphi_i + d2 - d1)/(dphi_i - dphi_i_1 + 2*d2)
  1205.  
  1206. if (alpha_i_1 - alpha_new)*(alpha_new - alpha_i) < 0:
  1207. # alpha_new が alpha_i_1 と alpha_iの間にない場合は
  1208. # alpha_i, alpha_i_1 の中点を返す．
  1209. # この評価は alpha_i_1 と alpha_i の大小関係によらない．
  1210. return (alpha_i + alpha_i_1) / 2
  1211.  
  1212. if np.abs(alpha_i - alpha_new) < eps_alpha \
  1213. or np.abs(alpha_i_1 - alpha_new) < eps_alpha \
  1214. or alpha_new < eps_alpha:
  1215. # 新しく生成された alpha_new が
  1216. # alpha_i, alpha_i_1 に近すぎる場合や
  1217. # 0に近すぎる場合は alpha_i, alpha_i_1 の中点を返す．
  1218. return (alpha_i + alpha_i_1) / 2
  1219.  
  1220. # 新しく生成された alpha_new が alpha_i_1 と alpha_i の間にあり，
  1221. # 適切な値と判断できたのでそれを返す．
  1222. return alpha_new
  1223.  
  1224.  
  1225. def set_alpha_init(f_k, f_k_1, dphi_0):
  1226. """ステップ幅の候補の初期値を返す．
  1227.  
  1228. Args:
  1229. f_k: 第k反復の近似解における関数値
  1230. f_k_1: 第(k-1)反復の近似解における関数値
  1231. dphi_0: φ'(0)
  1232.  
  1233. Returns:
  1234. ステップ幅の候補の初期値
  1235. """
  1236. alpha_1 = 2*(f_k - f_k_1) / dphi_0
  1237. alpha_1 *= 1.01
  1238. alpha_1 = 1.0 if alpha_1 > 1.0 else alpha_1
  1239. return alpha_1
  1240.  
  1241.  
  1242. def main():
  1243. """サンプルプログラム
  1244. """
  1245. # 目的関数とその導関数
  1246. f = lambda x: (x[0] - 4.0)**4 + (x[1] - 4.0)**4
  1247. df = lambda x: np.array([4*(x[0] - 4.0)**3, 4*(x[1] - 4.0)**3])
  1248.  
  1249. # 初期点
  1250. x0 = np.array([1.0, 1.0])
  1251.  
  1252. # 最適解を求める
  1253. try:
  1254. x = optimize(x0, f, df)
  1255. print(x)
  1256.  
  1257. except Exception as e:
  1258. print('An error occurred: %s' % str(e))
  1259.  
  1260.  
  1261. if __name__ == '__main__':
  1262. main()
  1263. \end{lstlisting}
  1264.  
  1265. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!