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


\chapter{制約つき最適化問題}

本章では, 
%
\begin{eqnarray}
&&g_{1}(\Dvect{x}) = 0, \cdots, g_{r}(\Dvect{x}) = 0 \\
&&g_{r+1}(\Dvect{x}) \geq 0, \cdots, g_{m}(\Dvect{x}) \geq 0 
\end{eqnarray}
%
という条件下で, 目的関数 $f(\Dvect{x})$ を最小化する問題を考える. 


\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} 式から成る連立方程式に適用するこ
と考える. \Deqref{L_1}, \Deqref{L_2} 式より $L$ を目的関数とみなせばよい
ことがわかる. ただし制約なしの最適化問題では目的関数を $\Dvect{x}$ に関
する 2 次方程式に近似するだけでよかったが, 制約つき最適化問題では
$\Dvect{x}$ と $\Dvect{\lambda}$ について停留点を求めるので, 目的関数を
$\Dvect{x}$ と $\Dvect{\lambda}$ で展開せねばならない. まず目的関数 $L$
を $\Dvect{x}_{k}$ の近傍でテーラー展開し, 2 次の微小量まで考慮する. 
そのようにして求めた $L(\Dvect{x}, \Dvect{\lambda})$ の近似関数を $Q$ と
すると, 
%
\begin{eqnarray}
 Q &=& f(\Dvect{x}_{k}) 
  + \Dgrad f(\Dvect{x}_{k}) \cdot (\Dvect{x} - \Dvect{x}_{k}) 
  + \Dinv{2} \Dlapla f(\Dvect{x}_{k})\cdot(\Dvect{x} - \Dvect{x}_{k})^{2}
  \nonumber \\
 && 
  - \Dvect{\lambda} \Dvect{g}(\Dvect{x}_{k}) 
  - \Dvect{\lambda}_{j} \Dgrad \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k}) 
  - \Dinv{2} \Dvect{\lambda}_{j} \Dlapla \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})^{2}
\end{eqnarray}
%
となる. さらに $Q$ を $\Dvect{\lambda}_{k}$ の近傍でテーラー展開すれば, 
%
\begin{eqnarray}
 Q &=& f(\Dvect{x}_{k}) 
  + \Dgrad f(\Dvect{x}_{k}) \cdot (\Dvect{x} - \Dvect{x}_{k}) 
  + \Dinv{2} \Dlapla f(\Dvect{x}_{k}) \cdot (\Dvect{x} - \Dvect{x}_{k})^{2}
  \nonumber \\
 && 
  - \Dvect{\lambda}_{k} \Dvect{g}(\Dvect{x}_{k}) 
  - \Dvect{g}(\Dvect{x}_{k}) \cdot (\Dvect{\lambda} - \Dvect{\lambda}_{k})
  \nonumber \\
 && 
  - \Dvect{\lambda}_{k} \Dgrad \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})
  - \Dgrad \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})\cdot(\Dvect{\lambda} - \Dvect{\lambda}_{k})
  \nonumber \\
 && 
  - \Dinv{2} \Dvect{\lambda}_{k} \Dlapla \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})^{2}
  - \Dinv{2} \Dlapla \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})^{2} \cdot (\Dvect{\lambda} - \Dvect{\lambda}_{k})
\end{eqnarray}
%
となる. この近似関数 $Q$ を $\Dvect{x}$ について微分すれば, 
%
\begin{eqnarray}
\Dgrad_{x} Q &=& 
   \Dgrad f(\Dvect{x}_{k})
  + \Dlapla f(\Dvect{x}_{k}) \cdot (\Dvect{x} - \Dvect{x}_{k})
  - \Dvect{\lambda} \Dgrad \Dvect{g}(\Dvect{x}_{k}) 
  - \Dvect{\lambda} \Dlapla \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k}) 
  \nonumber \\
 &=& 
  \left\{
     \Dlapla f(\Dvect{x}_{k})- \Dvect{\lambda} \Dlapla \Dvect{g}(\Dvect{x}_{k})
  \right\} (\Dvect{x} - \Dvect{x}_{k}) 
  + \Dgrad f(\Dvect{x}_{k})
  - \Dvect{\lambda} \Dgrad \Dvect{g}(\Dvect{x}_{k}) 
\end{eqnarray}
%
となるので, 停留点の条件を用いると, 
%
\begin{eqnarray}
&&  \left\{
     \Dlapla f(\Dvect{x}_{k})- \Dvect{\lambda} \Dlapla \Dvect{g}(\Dvect{x}_{k})
  \right\} (\Dvect{x} - \Dvect{x}_{k}) 
  + \Dgrad f(\Dvect{x}_{k})
  - \Dvect{\lambda} \Dgrad \Dvect{g}(\Dvect{x}_{k}) 
  = 0 \nonumber \\
&&  H(\Dvect{x}_{k}, \Dvect{\lambda}) \Dvect{d}_{k}
  - J(\Dvect{x}_{k})  \Dvect{\lambda} 
  = - \Dgrad f(\Dvect{x}_{k})
\Deqlab{grad_x}
\end{eqnarray}
%
である. ただし, 
%
\begin{eqnarray}
 H(\Dvect{x}, \Dvect{\lambda}) 
  = \Dlapla L(\Dvect{x}, \Dvect{\lambda}) 
  =  \Dlapla f(\Dvect{x}_{k})- \Dvect{\lambda} \Dlapla \Dvect{g}(\Dvect{x}_{k})
\end{eqnarray}
%
という置き換えをおこなった. 同様に近似関数 $Q$ を $\Dvect{\lambda}$ 微分す
ると, 
%
\begin{eqnarray}
\Dgrad_{\lambda} Q 
 &=& 
 -  \Dvect{g}(\Dvect{x}_{k}) 
  - \Dgrad \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})
  - \Dinv{2} \Dlapla \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})^{2} 
\end{eqnarray}
%
となり, 停留点の条件を用いると, 
%
\begin{eqnarray}
&& -  \Dvect{g}(\Dvect{x}_{k}) 
  - \Dgrad \Dvect{g}(\Dvect{x}_{k}) \cdot
  (\Dvect{x} - \Dvect{x}_{k})
  = 0 
  \nonumber \\
&&
   J(\Dvect{x}_{k}) \Dvect{d}_{k}
  = -   \Dvect{g}(\Dvect{x}_{k}) 
\Deqlab{grad_l}
\end{eqnarray}
%
が得られる. ここで $\Dvect{d}_{k}^{2}$ の項を微小量とみなして無視した. 


\Deqref{grad_x} と \Deqref{grad_l} 式より, 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}
\]
%
によって定め, \Deqref{tansaku} 式においてステップ幅を常に $\alpha = 1$ 
にとって点列 $\{\Dvect{x}_{k}\}, \{\Dvect{\lambda}_{k}\}$ を生成する.
$\Dvect{\lambda}_{k+1}$ は連立方程式の解として直接得られ
ることに注意を払う必要がある
\footnote{$H = H(\Dvect{x}_{k}, \Dvect{\lambda}_{k+1})$ とならずに $H =
H(\Dvect{x}_{k}, \Dvect{\lambda}_{k})$ となる理由は?}.
%
%ただし $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}
%
%とする. 


この方法は, 一般に収束域が狭く, 初期値 $\Dvect{x}_{0}$ の選び方によって
は発散したり, 解とは異なる Karush-Kuhn-Tucker 点に収束する可能性がある. 




