Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
(Gelfond-Schneider, Three-Cube and Fickett's Theorem)
(Intex method)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
 
= Welcome to MWiki =
 
= Welcome to MWiki =
−
== Theorems of the month ==
+
== Theorem of the month ==
−
=== Gelfond-Schneider theorem ===
+
Intex methods solve almost every solvable LP with <em>int</em>er-/<em>ex</em>trapolations in <math>\mathcal{O}({\vartheta}^3)</math>.
−
It holds <math>a^b \in {}^{\omega} \mathbb{T}_\mathbb{C}</math> where <math>a, c \in {}^{\omega} \mathbb{A}_\mathbb{C}^{*} \setminus \{1\}, Q :=  {}^{\omega} \mathbb{R} \setminus {}^{\omega} \mathbb{T}_\mathbb{R}</math> and <math>b, \varepsilon \in {}^{\omega} \mathbb{A}_\mathbb{C} \setminus Q</math>.
 
  
−
==== Proof: ====
+
== Proof and algorithm ==
−
Where <math>b \in Q</math> puts the minimal polynomial <math>p(a^b) = p(c^q) = 0</math>, assuming <math>a^b = c^{q+\varepsilon}</math> for maximum <math>q \in Q_{&gt;0}</math> leads to the contradiction <math>0 = (p(a^b) - p(c^q)) / (a^b - c^q) = p^\prime(a^b) = p^\prime(c^q) \ne 0.\square</math>
+
Let <math>z := m + n</math> and <math>d \in [0, 1]</math> the density of <math>A</math>. First, normalise and scale <math>{b}^{T}y - {c}^{T}x \le 0, Ax \le b</math> as well as <math>{A}^{T}y \ge c</math>. Let <math>P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y - {c}^{T}x \le r \in [0, \rho], Ax - b \le r{\upharpoonright}_m,</math> <math>c - {A}^{T}y \le r{\upharpoonright}_n\}</math> have the radius <math>\rho := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}|</math> and the scaling factor <math>s \in [1, 2]</math>.
  
−
=== Three-Cube Theorem ===
 
  
−
Three-cube theorem: It holds <math>S := \{n \in \mathbb{Z} : n \ne \pm 4\mod 9\} = \{n \in \mathbb{Z} : n = a^3 + b^3 + c^3 + 3(a + b)c(a - b + c) = (a + c)^3 + (b - c)^3 + c^3\} \subset a^3 + b^3 + c^3 + 6{\mathbb{Z}}</math>, since independent mathematical induction by equitable variables <math>a, b, c \in {\mathbb{Z}}</math> first shows <math>\{0, \pm 1, \pm 2, \pm 3\} \subset S</math>, and then the claim.<math>\square</math>
+
It follows <math>0{\upharpoonright}_z \in \partial P_{\rho}</math>. By the strong duality theorem, LP min <math>\{ r \in [0, \rho] : (x, y)^T \in P_r\}</math> solves LPs max <math>\{{c}^{T}x : c \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 c\}</math>. Its solution is the geometric centre <math>g</math> of the polytope <math>P_0</math>. For <math>p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k</math> and <math>k = 1, ..., \grave{z}</math> approximate <math>g</math> by <math>p_0 := (x_0, y_0, r_0)^T</math> until <math>||\Delta p||_1</math> is sufficiently small. The solution <math>t^o(x^o, y^o, r^o)^T</math> of the two-dimensional \ac{lp} min <math>\{ r \in [0, \rho] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\}</math> approximates <math>g</math> better and achieves <math>r \le \check{\rho}</math>.
  
−
=== Fickett's Theorem ===
 
  
−
For any relative positions of two overlapping congruent rectangular <math>n</math>-prisms <math>Q</math> and <math>R</math> with <math>n \in {}^{\omega }\mathbb{N}_{\ge 2}</math> and <math>\grave{m} := \hat{n}</math>, the exact standard measure <math>\mu</math> implies, where <math>\mu</math> for <math>n = 2</math> is the Euclidean path length <math>A</math>:
+
Repeat this for <math>t^o(x^o, y^o)^T</math> until <math>g \in P_0</math> is computed in <math>\mathcal{O}({}_2\rho^2dmn)</math> if it exists. Solving all two-dimensional LPs <math>\text{min}_k r_k</math> by bisection methods for <math>r_k \in {}^{\omega}\mathbb{R}_{\ge 0}</math> and <math>k = 1, ..., z</math> in <math>\mathcal{O}({\vartheta}^2)</math> each time determines <math>q \in {}^{\omega}\mathbb{R}^k</math> where <math>q_k := \Delta p_k \Delta r_k/r</math> and <math>r := \text{min}_k \Delta r_k</math>. Let simplified <math>|\Delta p_1| = ... = |\Delta p_{z}|</math>. Here min <math>r_{\grave{z}}</math> for <math>p^* := p + wq</math> and <math>w \in {}^{\omega}\mathbb{R}_{\ge 0}</math> may be solved, too. If <math>\text{min}_k \Delta r_k r = 0</math> follows, stop computing, otherwise repeat until min <math>r = 0</math> or min <math>r &gt; 0</math> is sure.<math>\square</math>
−
 
 
−
<div style="text-align:center;"><math>\tilde{m} &lt; r := \mu(\partial Q \cap R)/\mu(\partial R \cap Q) &lt; m.</math></div>
 
