Simplex Method

The simplex method is a method for solving problems in linear programming. This method, invented by George Dantzig in 1947, tests adjacent vertices of the feasible set (which is a polytope) in sequence so that at each new vertex the objective function improves or is unchanged. The simplex method is very efficient in practice, generally taking  to  iterations at most (where  is the number of equality constraints), and converging in expected polynomial time for certain distributions of random inputs (Nocedal and Wright 1999, Forsgren 2002). However, its worst-case complexity is exponential, as can be demonstrated with carefully constructed examples (Klee and Minty 1972).

A different type of methods for linear programming problems are interior point methods, whose complexity is polynomial for both average and worst case. These methods construct a sequence of strictly feasible points (i.e., lying in the interior of the polytope but never on its boundary) that converges to the solution. Research on interior point methods was spurred by a paper from Karmarkar (1984). In practice, one of the best interior-point methods is the predictor-corrector method of Mehrotra (1992), which is competitive with the simplex method, particularly for large-scale problems.

Dantzig's simplex method should not be confused with the downhill simplex method (Spendley 1962, Nelder and Mead 1965, Press et al. 1992). The latter method solves an unconstrained minimization problem in  dimensions by maintaining at each iteration  points that define a simplex. At each iteration, this simplex is updated by applying certain transformations to it so that it "rolls downhill" until it finds a minimum.

REFERENCES:

Dantzig, G. B. Linear Programming and Extensions. Princeton, NJ: Princeton University Press, 1963.

Forsgren, A.; Gill, P. E.; and Wright, M. H. "Interior Methods for Nonlinear Optimization." SIAM Rev. 44, 525-597, 2002.

Karmarkar, N. "A New Polynomial-time Algorithm for Linear Programming." Combinatorica 4, 373-395, 1984.

Klee, V.; Minty, G. J.; and Shisha, O. (Eds.). "How Good is the Simplex Algorithm?" In Inequalities 3. New York: Academic Press, 159-175, 1972.

Mehrotra, S. "On the Implementation of a Primal-dual Interior Point Method." SIAM J. Optimization 2, 575-601, 1992.

Nelder, J. A. and Mead, R. "A Simplex Method for Function Minimization." Comp. J. 7, 308-313, 1965.

Nemirovsky, A. and Yudin, N. Interior-Point Polynomial Methods in Convex Programming. Philadelphia, PA: SIAM, 1994.

Nocedal, J. and Wright, S. J. Numerical Optimization. New York: Springer-Verlag, 1999.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Downhill Simplex Method in Multidimensions" and "Linear Programming and the Simplex Method." §10.4 and 10.8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 402-406 and 423-436, 1992.

Spendley, W.; Hext, G. R.; and Himsworth, F. R. "Sequential Application of Simplex Designs in Optimization and Evolutionary Operation." Technometrics 4, 441-461, 1962.

Tokhomirov, V. M. "The Evolution of Methods of Convex Optimization." Amer. Math. Monthly 103, 65-71, 1996.