Convergence, Degeneracy, and the "Dark Side" of the Simplex

The Simplex Algorithm is extremely efficient in practice, but to guarantee that it always reaches the optimal solution (convergence), we must understand what happens when the algorithm encounters geometric and mathematical obstacles.

The Problem of Degeneracy

A basic feasible solution is considered degenerate if at least one of the basic variables has a value of zero.

Geometric cause: It occurs when more constraints than necessary intersect at a vertex, making multiple bases yield the same point. This causes the vertex to have more than one representation as a basic solution.
Consequence: The main danger of degeneracy is cycling. If a tie occurs in the leaving variable, one of the basic variables will have a value 0. This can cause the algorithm to enter an infinite loop, revisiting the same bases repeatedly without progressing toward the optimum.

Cycles, therefore, must be considered when solving linear optimization problems. The first example was proposed by Alan Hoffman in (Hoffman, 1953) with an 11-variable problem where a cycle occurs and Simplex does not converge. Shortly after, Martin Beale proposed an example (Beale, 1955) with 7 variables, shown below:

\[\begin{aligned} \min\;\; & z = -(3/4) x_4 + 20 x_5 -(1/2) x_6 + 6 x_7 \\ \textrm{s. t.}\;\; & x_1 + (1/4)x_4 - 8x_5 - x_6 + 9x_7 = 0 \\ & x_2 + (1/2)x_4 - 12x_5 - (1/2)x_6 + 3x_7 = 0 \\ & x_3 + x_6 = 1 \\ & x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geqslant 0 \end{aligned}\]

The sequence of tableaux shows that the same solution is reached repeatedly, and the Simplex Algorithm enters an infinite cycle:

