\documentclass{jsarticle}
\usepackage{ascmac}
\usepackage{amsmath, amssymb}
\usepackage[dvipdfm]{graphicx,color}
%
\parindent=0pt
%
\def\mathvc#1{\mbox{\boldmath $#1$}}
\begin{document}
\section{Steepest Descent method (SD method, 最急降下法)}
\subsection{一般的SD法}
$n$次元ベクトル$\mathvc x$についての関数$f(\mathvc x)$について最小化することを考える。
\begin{equation}
\mathrm{grad}f(\mathvc x_k)\ \left(=\ \nabla f(\mathvc x_k)\right)\ =\ \mathvc 0\ \mbox{（収斂条件）}
\end{equation}
また解は次のように更新される。
\begin{equation}
\mathvc x_{k+1}=\mathvc x_k-\alpha_k\nabla f(\mathvc x_k)\ \mbox{（直線探索）}
\end{equation}
ここで$\alpha_k$は$f(\mathvc x_{k+1})$が最小化されるように決定される。一般的に最急降下法はこれを繰り返すことで最良の$\mathvc x$を探査する。
この方法の場合、収束が遅いという問題が生じる。この問題を克服するため2次近似を行うニュートン法の改良が現在の主流になっている。
\subsection{2次近似の下でのニュートン法に基づく改良}
関数$f(\mathvc x)$について$\mathvc x_k$の下でTaylor展開を行う。
\begin{equation}
f(\mathvc x)=f(\mathvc x_k)+(\mathvc x-\mathvc x_k)^T\nabla f(\mathvc x_k)+\frac12(\mathvc x-\mathvc x_k)^T\mathvc F(\mathvc x_k)(\mathvc x-\mathvc x_k)
\end{equation}
ここで$\mathvc F(\mathvc x_k)$は$f(\mathvc x)$について$\mathvc x=\mathvc x_k$におけるHessian matrixである($\mathvc F(\mathvc x_k)=\nabla\left(\nabla f(\mathvc x)\right)^T |_{\mathvc x=\mathvc x_k}$)。$f(\mathvc x)$の第一変分は次のように求められる。
\begin{eqnarray}
\delta f&=&\delta x^T \nabla f(\mathvc x_k)+\frac12\delta\mathvc x^T\mathvc F(\mathvc x_k)(\mathvc x-\mathvc x_k)+\frac12\underbrace{(\mathvc x-\mathvc x_k)^T\mathvc F(\mathvc x_k)\delta\mathvc x}_{\left[\delta\mathvc x^T\mathvc F(\mathvc x_k)(\mathvc x-\mathvc x_k)\right]^\ast} \nonumber \\
&=&\delta\mathvc x^T\left[\nabla f(\mathvc x_k)+\mathvc F(\mathvc x_k)(\mathvc x-\mathvc x_k)\right] \qquad (\because\mbox{実空間での場合を考える})
\end{eqnarray}
したがって最適な$\mathvc x_{k+1}$は次の通り求められる。
\begin{equation}
\mathvc x_{k+1}=\mathvc x_k-\left[\mathvc F(\mathvc x_k)\right]^{-1}\nabla f(\mathvc x_k)
\end{equation}
したがって2次で十分近似可能な場合には、一回の操作で最適解を得ることが可能となる。
$f(\mathvc x)$が十分滑らかでかつ$\mathvc F(\mathvc x)$が正定値となる場合には、$\mathvc x_0$を十分最適解$\mathvc x$に近く選ぶことにより、次式が成立する。
\begin{equation}
\left|\mathvc x_{k+1}-\mathvc x\right|\leq M\left|\mathvc x_k-\mathvc x\right|^2
\end{equation}
この不等式のように、右辺のべき乗が2で成立する場合には、2次収束するといい、誤差が小さくなると加速度的に収束することが言える。一般的な最急降下法の場合1次収束であり、最適解近傍では急速に収束することが分かる。
この方法は非常に強力な反面、Hessian matrixの逆行列を計算する必要があり全体として計算速度は速くならない。
\end{document}
