Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

Question

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will be attained on some face of the polyhedron, typically a vertex. A vertex is a point determined by the intersection of n hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than n hyerplanes through a vertex. A basis is any subset of bounding hyperplanes that determines a vertex. Some inequalities will be the nonnegativity inequalities, the corresponding variables are called nonbasic and the rest basic. Only the basic variables can take nonzero values.

These are some lecture notes that I'm struggling to understand. Why does the optimal value not lie in say, the center of the polyhedron? Why must the optimal value be on the face or on a vertex? It seems arbitrary to me because there are so many points that lie on the faces. The center makes more sense to me.

Could anyone give me an intuition?

Answer 1

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with radius $\epsilon > 0$ s.t. $B \in int(P)$. Now consider any unit vector say $u \in \mathbb{R}^n$ s.t. $c^t u \neq 0$ (notice that it is always possible to select such a $u$), then both ($x_0 + \epsilon * u$) and ($x_0 - \epsilon * u$) are in $B$, so by extension also in $P$. Now evaluate the function at 3 points, namely $x_0, x_0 + \epsilon * u, x_0 - \epsilon * u$. The objective you would get are-: $c^T x_0 , c^T x_0 + \epsilon (c^T u) , c^T x_0 - \epsilon (c^T u) $. Clearly if since $c^T u \neq 0 $, one of $c^T x_0 + \epsilon (c^T u) , c^T x_0 - \epsilon (c^T u)$ must be lower than $c^T x_0$. This illustrates that the objective at $x_0$ is greater than some other point on the ball, hence $x_0$ cannot be optimum. You can repeat this argument for every other interior point and claim that such an interior point cannot give the optimum. Hopefully this gave you the intuition. More generally, suppose a point $x \in P$, can be represented as convex combination of 2 other points $y, z \in P$, we can repeat the same type of argument and say that the objective at $x$ cannot be strictly lesser than the objectives at both $y$ and $z$. A vertex is an example of a point that cannot be represented as convex combination of 2 other points from the same polyhedron.