next up previous
: 歪対称問題 : 内点法 : 内点法

はじめに

本項は, 琉球大学工学部電気電子工学科の4年次専門実験で提供されている 「線形計画法」の追加資料として作成されたものである. 実験指導書では内点法において解の存在性などに関する 数学的事実を詳しく述べる余裕がなかったので, 興味のある学生向けに, 本項で必要な事項を証明つきで説明する.

本項の解説の対象となるのは, 内点法の一種である, 主-双対内点法と呼ばれるアルゴリズムである. 本稿の構成は以下の通りである. 第2節で, 歪対称問題と呼ばれる問題を定式化し, 内点法のアルゴリズムの解析で中心的な役割を果たす 中心パスと強相補解について述べる. 最初に歪対称問題という特別な問題について議論する理由は, 与えられた線形計画問題を歪対称問題に帰着させて解くことが つねに可能だからである. この事実については 第3節で議論する. さらに, 第4で, 歪対称問題の数値解法および 収束の速さと数値解に含まれる誤差について議論する. また, 付録AにScilabによる ショートステップパス追跡法のプログラムを, 付録Bにロングステップパス追跡法のプログラムを示す.

典拠について述べておこう. 第2節と第3節 はおおむね文献[3]により, 第4はおおむね文献[4]による. 日本語の用語については[1]を参考にした. 凸関数に関する記述は[2]によった.

本項では次のような記号を用いる. 記号 $ \mathbb{R}^{n}$によって$ n$次元数空間をあらわす. ベクトルおよび行列にはボールド体を用いる. 特に断らない限りベクトルは縦ベクトルである. 記号 $ ^T$によってベクトルや行列の転置をあらわす. 記号$ \vec{0}$は零ベクトルや零行列を, $ \vec{1}$は全要素が1のベクトルを, $ \vec{I}$は単位行列をあらわす. $ n$次のベクトル$ \vec{x}$$ \vec{y}$に対し, $ \vec{x}\vec{y}$という記号で, 各ベクトルを 成分ごとに掛けあわせて得られるベクトルをあらわす. すなわち, $ \vec{x}=[x_1,\ldots,x_n]^T$ $ \vec{y}=[y_1,\ldots,y_n]$に対し, $ \vec{x}\vec{y}= [x_1 y_1,\ldots, x_n y_n]^T$ である. また, $ \vec{x}^2=[x_1^2,\ldots,x_n^2]^T$, $ 1/\vec{x}=[1/x_1,\ldots,1/x_n]^T$, $ \vec{x}^{-1/2}=[1/\sqrt{x_1},\ldots,1/\sqrt{x_n}]^T$ という記法を用いることがある. 特に断らない限り, ベクトルのノルムはユークリッドノルムであるものとし, これを $ \Vert\vec{\cdot}\Vert$であらわす( $ \Vert\vec{x}\Vert=\sqrt{x_1^2+\cdots+x_n^2}$である). 記号 $ \vec{x} \geq \vec{y}$によって, $ 1$から$ n$までのすべての$ i$に対し $ x_i \geq y_i$となる ことをあらわす. $ \vec{x}>\vec{y}$, $ \vec{x}\leq \vec{y}$, $ \vec{x} < \vec{y}$について も同様である. ベクトルに対応する大文字の記号で, そのベクトルの各要素を 対角要素としてならべた対角行列をあらわすことがある. たとえば, ベクトル$ \vec{x}$に対し,

$\displaystyle \vec{X}
=
\begin{bmatrix}
x_1&0 &\cdots& 0\\
0&\ddots&\ddots& \vdots\\
\vdots&\ddots&\ddots& 0\\
0&\cdots&0 & x_n\\
\end{bmatrix}$

である. これを $ \mathop {\rm diag}(\vec{x})$, $ \mathop {\rm diag}(x_1,\ldots,x_n)$などと 書き表すこともある. 最小化問題を書き下すときには,

$\displaystyle \min\{$目的関数$\displaystyle :$ 制約条件$\displaystyle \}
$

という記法を用いる. 記号$ \min$は minimize の略である. 同様に, 最大化問題を書き下すときには,

$\displaystyle \max\{$目的関数$\displaystyle :$ 制約条件$\displaystyle \}
$

という記法を用いる. 記号$ \max$は maximize の略である. 行列$ \vec{M}$が歪対称行列であるとは, $ \vec{M}$が正方行列で, $ \vec{M}^T=-\vec{M}$となることをいう. 関数 $ f(\vec{x})$が凸関数であるとは, 任意の$ \vec{x}$, $ \vec{y}$ $ t \in (0,1)$に対し,

$\displaystyle f(t\vec{x}+(1-t)\vec{y}) \leq t f(\vec{x})+(1-t)f(\vec{y})$ (1)

となることをいう. (1)が等号を除いて成り立つとき, 関数 $ f(\vec{x})$は狭義凸関数であるという.



Shigeru HANBA 平成25年12月22日