In the following section, we solve linear programmes (LPs) by the simplex and the intex method (*int*er-/*ex*trapolation) as strongly polynomial solution to Smale's 9th problem.

Diameter theorem for polytopes: The diameter of an n-dimensional polytope defined by m constraints with m, n ∈ ^{c}ℕ_{≥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.⃞

Theorem: The simplex method is not strongly polynomial.

Proof and algorithm: Let P := {x ∈ ^{c}ℝ^{n} : Ax ≤ b, b ∈ ^{c}ℝ^{m}, A ∈ ^{c}ℝ^{m×n}, m, n ∈ ^{c}ℕ*} be the feasible domain of the LP max {d^{T}x : d ∈ ^{c}ℝ^{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} ∈ ^{c}ℝ^{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 ∈ ^{c}ℕ* 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 strongly 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: Let wlog η := max_{i,j} {-b_{i}, d_{j}} > 0. The intex method solves every solvable LP in O(mn) ≤ mnqh/Δh for a small q ∈ ^{c}ℕ* and a *height* h ∈ ]0, η].

Proof and algorithm: We compute the LP min {h ∈ ^{c}ℝ_{≥0} : b^{T}y - d^{T}x ≤ h, 0 ≤ x ∈ ^{c}ℝ^{n}, 0 ≤ y ∈ ^{c}ℝ^{m}, Ax - b ≤ (h, …, h)^{T} ∈ ^{c}ℝ^{m}, d - A^{T}y ≤ (h, …, h)^{T} ∈ ^{c}ℝ^{n}} via the (dual) programme min {b^{T}y : 0 ≤ y ∈ ^{c}ℝ^{m}, A^{T}y ≥ d} for the (primal) programme max {d^{T}x : d ∈ ^{c}ℝ^{n}, x ∈ P_{≥0}}. Let v := (x^{T}, y^{T})^{T} ∈ ^{c}ℝ^{m+n} and goal h = 0. The case η ≤ 0 is solved by v := 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 ∈ ^{c}ℝ^{m+n} for u_{k} := Δv_{k} Δh_{k}/min Δh_{k}, after solving all LPs min h_{k} in h_{k}, v_{k} ∈ ^{c}ℝ_{≥0}. We solve min h in h, s ∈ ^{c}ℝ_{≥0} for v* := v + su and fix v.

The bisection method solves the two-dimensional LPs in O(mn) and O(m + n). After interpolating anew, we extrapolate (v^{T}, h)^{T} through (v*^{T}, h*)^{T} in O(m + n) 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 ∈ ^{c}ℝ_{≥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(m + n), 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(mn) fix (!) or even more than 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 an LP faster for small m and n. We can easily change the current stock of constraints or variables, because the intex method is one of the non-transforming methods and currently the fastest known (worst-case) LP-solving algorithm. 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 ∈ ^{c}ℝ^{n} can be solved in O(mn) if we write it as LP min {h ∈ ^{c}ℝ_{≥0} : ±(Ax - b) ≤ (h, …, h)^{T} ∈ ^{c}ℝ^{m}}.⃞

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

Corollary: Let α_{j} the j-th column vector of the matrix A^{-1} ∈ ^{c}ℝ^{n×n} and let δ_{ij} the Kronecker delta. Then 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(n^{2}). Whether A is regular can be also determined in O(n^{2}).⃞

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 ∈ ^{c}ℝ^{n}, (f_{2}(x), …, f_{m}(x))^{T} ≤ 0} where the f_{i} ∈ ^{c}ℝ are convex functions is strongly polynomial and may be solved by the intex method and two-dimensional bisection or Newton's methods, which handle the f_{i} in O(p), where p ∈ ^{c}ℕ* denotes the number of operands x_{j} of the f_{i}, assuming that an x exists so that f_{i}(x) < 0 for all i > 1 (see [939], p. 589 ff.).⃞

Further thoughts: Gomory or Lenstra cuts can find an integer solution of the original problem in polynomial time if we additionally assume that A, b, and d are integers wlog and that m and n are fixed. By dualising, a full-dimensional LP may be obtained as described before within the intex method. This shows that the problem of (mixed) integer linear programming is not NP-complete:

Theorem: (Mixed) integer LPs may be solved in polynomial time.⃞

© 14.07.2018 by Boris Haase

• privacy policy • disclaimer • pdf-version • bibliography • subjects • definitions • statistics • php-code • rss-feed • mwiki • top