Hauptseite: Unterschied zwischen den Versionen

Aus MWiki
Wechseln zu: Navigation, Suche
(Hauptsätze)
(Intexverfahren)
Zeile 1: Zeile 1:
 
__NOTOC__
 
__NOTOC__
 
= Willkommen bei MWiki =
 
= Willkommen bei MWiki =
−
== Sätze des Monats ==
+
== Satz des Monats ==
−
Erster Hauptsatz der exakten Differential- und Integralrechnung für Kurvenintegrale: Die Funktion <math>F(z)=\int\limits_{\gamma }{f(\zeta )dB\zeta }</math> ist mit <math>\gamma: [d, x[C \rightarrow A \subseteq {}^{(\omega)}\mathbb{K}, C \subseteq \mathbb{R}, f: A \rightarrow {}^{(\omega)}\mathbb{K}, d \in [a, b[C</math>, bei Wahl von <math>\curvearrowright B \gamma(x) = \gamma(\curvearrowright D x)</math>, exakt <math>B</math>-differenzierbar und es gilt für alle <math>x \in [a, b[C</math> und <math>z = \gamma(x)</math>
+
Das Intexverfahren löst jedes lösbare LP in <math>\mathcal{O}({\vartheta}^{3})</math>.
  
−
<div style="text-align:center;"><math>F' \curvearrowright B(z) = f(z).</math></div>
+
== 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>.
  
−
Beweis: <math>dB(F(z))=\int\limits_{t\in [d,x]C}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}D(t)dDt}-\int\limits_{t\in [d,x[C}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}D(t)dDt}=\int\limits_{x}{f(\gamma (t))\frac{\gamma (\curvearrowright Dt)-\gamma (t)}{\curvearrowright Dt-t}dDt}=f(\gamma (x)){{{\gamma }'}_{\curvearrowright }}D(x)dDx=\,f(\gamma (x))(\curvearrowright B\gamma (x)-\gamma (x))=f(z)dBz.\square</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 &gt; 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>
  
−
Zweiter Hauptsatz der exakten Differential- und Integralrechnung für Kurvenintegrale: Gemäß den Voraussetzungen von oben gilt mit <math>\gamma: [a, b[C \rightarrow {}^{(\omega)}\mathbb{K}</math>
+
== Leseempfehlung ==
−
 
 
−
 
 
−
<div style="text-align:center;"><math> F(\gamma (b))-F(\gamma (a))=\int\limits_{\gamma }{{{{{F}'}}_{\curvearrowright }}B(\zeta )dB\zeta }.</math></div>
 
−
 
 
−
 
 
−
Beweis: <math>F(\gamma (b))-F(\gamma (a))=\sum\limits_{t\in [a,b[C}{F(\curvearrowright B\,\gamma (t))}-F(\gamma (t))=\sum\limits_{t\in [a,b[C}{{{{{F}'}}_{\curvearrowright }}B(\gamma (t))(\curvearrowright B\,\gamma (t)-\gamma (t))}=\int\limits_{t\in [a,b[C}{{{{{F}'}}_{\curvearrowright }}B(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}D(t)dDt}=\int\limits_{\gamma }{{{{{F}'}}_{\curvearrowright }}B(\zeta )dB\zeta }.\square</math>
 
−
 
 
−
== Leseempfehlungen ==
 
 
[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]

Leseempfehlung

Nichtstandardmathematik

Abgerufen von „https://de.mwiki.de/index.php?title=Hauptseite&oldid=165“