% 表題: 制約なし最適化問題
%
% 履歴: 2004-06-05 杉山耕一朗

\chapter{制約なし最適化問題}

滑らかな実数値関数 $f(\Dvect{x})$ の最小値を与える $\Dvect{x}$ を求める
問題を考える. この問題を解くための反復解法 \Deqref{tansaku} 式において, 
探索ベクトル $\Dvect{d}_{k}$ は, 
%
\begin{eqnarray}
 \Dvect{d}_{k} \equiv - H_{k}^{-1} \Dgrad f(\Dvect{x})
\Deqlab{d_ippan}
\end{eqnarray}
%
という形式を取ることが多い. ここで $\Dvect{H}$ はヘッセ(Hesse)行列
と呼ばれ, 例えば最急降下法では $\Dvect{H} \equiv \Dvect{I}$ (単位行列) であり,
Newton 法では $\Dvect{H} \equiv \Dlapla f(\Dvect{x})$ である.

本章では制約なし最適化問題として, ギブス自由エネルギーを最小化するという
平衡熱力学計算に良く用いられる Newton 法, 準 Newton 法を解説する. 


\section{Newton 法}

制約なしの最適化解は, 停留点を定義する連立非線形方程式
%
\begin{eqnarray}
\Dgrad f(\Dvect{x}) = 0
\Deqlab{df=0}
\end{eqnarray}
%
を満たす. この関係式を用いることで Newton 法の探索方向を決める. 

目的関数 $f(\Dvect{x})$ を近似解 $\Dvect{x}_{k}$ のまわりでテーラー展開
し, 2 次の微小量まで考慮した 2 次近似関数を $Q$ とすると, 近似関数 $Q$
は, 
%
\begin{eqnarray}
 Q = f(\Dvect{x}_{k}) 
  + \Dgrad f(\Dvect{x}_{k}) (\Dvect{x} - \Dvect{x}_{k})
  + \Dinv{2} \Dlapla f(\Dvect{x}_{k}) (\Dvect{x} - \Dvect{x}_{k})^{2}
\Deqlab{f_taler}
\end{eqnarray}
%
と書ける. ただし, $\Dgrad = \partial/\partial \Dvect{x}_{k}$ である. 
\Deqref{f_taler} 式の $\Dvect{x}$ 微分をとると($\Dvect{x}_{k}$ 微分でない
ことに注意), 
%
\begin{eqnarray}
\DD{Q}{\Dvect{x}} 
 &=& \DD{}{\Dvect{x}} f(\Dvect{x}_{k})
 + \Dgrad f(\Dvect{x}_{k}) \cdot \DD{}{\Dvect{x}} (\Dvect{x} - \Dvect{x}_{k})
 + \Dinv{2} \Dlapla f(\Dvect{x}_{k}) \cdot
     \DD{}{\Dvect{x}} (\Dvect{x} - \Dvect{x}_{k})^{2}
\nonumber \\
 &=& 
  \Dgrad f(\Dvect{x}_{k}) + 
    \Dgrad^{2} f(\Dvect{x}_{k}) \cdot (\Dvect{x} - \Dvect{x}_{k})
\Deqlab{dQdx}
\end{eqnarray}
%
となる. \Deqref{dQdx} 式を停留点の条件 \Deqref{df=0} 式に代入することで, 
%
\begin{eqnarray}
\Dgrad f (\Dvect{x}_{k}) + \Dlapla f(\Dvect{x}_{k}) \Dvect{d}_{k} = 0
\Deqlab{d}
\end{eqnarray}
%
が得られる. ただし \Deqref{dQdx} において $\Dvect{x} - \Dvect{x}_{k}$ を
探索方向 $\Dvect{d}_{k}$ とみなした. 

Newton 法では, \Deqref{d} 式より探索方向を決め, ステップ幅を常に 
$\alpha_{k} \equiv 1$ にすることによって, 最適解 $\Dvect{x}^{*}$ に収束
させる. \Deqref{d} の定式化からわかるように, この探索方向は目的関数を変
数 $\Dvect{x}$ に関する 2 階の方程式に近似し, その停留点により目的関数の
最小値を求める方法といえる. 


\begin{figure}[h]
 \begin{center}
  \Depsf[100mm]{./ps/optimize.eps}
 \end{center}
\caption{Newton 法が生成する点列の意味}
\end{figure}



