Fundamental theorem of linear programming

In applied mathematics, the fundamental theorem of linear programming, in a weak formulation, states that the maxima and minima of a linear function over a convex polygonal region occur at the region's corners. Further, if an extreme value occurs at two corners, then it must also occur everywhere on the line segment between them.

Statement

Consider the optimization problem

\min c^{T}x{\text{ subject to }}x\in P

Where $P=\{x\in \mathbb {R} ^{n}:Ax\leq b\}$ . If $P$ is a bounded polyhedron (and thus a polytope) and $x^{*}$ is an optimal solution to the problem, then $x^{*}$ is either an extreme point (vertex) of $P$ , or lies on a face $F\subset P$ of optimal solutions.

Proof

Suppose, for the sake of contradiction, that $x^{*}\in \mathrm {int} (P)$ , then there exists some $\epsilon >0$ such that the ball of radius $\epsilon$ centered at $x^{*}$ is contained in $P$ , that is $B_{\epsilon }(x^{*})\subset P$ . Therefore,

x^{*}-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\in P

and

c^{T}\left(x^{*}-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\right)=c^{T}x^{*}-{\frac {\epsilon }{2}}{\frac {c^{T}c}{||c||}}=c^{T}x^{*}-{\frac {\epsilon }{2}}||c||<c^{T}x^{*}

And hence we have a contradiction because $x^{*}$ is not an optimal solution.

Therefore, $x^{*}$ must live on the boundary of $P$ . If $x^{*}$ is not a vertex itself, it must be the convex combination of vertices of $P$ . That is that $x^{*}=\sum _{i=1}^{t}\lambda _{i}x_{i}$ with $\lambda _{i}>0$ and $\sum _{i=1}^{t}\lambda _{i}=1$ . Then we must have

0=c^{T}\left(\left(\sum _{i=1}^{t}\lambda _{i}x_{i}\right)-x^{*}\right)=c^{T}\left(\sum _{i=1}^{t}\lambda _{i}(x_{i}-x^{*})\right)=\sum _{i=1}^{t}\lambda _{i}(c^{T}x_{i}-c^{T}x^{*})

Since all terms in the sum are positive and the sum is equal to zero, we must have that each individual term is equal to zero. Hence, every $x_{i}$ is also optimal, and therefore all points on the face whose vertices are $x_{1},...,x_{t}$ , are all optimal solutions.