Show that Problem (P’) can be reduced to Problem (P)

Question

We consider the following minimization problem (P): $$ \min _{\substack{x \geq 0 \\ \sum_i x_i \leq 1}} \frac{1}{2} \lVert x-a \rVert^2 . $$

On the other hand, we also consider the problem We now remove the positivity hypothesis and consider, for any $a \in \mathbb{R}^n$, the following problem: $\left(\mathrm{P}^{\prime}\right)$ $$ \min _{ \lVert x \rVert_1 \leq 1} \frac{1}{2} \lVert x-a \rVert^2 $$

I need to prove that Problem $\left(\mathrm{P}^{\prime}\right)$ can be reduced to Problem $(\mathrm{P})$ and show how the solutions to both problems are related.

My attempt I try to write $x_i = x_i^+ - x_i^-$ where $x_i^+ = \max \lbrace x_i;0 \rbrace$ and $x_i^- = \max\lbrace -x_i;0 \rbrace$ but I don't know how to split the objective function.

Answer 1

Hint 1:

In the solution to $P'$, if what can you say about the relationship between the sign of $a_i$ and the sign of $x^*_i$, where $x^*$ is the optimal solution to $P'$?

Hint 2:

Define $a'$ by $a'_i = |a_i|$. Can you find any relationship between the optimal solution to $P$ with $a$ vs the optimal solution to $P'$ with $a'$; or between the optimal solution to $P$ with $a'$ vs the optimal solution to $P'$ with $a$? (For convenience, assume the optimal solution is unique in each case.) Does that help you find a reduction?

Answer to Hint 1:

The sign of $a_i$ is the same as the the sign of $x_i$. (If the signs differ, then flip the sign of $x_i$; this decreases the value of the objective function, or keeps it the same.)

Answer to Hint 2:

The optimal solution to $P'$ with $a'$ will be the optimal solution to $P$ with $a'$. (Why? Since $a'_i=|a_i|\ge 0$, the optimal solution to $P'$, call it $x^*$, will always have $x^*_i\ge 0$ (as we learned from Hint 1, the sign of $x^*_i$ will be the same as the sign of $a'_i$), so $x^*$ is already a valid solution to $P$ with $a$ (since $x^*\ge 0$ and $\|x^*\|\le 1$ implies $\sum_i x^*_i \le 1$); and any solution to $P$ with $a$ is also a valid solution to $P'$ with $a'$.) Also, the optimal solution to $P'$ with $a'$ can be obtained from the optimal solution $P'$ with $a$. (How? Let $x^*$ be the optimal solution to $P'$ with $a'$. If $a_i < 0$, let $\hat{x}_i=-x^*_i$, otherwise let $\hat{x}_i=x^*_i$. Then $\hat{x}$ is the optimal solution to $P'$ with $a$.) Putting these two together gives us a way to reduce $P'$ to $P$. If you have a way to solve $P$, you can find the solution to $P$ with $a'=|a|$, then convert that solution to a solution to $P'$ with $a$.