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

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?

• It can be attained at the center of the face. Indeed, it can be attained anywhere on the polytope. Consider for example constant objective functions. But it is always also attained at a vertex. The reason is essentially that a linear function on an interval attains its maximum and minimum at endpoints of the interval. Nov 22 '17 at 22:18
• So is it because the constraints are related to the intersecting hyperplanes? Nov 22 '17 at 22:19
• It's because the objective is linear. Nov 22 '17 at 22:21

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.