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.
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." Combinatorica4,
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. Optimization2,
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." Technometrics4,
441-461, 1962.Tokhomirov, V. M. "The Evolution of Methods
of Convex Optimization." Amer. Math. Monthly103, 65-71, 1996.
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).
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.
