A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

ABSTRACT

It has been a challenge for mathematicians to theoretically confirm the extremely good performance of simplex-type algorithms for linear programming. In this paper we analyze the average number of steps performed by a simplex algorithm so-called the self-dual method. Instead of starting the algorithm at the traditional point (1, ..., 1)^T, we use points of the form (1, ε, ε², ...) ^T, with ε sufficiently small. The result that we get is much better, in two respects, than those of the previous analyses. First, we show that the expected number of steps is bounded between two quadratic functions c₁(min(m, n))² and c₂(min(m, n))² of the smaller dimension of the problem. This should be compared with the previous two major results in the field. Borgwardt proves an upper bound of O(n⁴m^1/(n-1)) under a restrictive model which implies that the zero-vector satisfies all the constraints, and also the algorithm under his consideration solves only problems from the particular subclass. Smale analyzes a less restrictive algorithm. He shows that for any fixed m there is a constant c(m) such the expected number of steps is less than c(m)(ln n)^m(m+1); Megiddo has shown that, under Smale's model, an upper-bound C(m) exists. Thus, we prove for the first time a polynomial upper bound with no restrictions (except for non-degeneracy) on the problem, and establish for the first time a nontrivial lower bound of precisely the same order of magnitude. Secondly, our probabilistic model is much less restrictive than the previous ones. Both Borgwardt and Smale require the input vectors to be drawn from spherically

References

1. 1.I. Adler, "The expected number of pivots needed to solve parametric linear programs and the efficiency of the Self-Dual Simplex method", Department of Industrial Engineering and Operations Research, University of California, Berkeley, June 1983.
2. 2.I. Adler and S. E. Berenguer, "Random linear programs", Technical Report ORC 81-4, Operations Research Center, University of California, Berkeley, 1981.
3. 3.I. Adler and S. E. Berenguer, "Duality theory and the random generation of linear programs", manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley, 1981.
4. 4.I. Adler and S. E. Berenguer, "Generating random linear programs", Revised manuscript, Department of Industrial Engineering and Operations Research, University of California, Berkeley (1983); submitted to Mathematical Programming.
5. 5.C. Blair, "Random linear programs with many variables and few constraints", Faculty Working Paper No. 946, College of Commerce and Business Administration, University of Illinois at Urbana-Champaign, April 1983.
6. 6.R. C. Buck, "Partition of Space", American Mathematical Monthly 50 (1943), 541-544.
7. 7.K.-H. Borgwardt, "Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method", Math. of Oper. Res. 7 (1982), 441-462.
8. 8.K.-H. Borgwardt, "The average number of steps required by the simplex method is polynomial", Zeitschrift fur Operations Research 26 (1982) 157-177.
9. 9.G. B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, New Jersey, 1963.
10. 10.M. Haimovich, "The simplex algorithm is very good!—On the expected number of pivot steps and related properties of random linear programs", Columbia University, New York, April 1983.
11. 11.V. Klee and G.J. Minty, "How good is the simplex algorithm?", in Inequalities III, Academic Press, New York, 1972, pp.159-175.
12. 12.J. May and R. Smith, "Random polytopes: Their definition, generation, and aggregate properties", Mathematical Programming 24 (1982) 39-54.
13. 13.C. E. Lemke, "Bimatrix equilibrium points and mathematical programming", Management Science 11 (1965) 681-689.
14. 14.N. Megiddo, "Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm", preliminary report, September 1983.
15. 15.N. Megiddo, "On the expected number of linear complementarity cones intersected by random and semi-random rays", preliminary report, September 1983.
16. 16.K. G. Murty "Computational complexity of parametric linear programming", Mathematical Programming 19 (1980) 213-219.
17. 17.S. Smale, "On the average number of steps of the simplex method of linear programming", Mathematical Programming 27 (1983), to appear.
18. 18.S. Smale, "The problem of the average speed of the simplex method", Proceedings of the 11th International Symposium on Mathematical Programming, Universitat Bonn, August 1982, pp. 530-539.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

      • Continuous optimization

        • Linear programming

    • Numerical analysis

      • Computations on matrices

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Linear programming

  • Models of computation

    • Probabilistic computation