# Understanding the "Simplex Algorithm" in Linear Programming: Algebra vs Geometry

The (famous) Simplex Algorithm in Linear Programming is meant for optimizing a system of linear equations and linear constraints. We are told that the Simplex Algorithm "scans" different vertices on the exterior surface (this surface corresponds to the "feasible region" and is called a "simplicial complex") made by the intersection of all equations and constraints - and gradually moves towards the vertex containing the true minimum. Supposedly, the Simplex Algorithm works remarkably well for such types of linear problems, even in high dimensions.

When we are shown how to use the Simplex Algorithm for small examples, we are shown that a "pivot" operations are iteratively required to navigate the vertices of the "simplicial complex" until the minimum is reached:

My Question: Why does the algebra of the "pivot operation" correspond to "navigating the vertices of the simplicial complex"? And is there any reason that the "pivot operation" is so effective at finding the minimum vertex and almost guaranteed to converge?

Thanks!

A linear program is defined as a linear system of inequalities plus a linear form to optimize. Each inequality $$ax \leq b$$ is geometrically a half-space on a side of the hyperplane $$ax = b$$. A linear system of inequalities is thus the same as a polyhedron. Optimizing a linear form on this polyhedron $$P$$, that is finding $$x \in P$$ with $$cx$$ maximum, is the same as trying to find a point as far as possible in the direction given by $$c$$. When $$P$$ is a polytope (or for some weaker conditions too), the intuition that the maximum is reached at a vertex of $$P$$ is true (this is not necessary the case when $$P$$ contains a subspace orthogonal to $$c$$ for instance).
The simplex method is to start from a basic feasible solution $$x$$, and iterate through better basic feasible solutions until reaching an optimal solution. Feasible means that $$x \in P$$. Basic means that $$x$$ can be described by the intersection of $$d$$ independant hyperplanes (the basis) from the linear system of inequalities. If you think about it, you may realize that basic + feasible is just the same as being a vertex.