4
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ This is a good explanation: Prof. Craig Tovey explains the column geometry of the simplex method $\endgroup$
    – Samarth
    Feb 14 at 6:59
  • 2
    $\begingroup$ 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$. $\endgroup$
    – YukiJ
    Feb 14 at 7:06

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.