Euclidean Geometry • Equitable Distributing • Linear Programming • Set Theory • Nonstandard Analysis • Advice • Topology • Transcendental Numbers • Number Theory • Calculation of Times (Previous | Next)

In the following section, we solve linear programmes (LPs) by the exponential simplex and the polynomial intex method (*int*er-/*ex*trapolation).

Diameter theorem for polytopes: The diameter of an n-dimensional polytope defined by m constraints with m, n ∈ ^{ω}ℕ_{≥2} is at most 2(m + n - 3).

Proof: We can assemble at most m - 1 hyperplanes into an incomplete cycle (of dimension 2) and have to consider n - 2 alternatives sidewards (in the remaining dimensions). Since we can pass each section with a maximum of two edges, the factor is 2. This theorem can be extended to polyhedra analogously by dropping the requirement of finiteness.⃞

Definition: Let ω be the limit, to which all variables in Landau notation tend, and ϑ := ω ln ω. A method is *polynomial* (*exponential*) if its computation time in seconds and (or) its memory consumption in bits is O(ω^{O(1)}) (O(e^{|O(ω|})).

Theorem: The simplex method is exponential.

Proof and algorithm: Let P := {x ∈ ^{ω}ℝ^{n} : Ax ≤ b, b ∈ ^{ω}ℝ^{m}, A ∈ ^{ω}ℝ^{m×n}, m, n ∈ ^{ω}ℕ*} be the feasible domain of the LP max {d^{T}x : d ∈ ^{ω}ℝ^{n}, x ∈ P}. By taking the dual or setting x := x^{+} - x^{-} with x^{+}, x^{-} ≥ 0, we obtain x ≥ 0. We first solve max {-z : Ax - b ≤ (z, …, z)^{T} ∈ ^{ω}ℝ^{m}, z ≥ 0} to obtain a feasible x when b ≥ 0 does not hold. Initial and target value are z := |min {b_{1}, ..., b_{m}}| and z = 0. We begin with x := 0 as in the first case. Pivoting if necessary, we may assume that b ≥ 0.

Let i, j, k ∈ ^{ω}ℕ* and let a_{i}^{T} the i-th row vector of A. If d_{j} ≤ 0 for all j, the LP is solved. If for some d_{j} > 0 (d_{j} = 0), a_{ij} ≤ 0 for all i, the LP is positively unbounded (for now, we may drop d_{j} and A_{.j} as well as b_{i} and a_{i}, but only when a_{ij} < 0 holds). The inequality a_{ij}x_{j} ≥ 0 > b_{i} for all j has no solution, too. If necessary, divide all a_{i}^{T}x ≤ b_{i} by ||a_{i}|| and all d_{j} and a_{ij} by the minimum of |a_{ij}| such that a_{ij} ≠ 0 for each j. This will be reversed later. If necessary, renormalise by ||a_{i}||.

We may always remove redundant constraints (with a_{i} ≤ 0). Select for each d_{j} > 0 and non-base variable x_{j} the minimum ratio b_{k}/a_{kj} for a_{ij} > 0. The variables with * are considered in the next step. The next potential vertex is given by x_{j}* = x_{j} + b_{k}/a_{kj} for feasible x*. To select the steepest edge, select the pivot a_{kj} corresponding to x_{j} that maximises d^{T}Δx/||Δx|| or d_{j}^{2}/(1 + ||A_{.j}||^{2}) for Δx := x* - x in the k-th constraint.

If there are multiple maxima, select max_{k,j} d_{j}b_{k}/a_{kj} according to the rule of best pivot value or alternatively (less well) the smallest angle min Σ_{j} d_{j}*/||d*||. If we cannot directly maximise the objective function, we relax (perturb) the constraints with b_{i} = 0 by the same, minimal modulus. These do not need to be written into the tableau: We simply set b_{i} = ||a_{i}||.

If another multiple vertex is encountered, despite this being unlikely, simply increase the earlier b_{i} by ||a_{i}||. The cost of eliminating a multiple vertex, after which we revert the relaxation, corresponds to an LP with d > 0 and b = 0. Along the chosen path, the objective function increases (effectively) strictly monotonically. We can then simply calculate d_{j}*, a_{ij}* and b_{i}* using the rectangle rule (cf. [775], p. 63).

In the worst-case scenario, the simplex method is not polynomial despite the diameter theorem for polytopes under any given set of pivoting rules, since an exponential "drift" can be constructed with Klee-Minty or Jeroslow polytopes, or others, creating a large deviation from the shortest path by forcing the selection of the least favourable edge. This is consistent with existing proofs. The result follows.⃞

Theorem: The intex method solves every solvable LP in O(ϑ^{3}).

Proof and algorithm: We compute the LP min {h ∈ ^{ω}ℝ_{≥0} : b^{T}y - d^{T}x ≤ h, 0 ≤ x ∈ ^{ω}ℝ^{n}, 0 ≤ y ∈ ^{ω}ℝ^{m}, Ax - b ≤ (h, …, h)^{T} ∈ ^{ω}ℝ^{m}, d - A^{T}y ≤ (h, …, h)^{T} ∈ ^{ω}ℝ^{n}} via the (dual) programme min {b^{T}y : 0 ≤ y ∈ ^{ω}ℝ^{m}, A^{T}y ≥ d} for the (primal) programme max {d^{T}x : d ∈ ^{ω}ℝ^{n}, x ∈ P_{≥0}}. Let v := (x^{T}, y^{T})^{T} ∈ ^{ω}ℝ^{m+n} and the goal for the *height* h let 0. We normalise and scale b^{T}y - d^{T}x ≤ 0, Ax ≤ b and A^{T}y ≥ d. We sort all scalar products d^{T}a_{i}, -d_{j}, b^{T}A_{.j} and b_{i}.

We compute x and analogously y from some equations a_{i}^{T}x = b_{i} or x_{j} = 0 with the largest corresponding d^{T}a_{i} or -d_{j}. Initial value for h is the minimum needed for the inequalities to be valid. We successively interpolate all v_{k}* := (max v_{k} + min v_{k})/2 (a few times) and determine the direction u ∈ ^{ω}ℝ^{m+n} for u_{k} := Δv_{k} Δh_{k}/min Δh_{k}, after solving all LPs min h_{k} in h_{k}, v_{k} ∈ ^{ω}ℝ_{≥0}. We solve min h in h, s ∈ ^{ω}ℝ_{≥0} for v* := v + su and fix v.

The bisection method solves the two-dimensional LPs in O(ϑ^{2}). After interpolating anew, we extrapolate in O(ωϑ) (v^{T}, h)^{T} through (v*^{T}, h*)^{T} into the boundary of the polytope. We compute (approaching the optimum) h as the minimum of all b_{i} - a_{i}^{T}x, A_{.j}^{T}y - d_{j} and d^{T}x - b^{T}y. By the bisection method, we solve the two-dimensional LP min h in h, t ∈ ^{ω}ℝ_{≥0} for v* := v + tr, r^{T} ∈ {(0^{T}, A_{.j}^{T}), (-a_{i}^{T}, 0^{T}), (-a_{i}^{T}, A_{.j}^{T}), (d^{T}, -b^{T})} and fix v in O(ϑ^{2}), too.

We may be able to do without the two-dimensional LPs. If x and y are optimal or if h cannot be minimised anymore, we stop the procedure. When we cannot leave v, we relax all constraints except v ≥ 0 a bit and undo that at the end of one iteration step. Since Δh is for each iteration step in O(ωϑ^{2}) roughly half of h, the claim follows by the strong duality theorem ([775], p. 60 - 65).⃞

Remarks: Simplex method and face algorithm ([916], p. 580 f.) may solve the LP faster for small m and n. We can easily change the current stock of constraints or variables, because the intex method is a non-transforming method and faster than all known (worst-case) LP-solving algorithms in O(ϑω^{3.5}). We simply have to adjust h if necessary, because we can initialise additional variables with 0.

Corollary: Every solvable linear system (LS) Ax = b for x ∈ ^{ω}ℝ^{n} can be solved in O(ϑ^{3}) if we write it as LP min {h ∈ ^{ω}ℝ_{≥0} : ±(Ax - b) ≤ (h, …, h)^{T} ∈ ^{ω}ℝ^{m}}.⃞

Corollary: Every solvable LP min {h ∈ ^{ω}ℝ_{≥0} : ±(Ax - λx) ≤ (h, …, h)^{T} ∈ ^{ω}ℝ^{n}} can determine an eigenvector x ∈ ^{ω}ℝ^{n} \ {0} of the matrix A ∈ ^{ω}ℝ^{n×n} for the eigenvalue λ ∈ ^{ω}ℝ in O(ϑ^{3}).⃞

Corollary: Let α_{j} the j-th column vector of the matrix A^{-1} ∈ ^{ω}ℝ^{n×n} and let δ_{ij} the Kronecker delta. Every LS Aα_{j} = (δ_{1j}, ..., δ_{nj})^{T} to determine the inverse A^{-1} of the regular matrix A can be solved for j = 1, ..., n in O(ϑ^{3}). Whether A is regular can be also determined in O(ϑ^{3}).⃞

Remarks: The three corollaries can be easily transferred to complex ones. The intex method is numerically very stable, since the initial data are only a little altered, and can be solved if modified by distributed computing in O(1). It may also be applied to (mixed) integer problems and branch-and-bound, in particular for nonconvex optimisation. It can easily be extended to convex programmes (with a vector-valued objective function f_{1}):

Corollary: Every solvable convex programme min {f_{1}(x) : x ∈ ^{ω}ℝ^{n}, (f_{2}(x), …, f_{m}(x))^{T} ≤ 0} where the f_{i} ∈ ^{ω}ℝ are convex functions is strongly polynomial and may be solved by the intex method and two-dimensional bisection or Newton's methods in polynomial runtime, if the number of operands x_{j} of the f_{i} is ≤ ω^{ć-2} and if an x exists so that f_{i}(x) < 0 for all i > 1 (see [939], p. 589 ff.).⃞

© 2008-2018 by Boris Haase

• disclaimer • mail@boris-haase.de • pdf-version • bibliography • subjects • definitions • statistics • php-code • rss-feed • top