A function $f$ is quasiconvex if all its sub-level sets are convex (i.e., $\{ x: f(x) \le \alpha\}$ is convex for all $\alpha$.)
For a convex function $f$, it is true that $f$ acheives its maximum over a convex set $S$ at an extreme point of $S$. What is the analogue of this for quasi-convex functions?
Best Answer
I think that assuming that $S$ is compact and that $f$ achieves its supremum over $S$ you are right - see below.
If $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is quasiconvex, then for any $0\leq\theta\leq 1$
$$f(\theta x+(1-\theta)y)\leq\max\{f(x),f(y)\}.$$
Proof: To get a contradiction assume there exists an $y,z$ and $0\leq\theta\leq 1$ such that
$$f(\theta y+(1-\theta)z)>\max(f(y),f(z)).$$
Consider the sub-level set $A:=\{x:f(x)\leq\max(f(y),f(z))\}$. Then $y,z\in A$, but $\theta y+(1-\theta)z\not\in A$ which contradictions quasiconvexity of $f$.
One can iterate the above to get that:
If $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is quasiconvex, then for any $x_1,\dots,x_m\in \mathbb{R}^n$ and $\theta_1\geq 0,\dots,\theta_m\geq0$ such that
$$\sum_{i=1}^m\theta_i=1,$$
then
$$f\left(\sum_{i=1}^m\theta_i x_i\right)\leq \max_{i=1,\dots,m}\{f(x_i)\}.\quad\quad(*)$$
We can use the above to show that:
Proof: By the Krein-Milman Theorem $S$ has at least a single extreme point. In addition, if $K$ denotes the set of all extreme points of $S$, then $S$ is equal to the convex hull of $K$.
Since $x^*\in S$, and using the definition of convex hull, there exists $x_1,\dots,x_m\in K$ and $\theta_1\geq0,\dots,\theta_m\geq0$ with $\sum_{i=1}^m\theta_i=1$, such that $x^*=\sum_{i=1}^m\theta_i x_i$. Applying $(*)$ completes the proof.
Note that if $f$ is continuous, since $S$ is compact, then the existence of $x^*$ in the premise above is guaranteed.