next up previous
Next: 線形計画問題(SP)の意味 Up: 内点法 Previous: 内点法


内点法のアルゴリズム

基準形で記述された最適化問題

$\displaystyle {\rm (P)}\quad \min \left \{ z=\vec{c}^T \vec{x}: \vec{A}\vec{x} \geq \vec{b}, \vec{x} \geq \vec{0} \right \}$ (30)

を考える。(32)を主問題と呼ぶ。(32)に対し, 双対問題と呼ばれる問題が,

$\displaystyle {\rm (D)}\quad \max \left \{ w=\vec{b}^T\vec{y}: \vec{A}^T\vec{y} \leq \vec{c},\vec{y} \geq \vec{0} \right \}$ (31)

で定義される。ここに, $ \max$ は maximize の略であり, 目的関数を最大化する問題をあらわす。なお, $ \vec{x} \in {\mathbb{R}}^n$, $ \vec{y} \in {\mathbb{R}}^m$であるvi)

主-双対法は, 簡単に言うと, (P)と(D)をまとめて解く方法である。 以下では, まず繰り返し計算のための初期値を定め, 続いて(P)と(D)を同時に解くために新たな問題(SP)を定義し, さいごに繰り返し計算のアルゴリズムを述べる。

まず, $ \vec{x}$$ \vec{y}$の適当な 初期値 $ \vec{x}^0 > \vec{0}$, $ \vec{y}^0 > \vec{0}$を決める。 これは正であればどのように取っても構わない。 次に, $ \vec{p}^0=1/\vec{x}^0$, $ \vec{t}^0=1/\vec{y}^0$とおく。パラメータ $ \bar{\vec{b}}$, $ \bar{\vec{c}}$, $ \beta$

\begin{displaymath}\begin{split}&\bar{\vec{b}} = \vec{t}^0+\vec{b} -\vec{A} \vec...
... &\beta = 1-\vec{b}^T\vec{y}^0 +\vec{c}^T \vec{x}^0 \end{split}\end{displaymath} (32)

と定義する。続いて, 行列$ \vec{M}$およびベクトル$ \vec{q}$

\begin{displaymath}\begin{split}\vec{M}&= \begin{bmatrix}\vec{0}_{m \times m}& \...
...\vec{0}_{n} 0 n+m+2 \end{array} \end{bmatrix} \end{split}\end{displaymath} (33)

と定義し, 次の問題を考える。

$\displaystyle {\rm {(SP)}}\quad \min \left \{ \vec{q}^T \vec{\xi}: \vec{M} \vec{\xi} + \vec{q} \geq \vec{0}, \vec{\xi} \geq \vec{0} \right \}$ (34)

ここに, $ \vec{\xi}=[\vec{y}^T, \vec{x}^T, \kappa, \theta]^T$$ n+m+2$ 次元のベクトルである。 問題(SP)のように, 制約条件に対応する行列$ \vec{M}$が歪対称行列 vii) であり, 非負のベクトル$ \vec{q}$が制約条件と目的関数の双方にあらわれる問題を, 歪対称問題と呼ぶ。

与えられた$ \vec{\xi}$に対し, (SP)の制約条件であらわれた式 $ \vec{M}\vec{\xi}+\vec{q}$が取る値を $ \vec{s}(\vec{\xi})$ とおく。すなわち,

$\displaystyle \vec{s}(\vec{\xi}) = \vec{M} \vec{\xi} +\vec{q}$ (35)

と定義する。また, 行列$ \vec{S}$, $ \vec{\Xi}$

$\displaystyle \vec{S}={\rm diag}[s_1,\ldots,s_{m+n+2}], \quad \vec{\Xi}={\mathop {\rm diag}}[\xi_1,\ldots,\xi_{m+n+2} ]$ (36)

と定義する。ただし, $ \mathop {\rm diag}[x_,\ldots,x_k]$は 対角要素が $ x_1,\ldots,x_k$でそれ以外の要素が零の正方行列をあらわす。

以上の準備のもとで, 2種類の内点法のアルゴリズムについて述べる。 最初のアルゴリズムは, Dikinステップ法と呼ばれるものである。

内点法(Dikinステップ法)

(初期化)
精度パラメータ $ \varepsilon$を適当に決める。また, $ \vec{\xi} := [(\vec{y}^0)^T, (\vec{x}^0)^T, 1, 1]^T$, $ \vec{s}:=\vec{s}(\vec{\xi} )$とする。 さらに, ステップ幅$ \alpha$を決める。ただし $ 0<\alpha\leq 1$である。
(ループ)
以下のプログラムを実行する。

        while 
