1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Thank you so much. I was thinking that it should boil down to projection problem... $\endgroup$ – user550103 Dec 31 '18 at 13:16

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.