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?




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.


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 :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.