$ \vec{\xi}^T\vec{s} \geq \varepsilon$ do

begin
$ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s}:=\vec{s}(\vec{\xi} )$
end
ここに, $ \vec{\Delta \xi}$

$\displaystyle (\vec{S}+\vec{\Xi} \vec{M}) \vec{\Delta \xi} = -\frac{\vec{\xi}^2 \vec{s}^2}{\Vert\vec{\xi} \vec{s}\Vert}$ (37)

を解くことで得られる。

このアルゴリズムによって最適解が得られるための十分条件は, ステップ幅$ \alpha$が不等式

$\displaystyle 0 < \alpha \leq \frac{1}{2 \sqrt{n+m+2}}$ (38)

を満たすことである viii) 。 とくに,

$\displaystyle \alpha=1/(2 \sqrt{n+m+2})
$

としたときには, 最適解を得るために必要な繰り返し計算の回数は高々

$\displaystyle 2 (n+m+1) \log \frac{n+m+2}{\varepsilon}$ (39)

回であることが示せる[5]。 なお, (41)において, 小数点以下は切り上げて考えるものとする。

問題(36)を初期値 $ \vec{\xi}^0$のもとで解き, $ \vec{q}^T\vec{\xi}^{\ast}=0$なる最適解 $ \vec{\xi}^{\ast}= [\vec{y}^{\ast}, \vec{x}^{\ast}, \kappa^{\ast}, \theta^{\ast}]^T$ が得られたとしよう。このとき $ \kappa^{\ast} \neq 0$であれば, もとの問題の最適解は

$\displaystyle \bar{\vec{x}}= \frac{\vec{x}^{\ast}}{\kappa^{\ast}}, \quad \bar{\vec{y}}= \frac{\vec{y}^{\ast}}{\kappa^{\ast}}$ (40)

となる。 $ \kappa^{\ast} =0$のときには, 最適解は存在しない。すなわち, 制約条件を 満たす領域が存在しないか, 目的関数の値は 有限にならない。これについては, 第2.4.2節においてもう少し詳しく説明する。

続いて, ショートステップパス追跡法と呼ばれるアルゴリズムについて述べる。 これは, 次のようなアルゴリズムである。

内点法(ショートステップパス追跡法)

(初期化)
精度パラメータ $ \varepsilon$を適当に決める。 また, $ \vec{\xi} :=\vec{\xi}^0$, $ \vec{s}:=\vec{s}(\vec{\xi} )$とする。 さらに,

$\displaystyle \sigma= 1-0.4/\sqrt{n+m+2}$ (41)

とおく。
(ループ)
以下のプログラムを実行する。

          while 
$ \vec{\xi}^T\vec{s} \geq \varepsilon$ do

begin
$ \mu := \vec{s}^T\vec{\xi}/(n+m+2)$
$ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s}:=\vec{s}(\vec{\xi} )$
end
ここに, $ \vec{\Delta \xi}$は線形方程式

$\displaystyle (\vec{S}+\vec{\Xi} \vec{M}) \vec{\Delta \xi} = -\vec{s}\vec{\xi}+\sigma \mu \vec{1}$ (42)

の解である。 各々のステップで(44)を解き直す必要があることに注意せよ。

Dikinステップ法は最急降下法の一種である。 これに対して, ショートステップパス追跡法はNewton法の一種である。 一般にショートステップパス追跡法はDikinステップ法よりは高速である。 Dikinステップ法, ショートステップパス追跡法のいずれも, 理論的な特性は良いが, 実際の問題に適用すると実行が極めて遅いという 特徴がある。より実用的なアルゴリズムとしては, ロングステップパス追跡法, Mehrotraの予測子・修正子法などがある.

以下では, まず第2.4.2節において, 本節で利用された行列$ \vec{M}$などの意味を説明する。 続いて, 第2.4.3節において Dikinステップ法の意味を説明する。 第2.4.4節では, Newton法に基づく内点法の一般的なアルゴリズム について説明する。これらは実験とは直接関係ないので, 興味のない読者は読み飛ばしてよい。

$ \blacktriangleright$


next up previous
Next: 線形計画問題(SP)の意味 Up: 内点法 Previous: 内点法
Shigeru HANBA
平成15年11月16日