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). The diameter theorem for polytopes is proven. The well-known simplex method is described, together with the strongly polynomial intex method (*int*er-/*ex*trapolation) as fast solution of Smale's 9th problem. We may generalise the intex method to (non-) convex programmes (with vector-valued objective function). It is shown that (mixed) integer LPs are polynomial.

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}}| resp. z = 0 and 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). Otherwise, we 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 to improve the runtime performance, if possible. This will be reversed later. If necessary, renormalise by ||a_{i}||.

We can reduce equal constraints to one of them and remove in each step such with a_{i} ≤ 0, since they are redundant. The second case is analogous. If in both cases b_{i} = 0 and a_{i} ≥ 0 for some i, then the LP has maximum 0 and solution x = 0 if b ≥ 0, otherwise it has no solutions. In each step, for each d_{j} > 0 and non-base variable x_{j}, we select 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)/||x* - x|| resp. d_{j}^{2}/(1 + ||A_{.j}||^{2}) in the k-th constraint. If there are multiple maxima, select max d_{j}b_{k}/a_{kj} according to the rule of best pivot value or alternatively (less well) the smallest angle min Σ 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. This may be collated with the end of the process when checking whether the LP admits any other solutions. 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: The intex method converges linearly and solves every solvable LP in O(mn).

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}}. First, we normscalise b^{T}y - d^{T}x ≤ 0, Ax ≤ b and A^{T}y ≥ d. We compute all scalar products d^{T}a_{i} resp. -d_{j} and sort them. Let v := (x^{T}, y^{T})^{T} ∈ ^{c}ℝ^{m+n}. We start with v := 0 and goal h = 0.

We compute x and analogously y from some equations a_{i}^{T}x = b_{i} resp. x_{j} = 0 with the largest corresponding d^{T}a_{i} resp. -d_{j}. Initial value for the *height* h is the minimum needed for the inequalities to be valid. If x and y are optimal, we stop the procedure. Otherwise, we successively interpolate (a few times) all v_{k}* := (max v_{k} + min v_{k})/2 and extrapolate (v^{T}, h)^{T} through (v*^{T}, h*)^{T} in O(m + n) into the boundary of the polytope if this is beneficial.

When we cannot leave v, we relax all constraints except v ≥ 0 a bit and undo that at the end of one iteration step. If we achieve only slight progress in the interpolation of v* or assume that it is not central, we interpolate again along the progress axis extrapolated on both sides. Since each iteration step in O(mn) processes circa 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 inventory of restrictions 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 paralleled at least as well as the simplex method. 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.⃞

© 2008-2018 by Boris Haase

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