I am having difficulties with the second part of this practice question on optimization, so I would appreciate any hints. Thanks in advance!
Let $\mathcal{M}\subset\mathbb{R}^n$ and $f:\mathcal{M}\to\mathbb{R}^n$ be convex.
I am to show that:
(1) The set arg $\min (f,\mathcal{M}):=\{x\in\mathcal{M}:f(x)\leq f(y),\; \forall y\in\mathcal{M}\}$ is convex.
(2) If $f$ is strictly convex, then $|\text{arg} \min (f,\mathcal{M})|\in\{0,1\}$
For the first part I wanted to show that for $x_1,x_2\in\text{arg} \min(f,\mathcal{M})$, $f(\lambda x_1 + (1-\lambda)x_2)\leq f(y)$:
Because $f$ is convex: $f(\lambda x_1 + (1-\lambda)x_2)\leq \lambda f(x_1)+(1-\lambda)f(x_2)$ and because $f(\text{arg} \min (f,\mathcal{M}))$ is the minimum of $f$: $\lambda f(x_1)+(1-\lambda)f(x_2)=f(x_1)=f(x_2)$
By definition $f(x_1)\leq f(y)$, therefore $\text{arg} \min (f,\mathcal{M})$ is convex.
$f$ is strictly convex in the second part, which means: $f(\lambda x_1 + (1-\lambda)x_2)\lt \lambda f(x_1)+(1-\lambda)f(x_2)\leq f(y)$.
It makes sense to me, that the first inequality holds if $|\text{arg} \min (f,\mathcal{M})|=0$, but if $|\text{arg} \min (f,\mathcal{M})|=1$, then wouldn't, in my inequality, $x_1=x_2$ and therefore $f(\lambda x_1 + (1-\lambda)x_2)=f(x_1)\lt f(x_1)=\lambda f(x_1)+(1-\lambda)f(x_2)$, which clearly doesn't hold?
Best Answer
I think you are misreading or misinterpreting the second part. It says that if $f$ is strictly convex, then there are either no points which are global minimizers or there is exactly one point which is a global minimizer.
To show this by contradiction, assume that $f$ is strictly convex and there are two (or more) points, $x_1, x_2$ in $\mathcal{M}$ such that $x_1 \ne x_2$, which are both global minimizers of $f$ (with respect to $\mathcal{M}$). Now consider the point $x_3 = 1/2*x_1 + 1/2*x_2$, which by convexity of $\mathcal{M}$ is also in $\mathcal{M}$. By strict convexity $f(x_3) < 1/2*f(x_1) + 1/2*f(x_2)$, which in turn equals $f(x_1)$. I.e., $f(x_3) < f(x_1)$. But this contradicts $x_1$ being a global minimizer of $f$. QED.