Homepage of Boris Haase

Previous | Next

#67: Improvement Linear Optimisation on 04.10.2016

In the following, we concern solving linear programmes (LP). The well-known simplex algorithm and its problems in the worst case is introduced as not strongly polynomial and a method is presented, which leaves fast each problematic multiple vertex. Then, it is opposed to the maximally quadratic and strongly polynomial normal method as solution for the 9th Smale problem.

Theorem: The simplex method is not strongly polynomial.

Proof and algorithm: Let be M := {x ∈ κn : Ax ≤ b, b ∈ κm, A ∈ κm×n, m, n ∈ κℕ*} the feasible domain of the LP max {cTx : c ∈ κn, x ∈ M}. If we dualise it or set x := x+ - x- mit x+, x- ≥ 0, we get x ≥ 0. We solve first max {-z : Ax - ze ≤ b, z ∈ κ≥0} with aim z = 0 and e = (1, ..., 1)Tκm, in order to obtain a feasible x, if b ≥ 0 is not true. We start here with z := |min {b1, ..., bm}| and as in the first case with x := 0. A suitable pivot step achieves b ≥ 0.

Let be i, j, k ∈ κℕ* and aiT the i-th row vector of A. If we have cj ≤ 0 for all j, the LP is solved. If there is a cj > 0 for that we have aij ≤ 0 for all aij, the LP is unbounded. Otherwise, we divide all aiTx ≤ bi by ||ai|| and all cj resp. aij by min |aij| for aij ≠ 0 per j. At the end, we undo the latter. We repeat the normalisation by ||ai||. By this, we achieve a favourable behaviour of the runtime, also for severely deformed polytopes.

We can in each step remove multiple constraints and such with ai ≤ 0, since they are redundant (avoidable with a further slack variable each). All applies analogously to the second case. If we have in both cases bi = 0 and ai ≥ 0 for an i, the LP has the maximum 0 and the solution x = 0, provided we have b ≥ 0, since it otherwise cannot be solved. In each step, we choose for each cj > 0 and non-base variables xj a minimal quotient bk/akj for aij > 0.

The variables with * are the ones of each next step. Then the potential next vertex is given by xj* = xj + bk/akj, with always feasible x*. Choosing steepest edge, the akj is the pivot concerning xj among them that maximises cT(x* - x)/||x* - x|| resp. cj|cj|/(1 + Σ aij2) in the k-th constraint. If we have several maxima, we can use the pivot rule of the best value max cjbk/akj or of the smallest angle min Σ cj*/||c*||, equivalent to that.

If more than n values bi equal 0 and if we cannot maximise the objective function directly, we treat the constraints with bi = 0 are equally by relaxing (perturbing) them by the same, but minimal factor. We need not to note this in the tableau itself: We simply set bi = ||ai||. If a multiple vertex occurs anew, although this is not very likely, we simply add ||ai|| to the bi just stated.

This ensures that the relaxed polytope of the LP alters structurally only minimally, so that we can assume quasi always a simple polytope without multiple vertices. We avoid so to be confronted with several minimal relaxations differing heavily that were, however, not chosen with respect to optimality aspects, as we have using the lexicographic method. Also Bland's rule is not optimal.

The effort to leave a multiple vertex, after what we undo the relaxations left, corresponds to the task to solve a LP with b = 0. This task can also occur finally, when we want to check whether there are further solutions of the LP, if we have at least two cj = 0. The objective function increases (quasi) strictly monotonically on the path passed. Afterwards we can easily calculate cj*, aij* and bi* according to the rectangle rule.

The simplex method cannot prevent an exponential "drifting", since a polytope of the Klee-Minty or Jeroslow type or otherwise can be constructed that deviates immensely form the shortest path, because we are forced to choose in each case the less favourable edge. This is in accordance with existing proofs and it follows the assertion.⃞

Theorem: The normal method solves the LP maximally in O(mn) and is strongly polynomial.

Proof and algorithm: The normal method has the two phases of the simplex method and solves the LP, if possible, by moving in a direction computed from O(n) orthogonal normal directions in the interior of the feasible domain as main step onto the potential maximum. Hereby, we solve all two-dimensional LPs (per direction) in each case by bisection method in O(m). Beginning and treating multiple vertices compare to the simplex method.

We set the height h := cTx and eliminate w. l. o. g. x1 with c1 > 0.. There is a conservative sub-procedure to be executed first for a dome-marginal maximum and an afterwards progressive one for a dome-central one. Then it follows again the conservative sub-procedure and so forth, until the maximum maybe is reached. We solve first the LPs max hj in hj, u ∈ κ≥0 for all j > 1 mit x* := (hj, x2, ..., xj-1, u, xj+1, ..., xn)T and constant xk for 1 ≠ k ≠ j.

We should maybe scale the xj* > 0 to the same minimal value. We set then successively xj := (max xj + min xj)/2, until we could alter all xj crucially. Otherwise, we relax the constraints minimally that x satisfies with equality and compute similarly a favourable direction r ∈ κn, in which we can leave x. We solve thereon again the LPs as above and continue afterwards progressively.

We compute then a favourable direction r ∈ κn with rj := xjhj/max hj. We solve the LP max h in ∈ κ≥0 with x* := x + (v, 0, ..., 0)T + wr ∈ M. If we reach a predefined upper limit of h, we abort the procedure as unlimited. Since all main steps of complexity O(mn) in each case process h almost logarithmically, also to the base of 2, it follows their constant number, and thus the assertion, if the LP can be solved at all.⃞

Corollary: Each linear system (LS) Ax = b with x ∈ κn can be solved, if at all, maximally in O(mn).

Proof: We write Ax = b as Ax ≤ b and -Ax ≤ -b resp. x = x+ - x- with x+, x- ≥ 0.⃞

Theorem: Each convex programme min {f1(x) : x ∈ κn, x ≥ 0, (f2(x), , fm(x))T ≤ 0} with convex posynomials fiκℝ is strongly polynomial and can be solved per normal and Newton's method, which processes the fi, maximally in O(p), if it can be solved at all, p ∈ κℕ* specifies the number of operands xj of the fi and the objective function f1 is linearised.

Proof: The assertion follows from the normal method.⃞

Remarks: The normal method is presently the fastest known LS resp. LP algorithm and numerically very stable, since we alter the initial data hardly. It is also suitable for branch and bound, especially in the non-convex optimisation. We can parallelise the simplex and well the normal method. The transfer to convex programmes with vector-valued or other convex fi is easily possible.

Diameter theorem for polytopes: A d-dimensional polytope given by n restrictions with d, n ∈ κℕ* has a diameter of no more than max(2(n - d), 0).

Proof: Maximally d hyperplanes can build a vertex of a (maybe distorted) cube. If we complete the polytope by adding or cutting with further hyperplanes, we obtain the assertion for the path to be passed and the following theorem, since for the former maximally two further edges emerge in each case. The theorem can be transferred analogously to polyhedra if we only drop the finite constraint.⃞

Prospect: Gomory resp. Lenstra cuts can determine an integer solution of the initially proposed problem in polynomial time, if we presuppose A, b and c w. l. o. g. additionally as integer and m resp. n as fixed. By determining redundant constraints and hyperplanes reached we can establish a full-dimensional LP. Hence, we have refuted that (mixed) integer linear programming is NP complete:

Theorem: (Mixed) integer LPs are polynomial.⃞

code of simplex method and data file example

© 04.10.2016 by Boris Haase

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