1
$\begingroup$

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:

enter image description here

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!

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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.

A pivot operation consists in replacing one hyperplane from the basis by another one, while keeping the feasibility. Again this matches with the intuition of traveling along an edge of the polyhedron from one vertex to one of its neighbor.

The pivot operation is not necessarily efficient: one can build polytopes for which it is extremely inefficient (and depending on the implementation, the simplex method may even never terminate). Still it is indeed efficient in practice. This practical efficiency may be explained by the fact that polytopes have a pretty low diameter in general (see for instance the Hirsch conjecture), and most of them are sufficiently regular so that the path followed by the simplex method is not that far from a shortest path. Remember that this all depends on the implementation details of the pivot (that is, which hyperplanes are chosen at each step), and current solvers benefit from years of experimentation and refinements of those details, making them fit to the industrial applications for which they are typically used.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .