Existence and uniqueness of solution to minimization problem over convex set

43 Views Asked by At

Let $\mathcal{C}\subseteq\mathbb{R}^d$ be nonempty, closed and convex. Fix some $\mathbf{z}\in\mathbb{R}^d$ and consider: $$ \min_{\mathbf{x}\in\mathcal{C}}\Vert\mathbf{z}-\mathbf{x}\Vert $$

(i) Show that the problem has a solution

(ii) Show that the solution is the unique global minimizer


For (i), I have been able to show that $f(\mathbf{x}):=\Vert\mathbf{z}-\mathbf{x}\Vert$ is a convex function. Let $\mathbf{p},\mathbf{q}\in\mathcal{C}$ and $\alpha\in[0,1]$: $$ \begin{align*} f(\alpha\mathbf{p}+(1-\alpha)\mathbf{q}) &= \Vert \mathbf{z} - (\alpha\mathbf{p}+(1-\alpha)\mathbf{q})\Vert \\ &= \Vert \mathbf{z} - \alpha\mathbf{p}-(1-\alpha)\mathbf{q} \Vert \\ &= \Vert \alpha\mathbf{z}+(1-\alpha)\mathbf{z}-\alpha\mathbf{p}-(1-\alpha)\mathbf{q}\Vert \\ &= \Vert \alpha(\mathbf{z} - \mathbf{p})+(1-\alpha)(\mathbf{z} - \mathbf{q}) \Vert \\ &\leq \Vert \alpha(\mathbf{z} - \mathbf{p}) \Vert\ + \ \Vert (1-\alpha)(\mathbf{z} - \mathbf{q}) \Vert \\ &= \alpha\Vert\mathbf{z} - \mathbf{p}\Vert\ +\ (1-\alpha)\Vert\mathbf{z} - \mathbf{q}\Vert \\ &= \alpha f(\mathbf{p}) + (1-\alpha)f(\mathbf{q}) \end{align*} $$

Since $f$ is convex and $\mathcal{C}$ is convex, I have the following necessary and sufficient conditions for optimality (from my lecture notes):

Necessary condition: any local optimal point is stationary.

Sufficient condition: if $f$ is convex, any stationary point is global optimal.

So I think that it suffices to show the existence of a stationary point of $f$. Since $f$ is convex, the sufficient condition above would mean such a stationary point is a global minimizer, and thus a solution exists. I'm unsure how to proceed at this point, and I feel like I'm missing something elementary.


For (ii) above, I believe that I would need to show that $f$ is strictly convex. If $f$ is strictly convex, then the minimizer of $$ \min_{\mathbf{x}\in\mathcal{C}}{f(\mathcal{x})} $$ is unique.


I would greatly appreciate any hints as to how I could proceed with these problems, particularly (i).