−
 
 
−
==== Proof: ====
 
−
The underlying extremal problem has its maximum for rectangles with side lengths <math>s</math> and <math>s + \hat{\iota}</math>. Putting <math>q := 3 - \hat{\iota}\tilde{s}</math> implies min <math>r = \tilde{q} \le r \le</math> max <math>r = q</math>. The proof for <math>n &gt; 2</math> works analogously.<math>\square</math>
 
−
 
 
−
== Recommended reading ==
 
  
 +
== Recommended readings ==
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
 
[https://en.calameo.com/books/003777977258f7b4aa332 Nonstandard Mathematics]
  
 
[[de:Hauptseite]]
 
[[de:Hauptseite]]

Revision as of 00:53, 1 December 2023

Welcome to MWiki

Theorem of the month

Intex methods solve almost every solvable LP with inter-/extrapolations in [math]\displaystyle{ \mathcal{O}({\vartheta}^3) }[/math].

Proof and algorithm

Let [math]\displaystyle{ z := m + n }[/math] and [math]\displaystyle{ d \in [0, 1] }[/math] the density of [math]\displaystyle{ A }[/math]. First, normalise and scale [math]\displaystyle{ {b}^{T}y - {c}^{T}x \le 0, Ax \le b }[/math] as well as [math]\displaystyle{ {A}^{T}y \ge c }[/math]. Let [math]\displaystyle{ P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y - {c}^{T}x \le r \in [0, \rho], Ax - b \le r{\upharpoonright}_m, }[/math] [math]\displaystyle{ c - {A}^{T}y \le r{\upharpoonright}_n\} }[/math] have the radius [math]\displaystyle{ \rho := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}| }[/math] and the scaling factor [math]\displaystyle{ s \in [1, 2] }[/math].


It follows [math]\displaystyle{ 0{\upharpoonright}_z \in \partial P_{\rho} }[/math]. By the strong duality theorem, LP min [math]\displaystyle{ \{ r \in [0, \rho] : (x, y)^T \in P_r\} }[/math] solves LPs max [math]\displaystyle{ \{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\} }[/math] and min [math]\displaystyle{ \{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\} }[/math]. Its solution is the geometric centre [math]\displaystyle{ g }[/math] of the polytope [math]\displaystyle{ P_0 }[/math]. For [math]\displaystyle{ p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k }[/math] and [math]\displaystyle{ k = 1, ..., \grave{z} }[/math] approximate [math]\displaystyle{ g }[/math] by [math]\displaystyle{ p_0 := (x_0, y_0, r_0)^T }[/math] until [math]\displaystyle{ ||\Delta p||_1 }[/math] is sufficiently small. The solution [math]\displaystyle{ t^o(x^o, y^o, r^o)^T }[/math] of the two-dimensional \ac{lp} min [math]\displaystyle{ \{ r \in [0, \rho] : t \in {}^{\omega}\mathbb{R}_{\gt 0}, t(x_0, y_0)^T \in P_r\} }[/math] approximates [math]\displaystyle{ g }[/math] better and achieves [math]\displaystyle{ r \le \check{\rho} }[/math].


Repeat this for [math]\displaystyle{ t^o(x^o, y^o)^T }[/math] until [math]\displaystyle{ g \in P_0 }[/math] is computed in [math]\displaystyle{ \mathcal{O}({}_2\rho^2dmn) }[/math] if it exists. Solving all two-dimensional LPs [math]\displaystyle{ \text{min}_k r_k }[/math] by bisection methods for [math]\displaystyle{ r_k \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] and [math]\displaystyle{ k = 1, ..., z }[/math] in [math]\displaystyle{ \mathcal{O}({\vartheta}^2) }[/math] each time determines [math]\displaystyle{ q \in {}^{\omega}\mathbb{R}^k }[/math] where [math]\displaystyle{ q_k := \Delta p_k \Delta r_k/r }[/math] and [math]\displaystyle{ r := \text{min}_k \Delta r_k }[/math]. Let simplified [math]\displaystyle{ |\Delta p_1| = ... = |\Delta p_{z}| }[/math]. Here min [math]\displaystyle{ r_{\grave{z}} }[/math] for [math]\displaystyle{ p^* := p + wq }[/math] and [math]\displaystyle{ w \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] may be solved, too. If [math]\displaystyle{ \text{min}_k \Delta r_k r = 0 }[/math] follows, stop computing, otherwise repeat until min [math]\displaystyle{ r = 0 }[/math] or min [math]\displaystyle{ r > 0 }[/math] is sure.[math]\displaystyle{ \square }[/math]

Recommended readings

Nonstandard Mathematics

Retrieved from "https://en.mwiki.de/index.php?title=Main_Page&oldid=288"