Is the projection function convex?

Question

Define the following function $f:\mathbb{R}^n\rightarrow \mathbb{R}^n$ to be the projection function onto a convex and a closed set C

$f(x)=\arg\min_{y\in C} ||x-y||_2^2 $

Denote $f_i(x)$ $i=1,...,n$ the components of $f$.

Is it true to claim that the $f_i(x)$ $i=1,...,n$ are convex functions?

Thanks

Answer 1

No.

For example take n=1, C = [0,1].

Then f(x) = 0 if x<0; f(x) = x for x in [0,1] and f(x) = 1 for x>1. And this function is not convex.

Answer 2

No, the $f_i$'s are not convex in general. A counter-example in any dimension $n$ is the projection onto the $\ell_2$ unit ball $C := \{x \in \mathbb{R}^n | \|x\| \le 1\}$. Indeed, for each $x \in \mathbb{R}^n$ one computes \begin{eqnarray} f(x) := proj_C(x) = \begin{cases}x, &\mbox{ if }\|x\| \le 1,\\\frac{1}{\|x\|}x, &\mbox{ otherwise.}\end{cases} \end{eqnarray} Here, the component functions $f_i$ are given by \begin{eqnarray} f_i(x) = \begin{cases}x_i, &\mbox{ if }\|x\| \le 1,\\\frac{1}{\|x\|}x_i, &\mbox{ otherwise}\end{cases} \end{eqnarray} It's clear that none of the $f_i$ is convex.

However, if you're not interested in the point at which the minimum (in your the general projection problem) is attained (argmin) but, the value minimum value itself (min), then this defines convex function. Indeed, the function \begin{eqnarray} x \mapsto \underset{y \in C}{\text{min }}\frac{1}{2}\|y-x\|^2 = \underset{y \in \mathbb{R}^n}{\text{min }}\frac{1}{2}\|y-x\|^2 + i_C(y) \end{eqnarray} corresponds to the Mureau envelope of the indicator function $i_C: y \mapsto \begin{cases}0, &\mbox{ if}y \in C,\\+\infty, &\mbox{ otherwise.}\end{cases}$

An example where all the $f_i$'s are convex

Let $C = \mathbb{R}^n_+ := \{x \in \mathbb{R}^n | x_i \ge 0\text{ } \forall i\}$, the nonnegative $n$th orthant. Then $f_i(x) = max(0, x_i)$ defines a convex function for each $i$.

Hope this helps :)