Simplex algorithm

In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. A variation commonly used in nonlinear regression programs is the Nelder-Mead method or Simplex method or downhill simplex method due to Nelder & Mead (1965) and is a numerical method for solving many-dimensional problems, belonging to the more general class of search algorithms.

Description

A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized). Some further details are given in the linear programming article.

Related Topics:
Linear - Real - Variable

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In geometric terms we are considering a closed convex polytope P, defined by intersecting a number of half-spaces in n-dimensional Euclidean space, which lie to one side of a hyperplane. The objective is to maximise a linear functional L; if we consider the hyperplanes H(c) defined by L(x) = c as c increases, these form a parallel family. If the problem is well-posed, we want to find the largest value of c such that H(c) intersects P (if there is no such largest value of c, this isn't a reasonable question for optimization as it stands). In this case we can show that the optimum value of c is attained, on the boundary of P. Methods for finding this optimum point on P have a choice of improving a possible point by moving through the interior of P (so-called interior point methods), or starting and remaining on the boundary.

Related Topics:
Closed - Convex - Euclidean space - Hyperplane

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The simplex algorithm falls into the latter class of method. The idea is to move along the facets of P in search of the optimum, from point to point. Note that the optimum cannot occur at a mid-point, for example in the middle of an edge lying as a line segment on the boundary of P, unless the whole relevant 'face' is parallel to H. Therefore it is possible to look solely at moves skirting the edge of a simplex, ignoring the interior. The algorithm specifies how this is to be done.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We start at some vertex of the polytope, and at every iteration we choose an adjacent vertex such that the value of the objective function does not decrease. If no such vertex exists, we have found a solution to the problem. But usually, such an adjacent vertex is nonunique, and a pivot rule must be specified to determine which vertex to pick. Various pivot rules exist.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In 1972, Klee and Minty{{rf|1|Greenberg}} gave an example of a linear programming problem in which the polytope P is a distortion of an n-dimensional cube. They showed that the simplex method as formulated by Dantzig visits all 2n vertices before arriving at the optimal vertex. This shows that the worst-case complexity of the algorithm is exponential time. Similar examples have been found for other pivot rules. It is an open question if there is a pivot rule with polynomial time worst-case complexity.

Related Topics:
1972 - Exponential time - Polynomial time

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Nevertheless, the simplex method is remarkably efficient in practice. Attempts to explain this employ the notion of average complexity or (recently) smoothed complexity.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Other algorithms for solving linear programming problems are described in the linear programming article.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~