next up previous
Next: 内点法のアルゴリズム Up: 原理 Previous: ビッグM法


内点法

本節では内点法について述べる。

内点法は大きく分けると主内点法と主-双対法の2種類に分類されるのだが, 本節では主-双対法と呼ばれるアルゴリズムのうち 比較的簡単なもの2種類を文献[5,6]にしたがって紹介する。

まず, いくつか記号の定義をしておく。 ベクトルのノルムは, $ \Vert\vec{x}\Vert=\sqrt{\sum_{i=1}^nx_i^2}$によって定義される。 ベクトル同士のHadamard 積を, 以下によって定義する。

$\displaystyle \vec{x}\vec{s}=[x_1s_1,\ldots,x_ns_n]^T
$

また, 記法の簡単のため, ベクトル$ \vec{x}$に対し,

\begin{displaymath}
\begin{array}{ccl}
1/\vec{x}&=&[1/x_1,\ldots,1/x_n]^T,\\
\vec{x}^2 &=&[x_1^2,\ldots,x_n^2]^T
\end{array}\end{displaymath}

などと書く。





Shigeru HANBA
平成15年11月16日