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[edit]

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[edit]

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 Alan o Conner wrote this theorem

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.

References[edit]