Content deleted Content added
No edit summary |
Rhildebrand (talk | contribs) No edit summary |
||
Line 1:
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 polygon]]al 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.
==References==
|