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.

\textbf{Statement of theorem:}

Consider the optimization problem \begin{equation} \min c^T x \ \ \text{subject to} \ \ x \in P \end{equation} 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^*$ lies 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 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^* - \epsilon/2 c / ||c|| \in P$ and

\begin{equation} c^T( x^* - \epsilon/2 c / ||c||) = c^T x^* - \epsilon/2 c^T c / ||c|| = c^T x^* - \epsilon/2 ||c|| < c^T x^* \end{equation} 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

\begin{equation} 0 = c^T( (\sum_{i=1}^t \lambda_i x_i) - x^*) = c^T( \sum_{i=1}^t \lambda_i (x_i - x^*)) = \sum_{i=1}^t \lambda_i (c^Tx_i - c^Tx^*) \end{equation} 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.