[[数理計画法]]
- 内点法
-- 主問題~
minimize. &mimetex(c^{T}x);~
s.t. &mimetex(Ax=b\ \wedge\ x \geq 0);
-- 双対問題~
maximize. &mimetex(b^{T}y);~
s.t. &mimetex(s=c-A^{T}y\ \wedge\ s\geq 0);
-- Aの各行ベクトルが一次独立で、主問題・双対問題にそれぞれ~
どの成分も0にならない許容解が存在することは仮定しておく。~
このような許容解は内点許容解と呼ばれる。
-- 多項式時間主双対内点法~
主問題・双対問題の許容解の空間に中心曲線を引き、~
主・双対両方の中心曲線を同時にたどって最適解に向かう。~
各反復で生成される列を&mimetex((x^k,s^k,y^k));として、~
&mimetex(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}));となるように点列を生成できる。~
収束速度が係数に依らず、問題の次元にのみ依っている。
-- 主問題・双対問題の最適解&mimetex((x,s,y));について、~
双対定理から~
&mimetex(Ax=b);~
&mimetex(c-A^{T}y=s);~
&mimetex(x^{T}s=0);~
&mimetex(x\geq 0);~
&mimetex(s\geq 0);が成立。~
非負ベクトル&mimetex((x,s));の内積が0になっているので、~
内積のすべての項について&mimetex(x_{i}s_{i}=0);が成立しなければならない。~
&mimetex(x_i);と&mimetex(s_i);のどちらかは0になる。~
和をとらないベクトルの成分ごとの積、&mimetex((x \circ s)_i = x_{i}s_{i});を定義し、~
&mimetex(x^{T}s=0);の代わりに~
&mimetex(x \circ s=0);を設定して問題を解く。
-- 中心曲線~
&mimetex(x\circ s = \nu \mathbb{1});~
&mimetex(Ax=b);~
&mimetex(c-A^{T}y=s);~
&mimetex(x \geq 0);~
&mimetex(s \geq 0);~
&mimetex(\nu);は正のパラメタ。&mimetex(\mathbb{1});は全要素が1のベクトル。
-- 中心線の近傍~
&mimetex(x\circ s);の平均&mimetex(\mu = \frac{x\cdot s}{n});を使って、~
&mimetex(|x\circ s - \mu \mathbb{1}| \leq \beta \mu);として近傍を定義し、~
中心線の近傍の中で中心曲線を予測子・修正子法で辿って解に近づく。
--- 近傍の性質~
&mimetex(|x\circ s - \mu \mathbb{1}| \leq \beta \mu);~
&mimetex(|x_{i}s_{i} - \mu| \leq \beta \mu);~
&mimetex((1-\beta)\mu \geq x_{i}s_{i} \leq (1+\beta)\mu);~
&mimetex((1-\beta)\mu \mathbb{1} \geq x \circ s \leq (1+\beta)\mu \mathbb{1});
&mimetex((1-\beta)\mu \leq x_{i}s_{i} \leq (1+\beta)\mu);~
&mimetex((1-\beta)\mu \mathbb{1} \leq x \circ s \leq (1+\beta)\mu \mathbb{1});
-- 元の問題を解くことは&mimetex(\mu \to 0 );のときの&mimetex(x,y);の値をもとめること。~
現在位置&mimetex((x,s,y));、&mimetex(\mu = \frac{x^{T}s}{n});として~
パラメタ&mimetex(0 \leq \sigma \leq 1);を使って、平均が&mimetex(\sigma \mu);である中心曲線上の点を求める。~
移動分を&mimetex((\Delta x,\Delta s,\Delta y));として、~
&mimetex((x+\Delta x)\circ (s+\Delta s) = x\circ s + \Delta x \circ s + x \circ \Delta s = \sigma \mu \mathbb{1});の２次の項を落として、~
&mimetex(x \circ s + \Delta x \circ s + x \circ \Delta s = \sigma \mu \mathbb{1});~
&mimetex(A \Delta x = 0);~
&mimetex(\Delta s + A^{T}\Delta y = 0);~
これらの条件を満たすような&mimetex((\Delta x,\Delta s,\Delta y));を見つける。~
--- この解について、~
&mimetex(\mu(t) = \mu(x+t\Delta x,s+t\Delta s));と置くと、~
&mimetex(\mu(t) = \frac{1}{n}(x+t\Delta x)^{T}(s+t\Delta s));~
&mimetex( = \mu(x,s) + \frac{t}{n}(\Delta x^{T}s + x^{T}\Delta s));~
&mimetex( = (1-t)\mu(x,s) + \frac{t}{n}(x^{T}s \Delta x^{T}s + x^{T}\Delta s));~
&mimetex(\mu(t) = (1-t)\mu(x,s) + t\sigma \mu(x,s));
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