\section{準 Newton 法}

\Deqref{d} 式の $\Dlapla f(\Dvect{x}_{k})$ の直接計算は手間がかかるため, 
1959 年に W. C. Davidon は $\Dlapla f(\Dvect{x}_{k})$ を直接計算せずに済
む「可変計量法」を開発した. 現在ではその変種が数多くしられており, それら
は総称して「準 Newton 法」と呼ばれている. この方法群においては,
$\{\Dvect{x}_{k}\}, \{\Dgrad f(\Dvect{x}_{k})\}$ の情報を用いて $\Dlapla
f(\Dvect{x}_{k})$ の近似行列の系列 $\{H_{k}\}$ を構成して $\Dlapla
f(\Dvect{x}_{k})$ に代用する. 

2 つのベクトルを $\Dvect{s}_{k} \equiv \Dvect{x}_{k+1} - \Dvect{x}_{k}$, 
$\Dvect{y}_{k} \equiv \Dgrad f(\Dvect{x}_{k+1}) - \Dgrad
f(\Dvect{x}_{k})$ と定義するとき, 近似的に $\Dlapla f(\Dvect{x}) 
\Dvect{s}_{k} \approx \Dvect{y}_{k}$ が成り立つ. そこで $\Dvect{s}_{k}$ と
$\Dvect{y}_{k}$ の対が得られるたびに, セカント条件, 
%
\begin{eqnarray}
 H_{k+1} \Dvect{s}_{k} = \Dvect{y}_{k}
\Deqlab{H}
\end{eqnarray}
%
を満たすように, 近似行列を $H_{k+1} = H_{k} + \Delta H_{k}$ の形式によっ
て逐次近似していくと, 系列 $\{H_{k}\}$ はある意味で $\Dlapla
f(\Dvect{x}_{k})$ の近似になることが期待できる. そこで $\Dvect{x}_{0},
H_{0}$ を決め, \Deqref{d_ippan} 式によって探索方向 $\Dvect{d}_{0}$ を決
め, $\Dvect{x}_{1}$ を生成し, \Deqref{H} 式に基づいて $H_{1}$ を更新する.
これを反復して点列 $\{\Dvect{x}_{k}\}$ を生成する. ステップ幅の決定は
Wolfe の条件, 
%
\begin{eqnarray}
 f(\Dvect{x} + \alpha \Dvect{d}_{k}) - f(\Dvect{x}_{k}) \leq 
  \sigma_{1} \alpha (\Dgrad f(\Dvect{x}_{k}))^{T} \Dvect{d}_{k} \\
 (\Dgrad f(\Dvect{x} + \alpha \Dvect{d}_{k}))^{T} \Dvect{d}_{k} \leq 
  \sigma_{2} (\Dgrad f(\Dvect{x}_{k}))^{T} \Dvect{d}_{k} 
\end{eqnarray}
%
によって行う. ただし, 準 Newton 法においては, この条件が極端に緩くなるよ
うにこの定数 $\sigma_{1}, \sigma_{2}$ を選択すると, 総合性能が良くなるこ
とが経験的に知られている. 典型的には $\sigma_{1} \equiv 10^{-4}, 
\sigma_{2} \equiv 0.9$, さらに $H_{0}$ として単位行列が選ばれることが多
い. 

今日, 経験的にも理論的にも最も優れているとされている準 Newton 法は,
C. G. Broyden, R. Fletcher, D. Goldfalb, D. F. Shanno による BFGS 公式, 
%
\begin{eqnarray}
 H_{k+1} = H_{k} 
  - \frac
  {H_{k} \Dvect{s}_{k} \Dvect{s}_{k}^{T} H_{k}}
  {\Dvect{s}_{k}^{T} H_{k} \Dvect{s}_{k} }
  + \frac
  {\Dvect{y}_{k} \Dvect{y}_{k}^{T}}
  {\Dvect{s}_{k}^{T} \Dvect{y}_{k} }
\Deqlab{BFGS}
\end{eqnarray}
%
に基づくものである. 

準 Newton 法は制約のない最適化問題の中で最もよく使われる方法であるが, 
行列 $H_{k}$ のために大きな記憶領域を必要とする点に適用上の限界がある. 
90 年代以降の最適化法による平衡熱力学計算においては, 準 Newton 法が最も
良く利用されている. 
