Hauptseite
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]