|
:<math>\min c^T x \text{ subject to } x \in P</math>
Where <math>P = \{x \in \mathbb{R}^n : Ax \leq b\}</math>. If <math>P</math> is a bounded polyhedron (and thus a polytope) and <math>x^*\ast</math> is an optimal solution to the problem, then <math>x^*\ast</math> is either an extreme point (vertex) of <math>P</math>, or lies on a face <math>F \subset P</math> of optimal solutions.
==Proof==
Suppose, for the sake of contradiction, that <math>x^*\ast \in \mathrm{int}(P)</math>, then there exists some <math>\epsilon > 0</math> such that the ball of radius <math>\epsilon</math> centered at <math>x^*\ast</math> is contained in <math>P</math>, that is <math>B_{\epsilon}(x^*\ast) \subset P</math>. Therefore,
:<math>x^*\ast - \frac{\epsilon}{2} \frac{c}{||c||} \in P</math> and
:<math>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</math>
And hence we have a contradiction because <math>x^*\ast</math> is not an optimal solution.
Therefore, <math>x^*\ast</math> must live on the boundary of <math>P</math>. If <math>x^*\ast</math> is not a vertex itself, it must be the convex combination of vertices of <math>P</math>. That is that <math>x^*\ast = \sum_{i=1}^t \lambda_i x_i</math> with <math>\lambda_i > 0</math> and <math>\sum_{i=1}^t \lambda_i = 1</math>. Then we must have
:<math>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^Tx_i - c^Tx^*\ast)</math>
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 <math>x_i</math> is also optimal, and therefore all points on the face whose vertices are <math>x_1, ..., x_t</math>, are all optimal solutions.
| 