# Fundamental theorem of linear programming

In mathematical optimization, the fundamental theorem of linear programming states, in a weak formulation, 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^\ast$ is an optimal solution to the problem, then $x^\ast$ 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^\ast \in \mathrm{int}(P)$. Then there exists some $\epsilon > 0$ such that the ball of radius $\epsilon$ centered at $x^\ast$ is contained in $P$, that is $B_{\epsilon}(x^\ast) \subset P$. Therefore,

$x^\ast - \frac{\epsilon}{2} \frac{c}{||c||} \in P$ and
$c^T\left( x^\ast - \frac{\epsilon}{2} \frac{c}{||c||}\right) = c^T x^\ast - \frac{\epsilon}{2} \frac{c^T c}{||c||} = c^T x^\ast - \frac{\epsilon}{2} ||c|| < c^T x^\ast.$

Hence $x^\ast$ is not an optimal solution, a contradiction. Therefore, $x^\ast$ must live on the boundary of $P$. If $x^\ast$ is not a vertex itself, it must be the convex combination of vertices of $P$, say $x_1, ..., x_t$. Then $x^\ast = \sum_{i=1}^t \lambda_i x_i$ with $\lambda_i \geq 0$ and $\sum_{i=1}^t \lambda_i = 1$. Observe that

$0=c^{T}\left(\left(\sum_{i=1}^{t}\lambda_{i}x_{i}\right)-x^{\ast}\right)=c^{T}\left(\sum_{i=1}^{t}\lambda_{i}(x_{i}-x^{\ast})\right)=\sum_{i=1}^{t}\lambda_{i}(c^{T}x_{i}-c^{T}x^{\ast}).$

Since $x^{\ast}$ is an optimal solution, all terms in the sum are nonnegative. Since the sum is equal to zero, we must have that each individual term is equal to zero. Hence, $c^{T}x^{\ast}=c^{T}x_{i}$ for each $x_i$, so every $x_i$ is also optimal, and therefore all points on the face whose vertices are $x_1, ..., x_t$, are optimal solutions.