Local optimum simplex algorithm

Question

I'm trying to figure out why the simplex algorithm cannot get stuck in a local optimum. It does not check all vertices, but is confident that the vertex it ends at is the global optimum.

I have stumbled upon this and that both giving a short explanation ("Simplex uses a monotonicity property: if a node B has a higher value than $A$, there is a path from $A$ to $B$ such that the value increases at each step. That is why you can never get stuck in a bad local optimum." and "Since linear programming is convex a local minimum will be a global minimum, so any pivoting rule that chooses some improving pivot will lead to an optimal solution.")

However, I'm still struggling to fully comprehend why. What I understand is how a non-convex space could lead to a local optimum but I don't understand why a convex space makes it so that we are SURE not to end up in a local optimum.

Also, does the linearity intervene? Or does it only assure that the optimum is on a vertex.

Thanks!

Answer 1

The general results are:

• When minimizing a convex function over a convex set, every local optimum is always global. The same goes for maximizing a concave function over a convex set.
• When minimizing or maximizing a linear function over a convex set, the same thing holds (because a linear function is both convex and concave).

However, for correctness of the simplex method, we don't need these general results. It comes down to reduced costs.

Suppose for concreteness that we are minimizing a linear objective function $z = \mathbf c^{\mathsf T} \mathbf x$ subject to $A \mathbf x = \mathbf b$ and $\mathbf x \ge \mathbf 0$. As the simplex method works, it rewrites the objective function as $z = z_0 + \mathbf r^{\mathsf T} \mathbf x$ for some reduced costs $\mathbf r$. This is possible because we have a bunch of constraints on $\mathbf x$, so we can express some variables in terms of other variables.

The pivoting rule for the simplex method says that if $r_i < 0$ for some $i$, then we can pivot on $x_i$ and make the objective value even smaller. While we have $r_i < 0$ for any $i$, the simplex method is not done: it has a concrete next step it can do.

However, if $r_i \ge 0$ for all $i$, then (because $x_i \ge 0$ for all $i$ as well) we have $\mathbf r^{\mathsf T} \mathbf x \ge 0$, so $z = z_0 + \mathbf r^{\mathsf T} \mathbf x \ge z_0$. In other words, $z_0$ (the current objective value) is a lower bound for $z$ (the possible objective value at any feasible point). This is exactly the condition for being a global minimum.

Therefore the simplex method can only stop at a global optimum. There are some issues with degeneracy that mean that with some pivoting rules, the simplex method might never stop, and loop forever instead, but that's a separate worry. Simply due to the stopping condition for the simplex method, we ensure that when it's done, it's found the optimal solution.