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
Since all terms in the sum are nonpositivenonnegative 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.