Hauptseite: Unterschied zwischen den Versionen
(Hauptsätze) |
(Intexverfahren) |
||
Zeile 1: | Zeile 1: | ||
__NOTOC__ | __NOTOC__ | ||
= Willkommen bei MWiki = | = Willkommen bei MWiki = | ||
− | == | + | == Satz des Monats == |
− | + | Das Intexverfahren löst jedes lösbare LP in <math>\mathcal{O}({\vartheta}^{3})</math>. | |
− | < | + | == Beweis und Algorithmus == |
+ | Zuerst werden <math>{b}^{T}y - {c}^{T}x \le 0, Ax \le b</math> sowie <math>{A}^{T}y \ge c</math> normiert und skaliert. Die <em>Höhe</em> <math>h</math> habe den Startwert <math>h_0 := s |\min \; \{b_1, ..., b_m, -d_1, ..., -d_n\}|</math> mit dem <em>Steigerungsfaktor</em> <math>s \in \, ]1, 2]</math>.</br> | ||
+ | Das LP min <math>\{h \in [0, h_0] : x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}, y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m},{b}^{T}y - {c}^{T}x \le h, Ax - b \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, c - {A}^{T}y \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}</math> hat <math>k</math> Restriktionen und den zulässigen inneren Startpunkt <math>(x_0, y_0, h_0/s)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1}</math>, z. B. <math>(0, 0, h_0/s)^{T}</math>. Es identifiziert die zueinander dualen LPs max <math>\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}</math> und min <math>\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}</math>. | ||
+ | Der Punkt <math>p := (x, y, h)^T</math> approximiere den Schwerpunkt des Teilpolytops <math>P^*</math> zu <math>p_k^* := (\min p_k + \max p_k)/2</math>, bis <math>{|| \Delta p ||}_{1}</math> hinreichend klein ist. Hier hat <math>x</math> Vorrang vor <math>y</math>. Dann wird <math>p</math> über <math>{p}^{*}</math> in <math>\partial P^*</math> als <math>u</math> extrapoliert. Mit <math>p := p^* + (u - p^*)/s</math> wird <math>\partial P^*</math> gemieden. Darauf wird <math>p</math> tiefer erneut als Schwerpunkt approximiert. Nach optionalem Lösen aller LPs min<math>{}_{k} {h}_{k}</math> durch Bisektionsverfahren für <math>{h}_{k} \in {}^{\omega}\mathbb{R}_{\ge 0}</math> in jeweils <math>\mathcal{O}({\vartheta}^{2})</math> lässt sich <math>v \in {}^{\omega}\mathbb{R}^{k}</math> mit <math>v_k := \Delta{p}_{k} \Delta{h}_{k}/r</math> und <math>r :=</math> min<math>{}_{k} \Delta{h}_{k}</math> ermitteln. Vereinfacht sei <math>|\Delta{p}_{1}| = ... = |\Delta{p}_{m+n}|</math>. | ||
− | + | Hierbei wäre min <math>{h}_{m+n+1}</math> für <math>p^* := p + tv</math> mit <math>t \in {}^{\omega}\mathbb{R}_{\ge 0}</math> und <math>{v}_{m+n+1} = 0</math> ebenso zu lösen. Folgt min<math>{}_{k} {h}_{k} r = 0</math>, wird aufgehört, andernfalls wiederholt, bis min <math>h = 0</math> oder min <math>h > 0</math> feststeht.</br> | |
+ | Falls erforderlich werden die Restriktionen vorübergehend um einen gleichen kleinen Betrag abgeschwächt. Da fast jeder Durchlauf <math>h</math> in <math>\mathcal{O}({\omega\vartheta}^{2})</math> wenigstens halbiert, liefert der starke Dualitätssatz die Behauptung.<math>\square</math> | ||
− | + | == Leseempfehlung == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
[https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik] | [https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik] | ||
[[en:Main Page]] | [[en:Main Page]] |
Version vom 4. Januar 2021, 20:15 Uhr
Willkommen bei MWiki
Satz des Monats
Das Intexverfahren löst jedes lösbare LP in [math]\displaystyle{ \mathcal{O}({\vartheta}^{3}) }[/math].
Beweis und Algorithmus
Zuerst werden [math]\displaystyle{ {b}^{T}y - {c}^{T}x \le 0, Ax \le b }[/math] sowie [math]\displaystyle{ {A}^{T}y \ge c }[/math] normiert und skaliert. Die Höhe [math]\displaystyle{ h }[/math] habe den Startwert [math]\displaystyle{ h_0 := s |\min \; \{b_1, ..., b_m, -d_1, ..., -d_n\}| }[/math] mit dem Steigerungsfaktor [math]\displaystyle{ s \in \, ]1, 2] }[/math].
Das LP min [math]\displaystyle{ \{h \in [0, h_0] : x \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}, y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m},{b}^{T}y - {c}^{T}x \le h, Ax - b \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, c - {A}^{T}y \le (h, ..., h)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\} }[/math] hat [math]\displaystyle{ k }[/math] Restriktionen und den zulässigen inneren Startpunkt [math]\displaystyle{ (x_0, y_0, h_0/s)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1} }[/math], z. B. [math]\displaystyle{ (0, 0, h_0/s)^{T} }[/math]. Es identifiziert die zueinander dualen LPs max [math]\displaystyle{ \{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\} }[/math] und min [math]\displaystyle{ \{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\} }[/math].
Der Punkt [math]\displaystyle{ p := (x, y, h)^T }[/math] approximiere den Schwerpunkt des Teilpolytops [math]\displaystyle{ P^* }[/math] zu [math]\displaystyle{ p_k^* := (\min p_k + \max p_k)/2 }[/math], bis [math]\displaystyle{ {|| \Delta p ||}_{1} }[/math] hinreichend klein ist. Hier hat [math]\displaystyle{ x }[/math] Vorrang vor [math]\displaystyle{ y }[/math]. Dann wird [math]\displaystyle{ p }[/math] über [math]\displaystyle{ {p}^{*} }[/math] in [math]\displaystyle{ \partial P^* }[/math] als [math]\displaystyle{ u }[/math] extrapoliert. Mit [math]\displaystyle{ p := p^* + (u - p^*)/s }[/math] wird [math]\displaystyle{ \partial P^* }[/math] gemieden. Darauf wird [math]\displaystyle{ p }[/math] tiefer erneut als Schwerpunkt approximiert. Nach optionalem Lösen aller LPs min[math]\displaystyle{ {}_{k} {h}_{k} }[/math] durch Bisektionsverfahren für [math]\displaystyle{ {h}_{k} \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] in jeweils [math]\displaystyle{ \mathcal{O}({\vartheta}^{2}) }[/math] lässt sich [math]\displaystyle{ v \in {}^{\omega}\mathbb{R}^{k} }[/math] mit [math]\displaystyle{ v_k := \Delta{p}_{k} \Delta{h}_{k}/r }[/math] und [math]\displaystyle{ r := }[/math] min[math]\displaystyle{ {}_{k} \Delta{h}_{k} }[/math] ermitteln. Vereinfacht sei [math]\displaystyle{ |\Delta{p}_{1}| = ... = |\Delta{p}_{m+n}| }[/math].
Hierbei wäre min [math]\displaystyle{ {h}_{m+n+1} }[/math] für [math]\displaystyle{ p^* := p + tv }[/math] mit [math]\displaystyle{ t \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] und [math]\displaystyle{ {v}_{m+n+1} = 0 }[/math] ebenso zu lösen. Folgt min[math]\displaystyle{ {}_{k} {h}_{k} r = 0 }[/math], wird aufgehört, andernfalls wiederholt, bis min [math]\displaystyle{ h = 0 }[/math] oder min [math]\displaystyle{ h > 0 }[/math] feststeht.
Falls erforderlich werden die Restriktionen vorübergehend um einen gleichen kleinen Betrag abgeschwächt. Da fast jeder Durchlauf [math]\displaystyle{ h }[/math] in [math]\displaystyle{ \mathcal{O}({\omega\vartheta}^{2}) }[/math] wenigstens halbiert, liefert der starke Dualitätssatz die Behauptung.[math]\displaystyle{ \square }[/math]