next up previous
Next: 内点法の詳細 Up: 内点法 Previous: 内点法


内点法のアルゴリズム

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

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

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

$\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 \}$ (60)

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

主-双対法は, 簡単に言うと, (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} (61)

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

$\displaystyle \vec{M}= \begin{bmatrix}\vec{0}_{m \times m}& \vec{A} & -\vec{b}&...
...begin{array}{c} \vec{0}_{m}\\ \vec{0}_{n}\\ 0\\ n+m+2 \end{array} \end{bmatrix}$ (62)

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

$\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 \}$ (63)

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

問題(SP)の初期値を

$\displaystyle \vec{\xi}^0= \begin{bmatrix}(\vec{y}^0)^T, (\vec{x}^0)^T 1, 1 \end{bmatrix}^T$ (64)

とする。

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

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

と定義する。 以下では, 記法の簡単のために, しばしば, $ \vec{s}(\vec{\xi})$$ \vec{s}$と略記する。 また, $ n+m+2$次のベクトル$ \vec{\xi}$, $ \vec{s}$に対し, 行列$ \vec{\Xi}$$ \vec{S}$

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

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

以上の準備のもとで, 2種類の内点法のアルゴリズムについて述べる。

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

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

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

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

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

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

$ \mu := \vec{s}^T\vec{\xi}/(n+m+2)$
$ \vec{\xi} :=\vec{\xi} + \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}$ (68)

の解である。

問題(SP)を初期値 $ \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}}$ (69)

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

ショートステップパス追跡法には, 理論的な特性は良いが, 実際の問題に適用すると実行が極めて遅いという特徴がある。

理論的な特性はショートステップパス追跡法に劣るが実用上はより 高速なアルゴリズムに, ロングステップパス追跡法がある。

ロングステップパス追跡法について述べる前に, 記号の定義をしておく。 (61)を解いて得られる$ \vec{\xi}$とパラメータ$ \alpha$ (ただし $ 0 \leq \alpha \leq 1$)に対し,

$\displaystyle \vec{\xi}_{\alpha}=\vec{\xi} +\alpha \vec{\Delta \xi},\quad \vec{s}_{\alpha}=\vec{s}(\vec{\xi}_{\alpha} )$ (70)

と定義する。

ロングステップ追跡法のショートステップパス追跡法との相異は, (61)を解いて得られる $ \Delta \vec {\xi}$の方向に 解$ \vec{\xi}$を可能な限り大きく動かすことである。 具体的には, $ \mu=\vec{s}^T\vec{\xi}/(n+m+2)$と あらかじめ定められた定数$ \gamma$に対し, 直線探索と呼ばれる方法を用いて

$\displaystyle \vec{\xi}_{\alpha}\vec{s}_{\alpha} \geq \gamma \mu \vec{1}$ (71)

を満たす範囲で最大の$ \alpha$を求め (ただし $ 0 \leq \alpha \leq 1$), $ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $により解を更新する。

\fbox{内点法(ロングステップパス追跡法)}

(初期化)
精度パラメータ $ \varepsilon$を適当に決める。 定数$ \gamma$, $ \sigma_{\min}$, $ \sigma_{\max}$ $ 0 < \gamma < 1$, $ 0 < \sigma_{\min}< \sigma_{\max} <1$となる ように定める。
(ループ)
以下のプログラムを実行する。

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

$ \mu := \vec{s}^T\vec{\xi}/(n+m+2)$
$ \sigma \in [\sigma_{\min},\sigma_{\max}]$を定める
線形方程式(61)を解いて $ \Delta \vec {\xi}$を求める
(64)を満たす最大の $ \alpha (0 \leq \alpha \leq 1)$を求める
$ \vec{\xi} :=\vec{\xi} +\alpha \vec{\Delta \xi} $
$ \vec{s}:=\vec{s}(\vec{\xi} )$
end

直線探索により$ \alpha$を決めるときには, たとえば2分探索を用ればよい。

ロングステップパス追跡法では, パラメータ$ \sigma$の値はステップごとに変えてよい。 $ \sigma$の決め方としては, たとえばステップごとに乱数を用いて ランダムに$ \sigma$を決める, といった方法が考えられる。

実は, $ \sigma$を0に近い値にすれば $ \vec{\Delta \xi}$は目的関数をより減少させる方向 (アフィンスケーリング方向)を向き, $ \sigma$$ 1$に近い値にすれば $ \vec{\Delta \xi}$は制約条件を満たす領域からはずれない ような方向(中心化方向)を向く(第2.5.2.3節参照)。

内点法を用いた線形計画問題の求解パッケージでは, 以上で述べた2種類のアルゴリズムではなく, Mehrotraの予測子・修正子法というアルゴリズムが採用されていることが多い。 Mehrotraの予測子・修正子法は高速ではあるが若干見通しが悪いので, ここでは述べない。興味のある読者は文献[3,7]を参照してほしい。


next up previous
Next: 内点法の詳細 Up: 内点法 Previous: 内点法
Shigeru HANBA
平成16年3月19日