Analytical solution for optimization problem

Question

Suppose we have a vector $p \in \Re ^n$. How can I get analytical solution for that optimization problem: $p = \arg \min {f(x)}_{p \in R} $ if $f(p) = ||p-z||^{2}_{2} + x||p||_{1} $, where $|| \cdot || $ are $L^1$ and $L^2$ norm and $x > 0$.

UPD1 Is it correct if I rewrite $f(p)$ as following: $f(p) = \sum_{i=1}^{N} \sqrt{(p-z)^2} + x\sum_{i=1}^{N}|{p}| $ ?

Have you tried the cases $n=1$ and $n=2$ just to get an idea? — mvw, Feb 04 '19 at 13:18
your reformulation is correct, but you should not expect an analytical solution for the 1-norm — LinAlg, Feb 04 '19 at 13:43
Ok. But is there a analytical solution for first fromulation? — Vasya Pravdin, Feb 04 '19 at 13:53
The reformulation is not quite correct, see my answer. the $\sqrt{}$ can be removed and the indices for coefficients are missing — supinf, Feb 04 '19 at 14:01

score 0 · Accepted Answer · answered Feb 04 '19 at 14:00

Here is a sketch for obtaining an analytical solution:

First, we consider only the case $n=1$. The problem can be written as $ \min f(p)= (p-z)^2+x |p|$. Then, by using classical methods and analyzing the cases $p \leq,0$ and $p\geq0$ one can optain that the solution $\bar p$ is given by $$ \bar p = \tfrac12 \min(z+x,\max(z-x,0)). $$ I suggest you try to figure out the details by yourself.

For $n>1$, the objective function $f$ can be written as $$ f(p) = \sum_{i=1}^N \left( (p_i-z_i)^2 + x | p_i| \right). $$

For this problem the solution can be obtained by minimizing each $p_i$ seperately using the method of the case $n=1$. This is possible due to the special structure of the problem. Then the analytical solution can be obtained by putting the individual solutions together in a vector $\bar p\in\mathbb R^n$.

Not clear enough but thank you anyway! – Vasya Pravdin Feb 05 '19 at 09:13 — Vasya Pravdin, Feb 05 '19 at 09:13

Analytical solution for optimization problem

1 Answers1