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

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?"

• This is a good explanation: Prof. Craig Tovey explains the column geometry of the simplex method Feb 14 at 6:59
• One remark regarding the statement "however, due to the linear nature of these functions and constraints, the resulting shapes will have distinct vertices.": Vertices need not necessarily exist. For example, consider the problem $\max\{y~|~ x\in \mathbb{R},~y\leq 1\}$. All points $(x,1)$ are optimal and there are no vertices in the feasible region. The feasible region is the half space given by $y\le1$. Feb 14 at 7:06

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.