Main Page
Welcome to MWiki
Theorem of the month
The intex method solves every solvable LP in [math]\displaystyle{ \mathcal{O}({\vartheta}^{3}) }[/math].
Proof and algorithm
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 the height [math]\displaystyle{ h }[/math] have the initial value [math]\displaystyle{ h_0 := s |\min \; \{b_1, ..., b_m, -d_1, ..., -d_n\}| }[/math] for the elongation factor [math]\displaystyle{ s \in \, ]1, 2] }[/math].
The 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] has [math]\displaystyle{ k }[/math] constraints and the feasible starting point [math]\displaystyle{ (x_0, y_0, h_0/s)^{T} \in {}^{\omega}\mathbb{R}_{\ge 0}^{m+n+1} }[/math], e.g. [math]\displaystyle{ (0, 0, h_0/s)^{T} }[/math].
It identifies the mutually dual 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].
Let the point [math]\displaystyle{ p := (x, y, h)^T }[/math] approximate the subpolytope’s centre of gravity [math]\displaystyle{ P^* }[/math] as [math]\displaystyle{ p_k^* := (\min p_k + \max p_k)/2 }[/math] until [math]\displaystyle{ {|| \Delta p ||}_{1} }[/math] is sufficiently small. Here [math]\displaystyle{ x }[/math] takes precedence over [math]\displaystyle{ y }[/math]. Then extrapolate [math]\displaystyle{ p }[/math] via [math]\displaystyle{ {p}^{*} }[/math] into [math]\displaystyle{ \partial P^* }[/math] as [math]\displaystyle{ u }[/math]. Put [math]\displaystyle{ p := p^* + (u - p^*)/s }[/math] to shun [math]\displaystyle{ \partial P^* }[/math]. Hereon approximate [math]\displaystyle{ p }[/math] more deeply again as centre of gravity. After optionally solving all LPs min[math]\displaystyle{ {}_{k} {h}_{k} }[/math] by bisection methods for [math]\displaystyle{ {h}_{k} \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] in [math]\displaystyle{ \mathcal{O}({\vartheta}^{2}) }[/math] each time, [math]\displaystyle{ v \in {}^{\omega}\mathbb{R}^{k} }[/math] may be determined such that [math]\displaystyle{ v_k := \Delta{p}_{k} \Delta{h}_{k}/r }[/math] and [math]\displaystyle{ r := }[/math] min[math]\displaystyle{ {}_{k} \Delta{h}_{k} }[/math]. Simplified let [math]\displaystyle{ |\Delta{p}_{1}| = ... = |\Delta{p}_{m+n}| }[/math].
Here min [math]\displaystyle{ {h}_{m+n+1} }[/math] may be solved for [math]\displaystyle{ p^* := p + tv }[/math] where [math]\displaystyle{ t \in {}^{\omega}\mathbb{R}_{\ge 0} }[/math] and [math]\displaystyle{ {v}_{m+n+1} = 0 }[/math]. If min[math]\displaystyle{ {}_{k} {h}_{k} r = 0 }[/math] follows, end, otherwise start over until min [math]\displaystyle{ h = 0 }[/math] or min [math]\displaystyle{ h > 0 }[/math] is certain. If necessary, relax the constraints temporarily by the same small modulus.
Since almost every iteration step in [math]\displaystyle{ \mathcal{O}({\omega\vartheta}^{2}) }[/math] halves [math]\displaystyle{ h }[/math] at least, the strong duality theorem yields the result.[math]\displaystyle{ \square }[/math]