内点法
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[数理計画法]]
- 内点法
-- 主問題~
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}{\...
収束速度が係数に依らず、問題の次元にのみ依っている。
-- 主問題・双対問題の最適解&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)_...
&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});は全要...
-- 中心線の近傍~
&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 \leq x_{i}s_{i} \leq (1+\beta)\mu);~
&mimetex((1-\beta)\mu \mathbb{1} \leq x \circ s \leq (1+\...
-- 元の問題を解くことは&mimetex(\mu \to 0 );のときの&mime...
現在位置&mimetex((x,s,y));、&mimetex(\mu = \frac{x^{T}s}{...
パラメタ&mimetex(0 \leq \sigma \leq 1);を使って、平均が&m...
移動分を&mimetex((\Delta x,\Delta s,\Delta y));として、~
&mimetex((x+\Delta x)\circ (s+\Delta s) = x\circ s + \Del...
&mimetex(x \circ s + \Delta x \circ s + x \circ \Delta s ...
&mimetex(A \Delta x = 0);~
&mimetex(\Delta s + A^{T}\Delta y = 0);~
これらの条件を満たすような&mimetex((\Delta x,\Delta s,\De...
--- この解について、~
&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 ...
&mimetex( = \mu(x,s) + \frac{t}{n}(\Delta x^{T}s + x^{T}\...
&mimetex( = (1-t)\mu(x,s) + \frac{t}{n}(x^{T}s \Delta x^{...
&mimetex(\mu(t) = (1-t)\mu(x,s) + t\sigma \mu(x,s));
終了行:
[[数理計画法]]
- 内点法
-- 主問題~
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}{\...
収束速度が係数に依らず、問題の次元にのみ依っている。
-- 主問題・双対問題の最適解&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)_...
&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});は全要...
-- 中心線の近傍~
&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 \leq x_{i}s_{i} \leq (1+\beta)\mu);~
&mimetex((1-\beta)\mu \mathbb{1} \leq x \circ s \leq (1+\...
-- 元の問題を解くことは&mimetex(\mu \to 0 );のときの&mime...
現在位置&mimetex((x,s,y));、&mimetex(\mu = \frac{x^{T}s}{...
パラメタ&mimetex(0 \leq \sigma \leq 1);を使って、平均が&m...
移動分を&mimetex((\Delta x,\Delta s,\Delta y));として、~
&mimetex((x+\Delta x)\circ (s+\Delta s) = x\circ s + \Del...
&mimetex(x \circ s + \Delta x \circ s + x \circ \Delta s ...
&mimetex(A \Delta x = 0);~
&mimetex(\Delta s + A^{T}\Delta y = 0);~
これらの条件を満たすような&mimetex((\Delta x,\Delta s,\De...
--- この解について、~
&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 ...
&mimetex( = \mu(x,s) + \frac{t}{n}(\Delta x^{T}s + x^{T}\...
&mimetex( = (1-t)\mu(x,s) + \frac{t}{n}(x^{T}s \Delta x^{...
&mimetex(\mu(t) = (1-t)\mu(x,s) + t\sigma \mu(x,s));
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
