We're studying a course and we're dabbling a bit in convex optimization.
We were told that the convex hull of a set of points x1,..,xn is a polytope and we were asked to show that any face of the convex hull must contain at least one of these points.
We defined a face to be the intersection of the polytope with a supporting hyperplane. So according to the definitions in this course the empty set is not considered a face.
I also understand that a subset of x1,..,xn must be the vertices but we aren't meant to use this property. any suggestions on how to go about proving this?
Best Answer
This is an intuition-jogger, so if at any point reading this you get the picture of the proof, feel free to finish it yourself. Every point is a convex combination of your vertices. So take an arbitrary point in a given face and write it as such. Visualise if you have to, to make a conjecture about some vertices of the convex hull having to be in the face. As you've written, a supporting hyperplane corresponding to this face is defined in terms of the inner product: for some $a$ in your vector space and $b\in\mathbb{R}$, it is the set of all points $x$ with $\langle a,x\rangle=b$. Substitute your point in the face into this expression. Use the linearity properties of the inner product in such a way that they play nicely with the convex combination. Use the fact that for all points $p$ in the convex hull $\langle a,p\rangle\leq b$ to check your conjecture.