Show that the maximum of a convex function $f$ over the polyhedron $\mathcal{P} = \textbf{conv}\{v_1,\dots,v_k\}$ is achieved at one of its vertices, i.e., $ \sup_{x \in \mathcal{P}} f(x) = \max_{i=1,\dots,k} f(v_i)$.
I am trying to prove this using Jensen's inequality. I am getting stuck because I do not know where to use the fact that the $v_i$ are vertices of $\mathcal{P}$.
Let $x$ be a maximum of the function. Then it is a convex combination of the vertices, $x=\sum_i \lambda_i v_i$ with $\lambda_i\ge0$ and $\sum_i \lambda_i=1$. By convexity $$ f(x) = f(\sum_i \lambda_i v_i) \le \sum_i \lambda_i f( v_i) \le f(x), $$ hence we have equality here. Since $f(x_i)\le f(x)$ for all $i$, it follows $f(x_i)=f(x)$ for all $i$ with $\lambda_i\ne0$. Since there is at least one such $i$, the claim follows.
Recall that convex functions are upper-semicontinuous and thus attains its maximum on the polyhedron (as it is compact).
Assume first that the maximum is not attained on the boundary of the polyhedron, but in $x_0$ in the interior (i.e. $f(x_0)>f(z)$ for every $z$ on the boundary). Pick two points $x,y$ on the boundary such that $x_0$ is on the segment connecting $x$ and $y$, i.e. $x_0=tx +(1-t)y$. Then we have the contradicition $$ f(x_0) = f(tx + (1-t)y) \leq t f(x) + (1-t)f(y) < t f(x_0) + (1-t) f(x_0) =f(x_0). $$ With the same trick you can rule out the possibility of the maximum laying on the edges.
