next up previous
Next: アルゴリズムの一般形 Up: 内点法のアルゴリズムの一般形 Previous: 中心パス


アフィンスケーリング方向と中心化方向

以上の議論を踏まえた上で, 2種類の異なる探索ベクトルの決め方について述べよう。

まず最初に, (SP)を変数$ \vec{x}$$ \vec{s}$に関する非線形関数

\begin{displaymath}\begin{split}\vec{F}(\vec{\xi},\vec{s})= \begin{bmatrix}\vec{...
...i}-\vec{s}+\vec{q}\\ \vec{s}\vec{\xi} \end{bmatrix} \end{split}\end{displaymath} (80)

の零点を求める問題とみなす。 点$ \vec{\xi}$ $ \vec {s}=\vec {M}\vec {\xi}+\vec {q}$が与えられているとき, $ \vec{\xi}^{\prime} =\vec{\xi}+\vec{\Delta \xi}_{a} $および $ \vec{s}^{\prime} =\vec{s}+\vec{\Delta s}_{a} $として $ \vec{F}(\vec{\xi}^{\prime},\vec{s}^{\prime})=\vec{0}$ $ \vec{\Delta \xi}_{a}$ $ \vec{\Delta s}_{a}$について Tailor展開によって近似的に解くと, $ \vec{\Delta \xi}_{a}$ $ \vec{\Delta s}_{a}$は方程式

$\displaystyle \begin{bmatrix}\vec{M} & -\vec{I}\\ \vec{S} & \vec{\Xi} \end{bmat...
...}_{a} \end{bmatrix} = \begin{bmatrix}\vec{0} \\ -\vec{s}\vec{\xi} \end{bmatrix}$ (81)

の解となる。 なお, 適当な正の定数$ \alpha$を取り, $ \vec{\xi}^{\prime} =\vec{\xi}+\alpha \vec{\Delta \xi}_{a} $および $ \vec{s}^{\prime} =\vec{s} +\alpha \vec{\Delta s}_{a} $とすると,

$\displaystyle \vec{M}(\vec{\xi}^{\prime})+\vec{q}
= \vec{s}+\alpha \vec{M}\vec{\Delta \xi}_{a}
= \vec{s}^{\prime}
$

となる。よって, 任意の$ \alpha$に対し, $ \vec{s}^{\prime}$ $ \vec{\xi}^{\prime}$は 等式 $ \vec{s}^{\prime}=\vec{M}\vec{\xi}^{\prime}+\vec{q}$を満たす。 (74)を解くことによって得られる探索ベクトル $ (\vec{\Delta \xi}_{a}^T,\vec{\Delta s}_{a}^T)^T$をアフィンスケーリング方向と呼ぶ。

アフィンスケーリング方向は目的関数を減少させるには都合が良いが, 制約条件を見たす領域の境界に解を誘導する可能性があるという点では不都合である。 ところで, 解を内点に誘導するには, 中心パス上の点を利用するのが良い。そこで, パラメータ$ \mu$を適当に決め, それ対応する中心パス上の点を求める問題を考える。 パラメータ$ \mu$の選び方にはいろいろなものが考えられるが, たとえば目的関数値を現在の値の $ 1/\mathop {\rm dim}\vec{\xi}$にすることを目指す, すなわち $ \mu=(1/\mathop {\rm dim}\vec{\xi})\vec{s}^T\vec{\xi}$とするという方法が考えられる。 この問題も, 先と同様に, 関数

\begin{displaymath}\begin{split}\vec{G}(\vec{\xi},\vec{s})= \begin{bmatrix}\vec{...
...vec{q}\\ \vec{s}\vec{\xi}-\mu \vec{1} \end{bmatrix} \end{split}\end{displaymath} (82)

の零点を求める問題に帰着される。 $ \vec{\xi}^{\prime} =\vec{\xi}+\vec{\Delta \xi}_{c}$, $ \vec{s}^{\prime} =\vec{s}+\vec{\Delta s}_{c}$とし, (75)をTailor展開によって近似的に解くと, $ \vec{\Delta \xi}_{c}$ $ \vec{\Delta s}_{c}$は方程式

$\displaystyle \begin{bmatrix}\vec{M} & -\vec{I}\\ \vec{S} & \vec{\Xi} \end{bmat...
...matrix} = \begin{bmatrix}\vec{0} \\ -\vec{s}\vec{\xi}+\mu \vec{1} \end{bmatrix}$ (83)

の解となる。 (76)を解くことによって得られる探索ベクトル $ (\vec{\Delta \xi}_{c}^{T},\vec{\Delta s}_{c}^{T})^T$を中心化方向と呼ぶ。

これらの探索ベクトルを用いた解法は, Newton法による非線形方程式の求解の一種となる。


next up previous
Next: アルゴリズムの一般形 Up: 内点法のアルゴリズムの一般形 Previous: 中心パス
Shigeru HANBA
平成16年3月19日