A 1965 Linear Programming Algorithm Runs In Polynomial Time^{∗}

Boris Yamnitsky and Leonid A. Levin^{†}

Abstract

The Ellipsoid Algorithm (EA) for linear programming has recently attracted great attention. EA was proposed in [5] and developed in [1,2] and other works. It is a modification of the Method of Centralized Splitting proposed in [3], which differs from EA in two essential aspects. Firstly, [3] uses simplexes instead of ellipsoids; it is admitted, secondly, that several, q(n), splittings of the n-dimensional simplex may be needed before the remaining polyhedron can be enclosed into a simplex of a smaller volume. Only a very rough upper bound q(n) < n log n follows from the reasoning of [3]. This does not imply polynomiality of the computation time, since n log n splittings may make the simplex very complex. We prove below that q(n) = 1.

Without loss of generality, let the problem be to find x ∈ ℜ^{n} such that Ax > 0, where A is an m × n matrix of rank n. We normalize the solutions by restricting x throughout to a hyperplane (e · Ax) = 1 where e > 0. On every step the algorithm considers a simplex BAx ≥ 0, where B is a non-negative n × m matrix with det(BA) ≠ 0. Any such simplex necessarily contains all solutions. Let us denote this simplex by Δ_{B}, its volume by V_{B} and its center by c_{B}. Initially we take an arbitrary B and e = (1, .., 1)B.

Theorem 1 Either Ac_{B} > 0 or by increasing one of the entries of B one can decrease ln V_{B} by > 1/2n^{2}.

The new simplex contains the half {x : (A_{i}· x) ≥ 0 ≥ (A_{i} · c_{B})} of the old one.

The proof is based on a geometric idea from [4], which is the contribution of B. Yamnitsky. The gain in − ln V_{B} after one central splitting varies between 1 and 1/2n^{2}, in some contrast to the constant 1/2n gain in EA. The gain is > 1/2n if the splitting (a · x) ≥ 0 is random with probability distributed symmetrically over reflection: a → −a. B. Yamnitsky noted that simplexes or ellipsoids can not be replaced by an arbitrary convex body. Namely, a triangular half of a parallelogram can not be enclosed in a parallelogram of a smaller volume.

The Theorem provides a step of DM (Dual Matrix or Simplex Splitting?) algorithm. It has not only historical interest. Being worse case polynomial, like EM, it also shares an important advantage with Dantzig’s Simplex Method (SM). SM is a “climbing” algorithm, i.e. it has an easy computable rating (the purpose functional F) of intermediate results (nodes x of the polyhedron). The algorithm’s step is expected (unfortunately not guaranteed) to improve F (x) quickly. EM is not a “climbing” algorithm, since its intermediate results (small ellipsoids, containing all solutions) are hard to evaluate: it is difficult to check whether an ellipsoid contains all solutions. So non-standard or just nonprecise transformations may produce an ellipsoid unrelated to the set of solutions. But DM is “climbing”, since Δ_{B} contains all solutions for any non-negative B. This makes DM stable and flexible (any transformation of B works, if V_{B} decreases substantially) and, hopefully, well adjustable for important special cases.

∗Supported by BU, MIT and NSF grant # MCS-8104211.

†Boston University, Department of Mathematics, Boston, MA 02215

Construction: Let a = A_{i}, where (A_{i} · c_{B}) ≤ 0, and d_{j} be a simplex vertex with maximal (a · d_{k}). Let B_{j}Ax = 0 be the equation of the simplex side opposite to d_{j} and b = B_{j}A.

Then, increasing B_{j,i} by t = (b · d_{j})/(a · d_{j})(n^{2} − 2n) will decrease ln V_{B} by > 1/2n^{2}.

Proof: The new simplex Δ_{B′} has only one new face: (b′ · x) = 0, where b′ = b + ta.

The vertex d_{j} and directions of edges (d_{j}, d_{k}) remain unchanged. Lengths of these edges are divided by l_{k} = 1−(b′·d_{k})/(b′·d_{j}). Then V_{B}/V_{B′} = ∏ l_{k}.

We have: (a · d_{j}) = max_{k}(a · d_{k}) > 0; (a·c_{B}) ≤ 0; c_{B} = ∑ d_{k}/n; (b·d_{k})(k− j) = 0.

This implies: min_{k} l_{k} ≥ 1 − 1/(n − 1)^{2} = μ and ∑ l_{k} ≥ n − μ.

Consequently, ∏ l_{k} ≥ μ^{n−2}(n − (n − 1)μ) = μ^{n−1}/(1 − 1/(n − 1)) = λ.

Then ln λ = (n−1) ln μ−ln(1−1/(n−1)) = −(n − 1) ∑_{k=1}^{∞} 1/k(n − 1)^{2k} + ∑_{k=1}^{∞} 1/k(n − 1)^{k} =

∑_{k=3}^{∞}(1/k(n−1)^{k}−1/k(n−1)^{2k−1})+1/2(n− 1)^{2} − 1/2(n − 1)^{3} > 1/2n^{2},

1 Complexity:

Let the numbers n, m, A_{i,j} have at most k decimal digits. If h is a height of a simplex whose faces (or nodes) are given by a square sub-matrix of A then | ln h| is at most O(kn). Thus after at most O(kn^{4}) splittings, the simplex gets so “thin” that it can not contain solutions of the system.

Each splitting takes at most O(nm) arithmetical operations, using nodes of the old simplex. The simplex diameter need not grow substantially (otherwise it can be easily restored with a great volume reduction). Then entries of B need at most O(kn) digits. In total the algorithm takes at most O(k^{3}n^{6}m) Boolean operations.

The authors are deeply grateful to P. Gacs and L. Lovasz for valuable discussions.

References

[1] 1P. Gacs and L. Lovasz, Khachian’s Algorithm for Linear Programming, Math. Programming Studies 14 (1981) 61-68.

[2] 2L.G. Khachian, A Polynomial Algorithm for Linear Programming, Soviet Mathematics, Doklady 20/1 (1979) 191-194.

[3] 3A.Yu. Levin, On an Algorithm for the Minimization of Convex Functions, Soviet Mathematics, Doklady 6 (1965) 286-290.

[4] 4B. Yamnitsky, Notes on Linear Programming, Master’s Thesis Boston University (1982).

[5] 5D.B. Yudin and A.S. Nemirovsky, Informational Complexity and Effective Methods for Solving Convex Extremum Problems, Economica i Mat. Metody12/2 (1976) 128-142, transl. MatEcon13 (1976) 3-25.