next up previous
Next: 内点法のアルゴリズム Up: 原理 Previous: ビッグM法の問題が有限の最適解を持たないとき


内点法

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

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

まず, いくつか記号の定義をしておく。 ベクトルのノルムは, $ \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$ (57)

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

$\displaystyle 1/\vec {x}=[1/x_1,\ldots,1/x_n]^T$ (58)

と定義する。





Shigeru HANBA
平成16年3月19日