内点法のバックアップ(No.4) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
内点法へ行く。
- 1 (2007-11-21 (水) 11:15:24)
- 2 (2007-11-21 (水) 11:46:39)
- 3 (2007-11-28 (水) 11:45:23)
- 4 (2007-12-06 (木) 18:16:25)

数理計画法

内点法
- 主問題
  minimize. $c^{T}x$
  s.t. $Ax=b\ \wedge\ x \geq 0$
- 双対問題
  maximize. $b^{T}y$
  s.t. $s=c-A^{T}y\ \wedge\ s\geq 0$
- Aの各行ベクトルが一次独立で、主問題・双対問題にそれぞれ
  どの成分も0にならない許容解が存在することは仮定しておく。
  このような許容解は内点許容解と呼ばれる。
- 多項式時間主双対内点法
  主問題・双対問題の許容解の空間に中心曲線を引き、
  主・双対両方の中心曲線を同時にたどって最適解に向かう。
  各反復で生成される列を $(x^k,s^k,y^k)$ として、
  $c^{T}x^{k+1} - b^{T}y^{k+1} \leq (1-\frac{0.1}{\sqrt{n}})(c^{T}x^{k}-b^{T}y^{k})$ となるように点列を生成できる。
  収束速度が係数に依らず、問題の次元にのみ依っている。
- 主問題・双対問題の最適解 $(x,s,y)$ について、
  双対定理から
  $Ax=b$
  $c-A^{T}y=s$
  $x^{T}s=0$
  $x\geq 0$
  $s\geq 0$ が成立。
  非負ベクトル $(x,s)$ の内積が0になっているので、
  内積のすべての項について $x_{i}s_{i}=0$ が成立しなければならない。
  $x_i$ と $s_i$ のどちらかは0になる。
  和をとらないベクトルの成分ごとの積、 $(x \circ s)_i = x_{i}s_{i}$ を定義し、
  $x^{T}s=0$ の代わりに
  $x \circ s=0$ を設定して問題を解く。

中心曲線
$x\circ s = \nu \mathbb{1}$
$Ax=b$
$c-A^{T}y=s$
$x \geq 0$
$s \geq 0$
$\nu$ は正のパラメタ。 $\mathbb{1}$ は全要素が1のベクトル。
中心線の近傍
$x\circ s$ の平均 $\mu = \frac{x\cdot s}{n}$ を使って、
$|x\circ s - \mu \mathbb{1}| \leq \beta \mu$ として近傍を定義し、
中心線の近傍の中で中心曲線を予測子・修正子法で辿って解に近づく。
- 近傍の性質
  $|x\circ s - \mu \mathbb{1}| \leq \beta \mu$
  $|x_{i}s_{i} - \mu| \leq \beta \mu$
  $(1-\beta)\mu \geq x_{i}s_{i} \leq (1+\beta)\mu$
  $(1-\beta)\mu \mathbb{1} \geq x \circ s \leq (1+\beta)\mu \mathbb{1}$
元の問題を解くことは $\mu \to 0$ のときの $x,y$ の値をもとめること。
現在位置 $(x,s,y)$ 、 $\mu = \frac{x^{T}s}{n}$ として
パラメタ $0 \leq \sigma \leq 1$ を使って、平均が $\sigma \mu$ である中心曲線上の点を求める。
移動分を $(\Delta x,\Delta s,\Delta y)$ として、
$(x+\Delta x)\circ (s+\Delta s) = x\circ s + \Delta x \circ s + x \circ \Delta s = \sigma \mu \mathbb{1}$ の２次の項を落として、
$x \circ s + \Delta x \circ s + x \circ \Delta s = \sigma \mu \mathbb{1}$
$A \Delta x = 0$
$\Delta s + A^{T}\Delta y = 0$
これらの条件を満たすような $(\Delta x,\Delta s,\Delta y)$ を見つける。
- この解について、
  $\mu(t) = \mu(x+t\Delta x,s+t\Delta s)$ と置くと、
  $\mu(t) = \frac{1}{n}(x+t\Delta x)^{T}(s+t\Delta s)$
  $= \mu(x,s) + \frac{t}{n}(\Delta x^{T}s + x^{T}\Delta s)$
  $= (1-t)\mu(x,s) + \frac{t}{n}(x^{T}s \Delta x^{T}s + x^{T}\Delta s)$
  $\mu(t) = (1-t)\mu(x,s) + t\sigma \mu(x,s)$