Why is it called the "Simplex" Algorithm/Method?

Question

I have been trying to learn more about the Simplex Algorithm/Method. In particular, I am interested in knowing why this algorithm is called the "Simplex Algorithm".

For instance, when reading the Wikipedia Page (https://en.wikipedia.org/wiki/Simplex_algorithm) : "The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function."

This is a bit confusing for me to understand. Here is what I thought the reason is:

• A "simplex" is a "triangular shaped polygon." Several "simplices" can be combined together to make unique shapes. These are called "simplicial complexes".

• In Linear Programming problems, the objective functions and their constraints form irregular shapes (i.e. a combination of overlapping planes). However, due to the linear nature of these functions and constraints, the resulting shapes will have distinct vertices.

• Thus, the system of objective functions and constraints from a Linear Programming problem form a "simplicial complex."

• In Linear Programming problems, we are interested in optimizing the objective functions relative to some constraints since the system of equations and constraint form a "simplicial complex," we could say that we are interested in optimizing a simplicial complex .

• As a result, the algorithm used for optimizing the simplicial complex is called the "Simplex Algorithm". This algorithm (strategically) "walks around" the vertices of the simplicial complex (corresponding to the system of linear equations and constraints) until it finds the vertex located at the lowest elevation point.

My Question: Can someone please help me understand if I have correctly understood why the Simplex Algorithm is called the "Simplex Algorithm?"

Answer 1

In the open-access paper George B. Dantzig, (2002) Linear Programming. Operations Research 50(1):42-47, the mathematician behind the simplex method writes:

The term simplex method arose out of a discussion with T. Motzkin who felt that the approach that I was using, when viewed in the geometry of the columns, was best described as a movement from one simplex to a neighboring one.

What exactly Motzkin had in mind is anyone's guess, but the interpretation provided by this lecture video of Prof. Craig Tovey (credit to Samarth) is noteworthy. In it, he explains that any finitely bounded problem, $$ \min c^T x\\ Ax = b,\\ 0 \leq x \leq u, $$

can be scaled to $e^T u = 1$ without loss of generality. Then by rewritting all upper bound constraints to equations, $x_j + r_j = u_j$ for slack variables $r_j \geq 0$, we have that the sum of all variables (original and slack) equals $e^T u$ equals one. Hence, all finitely bounded problems can be cast to a formulation of the form $$ \min c^T x\\ Ax = b,\\ e^T x = 1,\\ x \geq 0, $$ where the feasible set is simply described as the set of convex combinations of columns in $A$ that equal $b$. If $A \in \mathbb{R}^{m \times n}$, then a feasible basic solution corresponds to finding $m+1$ columns of $A$ such that the simplex generated by these $m+1$ columns contains $b$. In the simplex method we thus start from a simplex containing $b$ and iterate by moving to a neighboring simplex containing $b$. This sounds a lot like what Motzkin was talking about.

Answer 2

Your explanation is acceptable.

I am giving this from LINEAR PROGRAMMING, 5th Ed. By Saul I Gass. Page 37.

A simplex is an n-dimensional convex polyhedron having exactly n-1 vertices. The boundary of the simplex contains simplices of lower dimension which are called simplicial faces. A simplex in zero dimension is a point; in one dimension it is a line; in two dimensions it is a triangle; and in three dimensions it is a tetrahedron.

also please check the foot note on page 76 of the same book.