Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
(Theorem of the month)
(Counter-directional theorem)
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
__NOTOC__
 
= Welcome to MWiki =
 
= Welcome to MWiki =
 
== Theorem of the month ==
 
== Theorem of the month ==
Theorem: The intex method solves every solvable LP in <math>\mathcal{O}({\vartheta}^{3})</math>.
+
=== Counter-directional theorem ===
  
Proof and algorithm: First, we normalise and scale <math>{b}^{T}y - {d}^{T}x \le 0, Ax \le b</math> and <math>{A}^{T}y \ge d</math>. Let the ''height'' <math>h</math> have the initial value <math>{h}_{0} := |\text{min } \{{b}_{1}, ..., {b}_{m}, {-d}_{1}, ..., {-d}_{n}\}|/r</math> for the reduction factor <math>r \in \; [&frac12;, 1[</math>. Let the
+
If the path <math>\gamma: [a, b[ \, \cap \, C \rightarrow V</math> with <math>C \subseteq \mathbb{R}</math> passes the edges of every <math>n</math>-cube of side length d0 in the <math>n</math>-volume <math>V \subseteq {}^{(\omega)}\mathbb{R}^{n}</math> with <math>n \in \mathbb{N}_{\ge 2}</math> exactly once, where the opposite edges in all two-dimensional faces of every <math>n</math>-cube are traversed in reverse direction, but uniformly, then, for <math>D \subseteq \mathbb{R}^{2}, B \subseteq {V}^{2}, f = ({f}_{1}, ..., {f}_{n}): V \rightarrow {}^{(\omega)}\mathbb{R}^{n}, \gamma(t) = x, \gamma(\curvearrowright D t) = \curvearrowright B x</math> and <math>{V}_{\curvearrowright } := \{\curvearrowright B x \in V: x \in V, \curvearrowright B x \ne \curvearrowleft B x\}</math>, it holds that
  
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 - {d}^{T}x \le h, Ax - b \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, d - {A}^{T}y \le (h, ..., h)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{n}\}</math> have for <math>\underline{v} := {v}^{T}</math> the feasible interior starting point <math>v := ({\underline{x}, \underline{y}, h)}^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1}</math>, e.g. <math>({\underline{0}, \underline{0}, {h}_{0})}^{T}</math>.
 
  
It identifies the mutually dual LPs <math>\{{d}^{T}x : d \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}</math> and min <math>\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge d\}</math>.
+
<div style="text-align:center;"><math>\int\limits_{t \in [a,b[ \, \cap \, C}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}(t)dDt}=\int\limits_{\begin{smallmatrix} (x,\curvearrowright B\,x) \\ \in V\times {{V}_{\curvearrowright}} \end{smallmatrix}}{f(x)dBx}=\int\limits_{\begin{smallmatrix} t \in [a,b[ \, \cap \, C, \\ \gamma | {\partial{}^{\acute{n}}} V \end{smallmatrix}}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}(t)dDt}.</math></div>
  
Hereon, we successively interpolate all <math>{v}_{k}^{*} := (\text{max } {v}_{k} + \text{min } {v}_{k})/2</math> until all <math>|\Delta{v}_{k}|</math> are sufficiently small. After that, we extrapolate then <math>v</math> via <math>{v}^{*}</math> into the boundary of the polytope. The <math>r</math>-fold of the distance exceeding <math>{v}^{*}</math> determines the new starting point <math>v</math>.
+
==== Proof: ====
 +
If two arbitrary squares are considered with common edge of length d0 included in one plane, then only the edges of <math>V\times{V}_{\curvearrowright}</math> are not passed in both directions for the same function value. They all, and thus the path to be passed, are exactly contained in <math>{\partial}^{\acute{n}}V.\square</math>
  
If min<math>{}_{k} {h}_{k} t = 0</math> follows from <math>t :=</math> min<math>{}_{k} \Delta{h}_{k}</math>, we end. Then we start over until min <math>h = 0</math> or min <math>h > 0</math> is certain. Since <math>h</math> at least halves itself for each iteration step in <math>\mathcal{O}({\omega\vartheta}^{2})</math>, the strong duality theorem yields the result.<math>\square</math>
+
== Recommended reading ==
 
 
== Recommended readings ==
 
[http://www.epubli.de/shop/buch/Relil-Boris-Haase-9783844208726/11049 Relil - Religion und Lebensweg]
 
  
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
  
 
[[de:Hauptseite]]
 
[[de:Hauptseite]]

Revision as of 05:04, 1 August 2020

Welcome to MWiki

Theorem of the month

Counter-directional theorem

If the path [math]\displaystyle{ \gamma: [a, b[ \, \cap \, C \rightarrow V }[/math] with [math]\displaystyle{ C \subseteq \mathbb{R} }[/math] passes the edges of every [math]\displaystyle{ n }[/math]-cube of side length d0 in the [math]\displaystyle{ n }[/math]-volume [math]\displaystyle{ V \subseteq {}^{(\omega)}\mathbb{R}^{n} }[/math] with [math]\displaystyle{ n \in \mathbb{N}_{\ge 2} }[/math] exactly once, where the opposite edges in all two-dimensional faces of every [math]\displaystyle{ n }[/math]-cube are traversed in reverse direction, but uniformly, then, for [math]\displaystyle{ D \subseteq \mathbb{R}^{2}, B \subseteq {V}^{2}, f = ({f}_{1}, ..., {f}_{n}): V \rightarrow {}^{(\omega)}\mathbb{R}^{n}, \gamma(t) = x, \gamma(\curvearrowright D t) = \curvearrowright B x }[/math] and [math]\displaystyle{ {V}_{\curvearrowright } := \{\curvearrowright B x \in V: x \in V, \curvearrowright B x \ne \curvearrowleft B x\} }[/math], it holds that


[math]\displaystyle{ \int\limits_{t \in [a,b[ \, \cap \, C}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}(t)dDt}=\int\limits_{\begin{smallmatrix} (x,\curvearrowright B\,x) \\ \in V\times {{V}_{\curvearrowright}} \end{smallmatrix}}{f(x)dBx}=\int\limits_{\begin{smallmatrix} t \in [a,b[ \, \cap \, C, \\ \gamma | {\partial{}^{\acute{n}}} V \end{smallmatrix}}{f(\gamma (t)){{{{\gamma }'}}_{\curvearrowright }}(t)dDt}. }[/math]

Proof:

If two arbitrary squares are considered with common edge of length d0 included in one plane, then only the edges of [math]\displaystyle{ V\times{V}_{\curvearrowright} }[/math] are not passed in both directions for the same function value. They all, and thus the path to be passed, are exactly contained in [math]\displaystyle{ {\partial}^{\acute{n}}V.\square }[/math]

Recommended reading

Nonstandard Mathematics