Show that the set of all minimum points of a convex function over a convex set is convex

Question

I am given the following problem, but can't figure it out.

Let $f\colon\mathcal{C}\rightarrow\mathbb{R}$ denote a convex function defined on the convex set $\mathcal{C}$. A (global) minimum of $f$ is an $x^*\in\mathcal{C}$ with $f(x^*)\leq f(x)$ for all $x\in\mathcal{C}$. Show that the set $\mathcal{S}$ of all minimum points of $f$ is convex.

I have tried the following but am unable to "finish" the solution (maybe I'm not even close and working in the wrong direction?):

$$\mathcal{S} = \left\{x^*~\middle|~f(x^*)\leq f(x),\, x\in\mathcal{C}\right\}$$

Let $u, v \in\mathcal{C}$, $\lambda\in(0,1)$. Then

$$\lambda u + (1-\lambda)v \overset{!}{\in} \mathcal{S}\\ \Leftrightarrow f(\lambda u + (1-\lambda)v) \overset{!}{\leq} f(x),\quad\forall x\in\mathcal{C}$$

• $f$ is strict convex: the set S has only one element and the set is convex
• $f$ is convex: because $f$ is defined over a convex set the line of points between $u$ and $v$ are in the set. At this point I'm lost.

Answer 1

Let $x,y\in\mathcal{C}$. Since both are minimizers, $f(x)=f(y)$. Let $\lambda\in[0,1]$. Since $f$ is convex, $f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)=\lambda f(x)+(1-\lambda)f(x)=f(x)$. Since $x$ minimizes $f$, also $f(x)\leq f(\lambda x+(1-\lambda)y)$. So every convex combination in $\mathcal{C}$ gives the same value of $f$ and is a minimizer. So $\mathcal{S}$ is convex.

Answer 2

Let $x_1$ and $x_2$ be two minimum points. If $0 \leq \lambda \leq 1$, then $$f (\lambda x_1 + (1-\lambda)x_2)\leq \lambda f(x_1)+(1-\lambda)f(x_2) = \lambda \min f + (1-\lambda) \min f = \min f.$$ Hence $\lambda x_1 + (1-\lambda) x_2$ is a minimum point.

Answer 3

Note: the solution has already been given, but this is an alternative proof I found to be more intuitive.

Given a non-empty convex set $\mathcal{C}$, and convex function $f:\mathcal{C}\to \mathbb{R}$, by the definition of convexity we know that any local minimum is a global minimum of $f$ over $\mathcal{C}$.

As such, we know that given two minimizers $x^*, y^* \in \mathcal{C}$, $f(x^*) = f(y^*) \in \mathcal{S}$ where we can define $\mathcal{S}$ as the set of global minima of $f$.

Given the definition of a convex set:

$\mathcal{F}$ is convex if for every convex combination $x,y \in F$ and $\forall \lambda \in [0,1]$, $\lambda x + (1-\lambda)y \in \mathcal{F}$.

We can then see that $\lambda f(x^*) + (1-\lambda)f(y^*) = f(x^*) = f(y^*) \in \mathcal{S}$ satisfies the above definition for every convex combination $f(x^*), f(y^*) \in \mathcal{S}$ and $\lambda \in [0,1]$ because all $f(x^*) = f(y^*) \in \mathcal{S}$.

QED