Simplex algorithm
|
|
In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. There is also an unrelated method for solving nonlinear programming problems (called the "downhill simplex method" or "Nelder-Mead simplex method", to avoid confusion).
In both cases, the method uses the concept of a simplex, which is a polytope of N + 1 vertices in N dimensions; a line segment on a line, a triangle on a plane, a tetrahedron in three-dimensional space and so forth.
The simplex algorithm in linear programming
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.
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.
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 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.
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.
The simplex algorithm in nonlinear programming
The simplex algorithm finds an optimum solution to a problem with N variables when the solution varies smoothly from one point in the N-dimensional solution space to the neighboring points. For example, a 2-dimensional map showing the elevation of a piece of land or the depth of a pool of oil, or optimizing the outcome of an experiment where many conditions are varied over some known range. With an elevation map, simple inspection shows the answer to the question of the highest elevations; thus illustrating that the usefulness of the simplex method lies in cases where the value at various points is hard to come by, and an exhaustive search is infeasible.
A computer program to use the simplex method to automatically find an optimum typically (1) chooses N + 1 points, (2) finds the values (if unknown) at those points (the elevation, depth, speed, cost, execution time ... whatever is being optimized), (3) stop if we found a good enough value (by any of several criteria), else choose a new point CLOSER TO THE OTHER POINTS (typically by half) in place of the worst valued point (creating a new smaller simplex), (4) go to step (2).
Many variations exist depending on the actual nature of problem being solved. The most common, perhaps, is to use a constant size small simplex that climbs local gradients to local maximums. Visualize a small triangle on an elevation map flip flopping its way up a hill to a local peak.
External links
- An Introduction to Linear Programming and the Simplex Algorithm (http://www.isye.gatech.edu/~spyros/LP/LP.html) by Spyros Reveliotis of the Georgia Institute of Technology.
- Java-based interactive simplex tool (http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/) hosted by Argonne National Laboratory.de:Simplex-Verfahren