Solve $\arg\min_{x \in \mathbb{R}^n} I_C(x) + \alpha \sum_i \left\|y_i -x \right\|_2^2$, where $I_C(x)$: indicator function; set $C$: norm 2 ball

Question

I have a problem on hand that I am not sure how to handle it. Can you please help/guide me to solve this optimization problem?

\begin{align} \arg\min_{x \in \mathbb{R}^n} I_C(x) + \alpha \sum_i \left\|y_i -x \right\|_2^2 \ , \end{align} where $I_C(x)$ is an indicator or characteristic function and the set $C$ can be a norm-2 ball, i.e., $C = \left\{x \in \mathbb{R}^n : \left\|x - c \right\|_2^2 \leq r\right\}$, $y_i, c \in \mathbb{R}^n$ are given, and $r \in \mathbb{R}$.

---

My partial attempt:

The above problem can be rewritten as \begin{equation} \label{eqn:weighted_projection_problem_definition_3} \begin{aligned} & \underset{x}{\text{minimize}} & & \alpha \sum_i \left\|y_i -x \right\|_2^2 \\ & \text{subject to} & & \left\|x - c \right\|_2^2 \leq r \ ,\\ %&&& X \succeq 0. \end{aligned} \end{equation}

Right?

If yes, then I think it is possible to solve in the closed form.

Answer 1

Let's complete the square: $\| y_i - x \|^2 = \|y_i\|^2 - 2 \langle y_i, x \rangle + \|x\|^2$, so \begin{align} \sum_{i=1}^N \|y_i - x \|^2 &= -2 \left \langle \sum_{i=1}^N y_i, x \right\rangle + N \|x\|^2 + \ldots \\ &=N \left(-2 \left \langle \frac{1}{N}\sum_{i=1}^N y_i, x \right\rangle + \|x\|^2 \right) + \ldots \\ &= N \left\|x - \frac{1}{N} \sum_{i=1}^N y_i \right\|^2 + \ldots \end{align} where the ellipses ($\ldots$) indicate terms that do not depend on $x$. It follows that \begin{align} \arg\min_x \, I_C(x) + \alpha \sum_{i=1}^N \|y_i - x \|^2&= \arg\min_x I_C(x) + \alpha N \left\|x - \frac{1}{N} \sum_{i=1}^N y_i \right\|^2 \\ &= \text{projection of } \frac{1}{N} \sum_{i=1}^N y_i \text{ onto } C. \end{align}