\[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 0 & 0 & 0 & 3/4 & -20 & 1/2 & -6 & 0 \\ \hline {\color{gray}0} & x_1 & 1 & 0 & 0 & {\color{#2698ba}1/4} & -8 & -1 & 9 & 0 \\ {\color{gray}0} & x_2 & 0 & 1 & 0 & 1/2 & -12 & -1/2 & 3 & 0 \\ {\color{gray}0} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & -3 & 0 & 0 & 0 & 4 & 7/2 & -33 & 0 \\ \hline {\color{gray}{-3/4}} & x_4 & 4 & 0 & 0 & 1 & -32 & -4 & 36 & 0 \\ {\color{gray}0} & x_2 & -2 & 1 & 0 & 0 & {\color{#2698ba}4} & 3/2 & -15 & 0 \\ {\color{gray}0} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & -1 & -1 & 0 & 0 & 0 & 2 & -18 & 0 \\ \hline {\color{gray}{-3/4}} & x_4 & -12 & 8 & 0 & 1 & 0 & {\color{#2698ba}8} & -84 & 0 \\ {\color{gray}{20}} & x_5 & -1/2 & 1/4 & 0 & 0 & 1 & 3/8 & -15/4 & 0 \\ {\color{gray}{0}} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 2 & -3 & 0 & -1/4 & 0 & 0 & 3 & 0 \\ \hline {\color{gray}{-1/2}} & x_6 & -3/2 & 1 & 0 & 1/8 & 0 & 1 & -21/2 & 0 \\ {\color{gray}{20}} & x_5 & 1/16 & -1/8 & 0 & -3/64 & 1 & 0 & {\color{#2698ba}3/16} & 0 \\ {\color{gray}{0}} & x_3 & 3/2 & -1 & 1 & -1/8 & 0 & 0 & 21/2 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 1 & -1 & 0 & 1/2 & -16 & 0 & 0 & 0 \\ \hline {\color{gray}{-1/2}} & x_6 & {\color{#2698ba}2} & -6 & 0 & -5/2 & 56 & 1 & 0 & 0 \\ {\color{gray}{6}} & x_7 & 1/3 & -2/3 & 0 & -1/4 & 16/3 & 0 & 1 & 0 \\ {\color{gray}{0}} & x_3 & -2 & 6 & 1 & 5/2 & -56 & 0 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 0 & 2 & 0 & 7/4 & -44 & -1/2 & 0 & 0 \\ \hline {\color{gray}{0}} & x_1 & 1 & -3 & 0 & -5/4 & 28 & 1/2 & 0 & 0 \\ {\color{gray}{6}} & x_7 & 0 & {\color{#2698ba}1/3} & 0 & 1/6 & -4 & -1/6 & 1 & 0 \\ {\color{gray}{0}} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\]

iterating again, the first tableau reappears.

Ensuring Convergence: Bland’s and Lexicographic Rules

To prevent the algorithm from getting trapped in a cycle, variable selection rules are used:

Lexicographic Rule: Proposed by Abraham Charnes in (Charnes, 1952) and George Dantzig, Alexander Orden, and Philip Wolfe in (Dantzig et al., 1955). If a tie occurs in the leaving variable, the elements of candidate rows are divided by the pivot and compared column by column (starting from the first) to break the tie based on the smallest ratio.

Bland’s Rule: Proposed by Robert Bland in (Bland, 1977). It is simpler: always select the variable with the lowest index to enter or leave the basis when multiple candidates exist. This guarantees mathematically that there will be no cycles and the algorithm will converge.

Using Bland’s rule, the tableaux sequence is as follows, always picking the lowest index variable:

In this tableau, Bland’s rule is applied, entering $x_1$ instead of $x_7$:

Again, Bland’s rule is applied entering $x_2$ instead of $x_4$:

Again, the optimal solution is achieved:

\[(\mathbf{x}^*)^\intercal = (3/4,0,0,1,0,1,0) \quad z^* = -5/4\]

Algorithmic Complexity and Klee-Minty Cubes

Although Simplex is very fast in real problems (usually between $3m$ and $3m^2$ iterations), its theoretical complexity is exponential.

The Klee-Minty Example

In 1972, Victor Klee and George Minty designed an example (Klee & Minty, 1972) (the “Klee-Minty cubes”) to show Simplex’s worst-case scenario. This example illustrates that in the worst case, Simplex may literally traverse every vertex of the polyhedron before finding the optimal solution, something that rarely occurs in real-world problems.

General formulation:

\[\begin{array}{lrcrcrcrcrcr} \max & 2^{n-1} x_1 &+& 2^{n-2} x_2 &+& \ldots &+& 2 x_{n-1} &+& x_n \\ \textrm{s. t.} & x_1 & & & & & & & & & \leqslant & 5 \\ & 2^2 x_1 &+& x_2 & & & & & & & \leqslant & 5^2 \\ & 2^3 x_1 &+& 2^2 x_2 &+& x_3 & & & & & \leqslant & 5^3 \\ & \vdots & & & & & & & & & & \vdots \\ & 2^n x_1 &+& 2^{n-1} x_2 &+& \ldots &+& 2^2 x_{n-1} &+& x_n & \leqslant & 5^n \\ & x_1 &,& x_2 &,& \ldots &,& x_{n-1} &,& x_n & \geqslant & 0 \end{array}\]

Why is it special?

With the standard entering rule, Simplex is forced to visit all vertices. For $n$ variables, this requires $2^n - 1$ iterations.

For $n=2$ (a “deformed” square), the algorithm visits points A(0,0) → B(5,0) → C(5,5) → D(0,25) before finding the optimum. For $n=3$ (a “deformed” cube), all vertices are similarly traversed:

Simplex traversal in Klee-Minty example n=2

Simplex traversal in Klee-Minty example n=3

Summary of Simplex Efficiency

Theoretical Complexity: Exponential (Klee-Minty cases).
Empirical Complexity: Very efficient (linear/quadratic in the number of constraints $m$).
Alternative: Interior Point Methods, introduced by Narendra Karmarkar in (Karmarkar, 1984), solve linear optimization in polynomial time, making them a viable option for large-scale problems where Simplex might face convergence challenges.