Fundamental theorem of linear programming

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

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.

References