% 表題: Newton 法との比較
%
% 履歴: 2004-06-06 杉山耕一朗

\chapter{Newton 法との比較}

RAND 法は「制約つき最適化法」の「Newton 法」に分類される最適化法であるが,
教科書的な Newton 法の表記とは多少異なる. 本章では RAND 法を Newton 法と
比較し, その表記の差異が何に起因するか考察する. 



\section{Newton 法}

$\Dvect{g}(\Dvect{x}) = (g_{1}(\Dvect{x}) = 0, \cdots, 
g_{r}(\Dvect{x}))^{T} = 0$ という等式制約のみの場合を考える. このとき,
制約想定下で最適解 $\Dvect{x}^{*}$ に対して $\Dvect{\lambda}^{*}$ が存在
し, これらは Karush-Kuhn-Tucker 条件, すなわち変数 $\Dvect{x},
\Dvect{\lambda}$ に連立非線形方程式, 
%
\begin{eqnarray}
&& \Dgrad_{x} L(\Dvect{x}, \Dvect{\lambda}) 
  = \Dgrad_{x} f(\Dvect{x}) - (J(\Dvect{x}))^{T} \Dvect{\lambda} = 0 
\Deqlab{L_1} \\
&& \Dgrad_{\lambda} L(\Dvect{x}, \Dvect{\lambda}) 
  = \Dvect{g}(\Dvect{x}) = 0
\Deqlab{L_2}
\end{eqnarray}
%
を満たす. ただし $\lambda$ は未定乗数, $L(\Dvect{x}, \Dvect{\lambda})
\equiv f(\Dvect{x}) - \sum \lambda_{j} g_{j} (\Dvect{x})$ とし, Jacobi 
行列は $J(\Dvect{x}) \equiv \Dgrad \Dvect{g}(\Dvect{x})$ とする.  この 
Karush-Kuhn-Tucker 条件はラグランジュの未定乗数法の条件と同じものである. 
制約つき最適化法は究極的にはこの方程式を解かねばならないと言える.

Newton 法を \Deqref{L_1}, \Deqref{L_2} 式から成る連立方程式に適用するこ
とで次のアルゴリズムが得られる. 探索方向 $\Dvect{d}_{k}$ を連立一次方程
式,
%
\[
\left[
\begin{array}{cc}
 H(\Dvect{x}_{k}, \Dvect{\lambda}_{k}) & -J^{T}(\Dvect{x}_{k}) \\
 J(\Dvect{x}_{k}) & 0 
\end{array}
\right]
\left[
\begin{array}{c}
 \Dvect{d}_{k} \\
 \Dvect{\lambda}_{k+1}
\end{array}
\right]
= 
- \left[
\begin{array}{c}
 \Dgrad_{x} f(\Dvect{x}_{k}) \\
 \Dvect{g}(\Dvect{x}_{k})
\end{array}
\right]
\Deqlab{const}
\]
%
によって定め, ステップ幅を常に $\alpha = 1$ にとして点列 
$\{\Dvect{x}_{k}\}, \{\Dvect{\lambda}_{k}\}$ を生成する.
$\Dvect{\lambda}_{k+1}$ は連立方程式の解として直接得られることに注意を払
う必要がある.  ただし $H(\Dvect{x}, \Dvect{\lambda})$ は,
%
\begin{eqnarray}
 H(\Dvect{x}, \Dvect{\lambda}) = 
  \Dlapla_{x} L(\Dvect{x}, \Dvect{\lambda}) = \Dlapla_{x} f(\Dvect{x}) -
  \sum \lambda_{i} \Dlapla_{x} g_{i}(\Dvect{x})
\end{eqnarray}
%
とする. 


\section{RAND 法と Newton 法の比較}

RAND 法と前節の Newton 法を比較すると, 
%
\begin{itemize}
 \item RAND 法では目的関数をギブス自由エネルギー $G$ 自体を 
       $\Dvect{x}$ に関する 2 次式として展開するのに対し,
       Newton 法ではラグランジュ未定乗数法による関数 $L$ を展開する. 
 \item 解くべく連立方程式が, 探索ベクトル $\Dvect{d}$ ではなく
       最適解 $\Dvect{x}$ に対する方程式系になっている. 
\end{itemize}
%
という差異があることがわかる. ギブス自由エネルギーの最小化の場合には等式
制約が $\Dvect{x}$ に関する 1 次関数になっているため, ギブス自由エネルギー 
$G$ だけを $\Dvect{x}$ に関して展開すれば十分なのであり, 等式制約をその
まま使える $\Dvect{x}$ に関する方程式系として整理する方が都合が良いので
ある. 


ギブス自由エネルギーを最小化する問題について, Newton 法の形式で書くこと
を試みる. 
\Deqref{L_1} 式は, 
%
\begin{eqnarray}
 H(\Dvect{x}_{k}) \Dvect{d}_{k} - J(\Dvect{x}_{k}) \Dvect{\lambda}
  = - \Dgrad G(\Dvect{x}_k)
\end{eqnarray}
%
となる. ただし $J(\Dvect{x}) = \Dgrad g(\Dvect{x}) = a_{ie}$ であり, 
等式制約の $\Dvect{x}$ に関する 2 階微分はゼロなので, ヘッシアンは
%
\begin{eqnarray}
 H(\Dvect{x}, \Dvect{\lambda}) 
  = H(\Dvect{x}) 
  = \Dlapla G(\Dvect{x})
\end{eqnarray}
%
である. \Deqref{L_2} 式は, 
%
\begin{eqnarray}
 \Dgrad \Dvect{g}(\Dvect{x}_{k}) \Dvect{d}_{k} = - \Dvect{g}(\Dvect{x}_{k})
\end{eqnarray}
%
である. したがって前章の定式化を利用すると, 
%
\[
\left[
\begin{array}{cc}
 RT \left( \frac{\delta_{il}}{m_{i}} - \Dinv{\sum m_{i}}\right) & - \Dvect{a} \\
 \Dvect{a} & 0 
\end{array}
\right]
\left[
\begin{array}{c}
 \Dvect{d}_{k} \\
 \Dvect{\lambda}_{k+1}
\end{array}
\right]
= 
- \left[
\begin{array}{c}
 \mu^{\circ} + RT \ln{\frac{\Dvect{x}_{k}}{\sum \Dvect{x}_{k}}} + RT \ln{p/p_{0}} \\
 \Dvect{a} \Dvect{n}_{k}
\end{array}
\right]
\Deqlab{const}
\]
%
となる. 

