maximum of a linear function on a convex set

Question

How to prove that any linear function which is defined on a convex subset of $\mathbb{R}^n$ attains its maximum always at one of the extreme points of the set? Thank you for the hint!

Answer 1

Let $C \in \mathbb{R}^n$ be a convex function, and $f(x)$ be a linear function defined on $C$.
Assume that the maximum is attained at one of the non-extreme points, say $y$. Then, if $x_1,\dots,x_k$ are the extreme points of $C$, we can write $y=\sum_{i=1}^k \mu_i x_i$ such that $\sum_{i=1}^k \mu_i =1,\, \mu_i\geq 0\,\forall i$.
Let $f(x_m)=\max_{1\leq i\leq k} f(x_i)$.
$f(y)=f(\sum_{i=1}^k \mu_i x_i)= \sum_{i=1}^k \mu_i f(x_i)\leq \sum_{i=1}^k \mu_if(x_m)=f(x_m)$.
The second equality follows because $f$ is linear and the third inequality follows by the definition of $f(x_m).$ This implies that $\exists$ an extreme point $x_m$ that gives better (or same) objective function value as $y$. So, we conclude that the maximum of a linear function on a convex set can be obtained at an extreme point.