2
$\begingroup$

Is there a closed-form solution of the following convex problem:

$$\min_x \| x - u \| + C \| x - v \|^2$$

where $\| \cdot \|$ is the L2 norm.

$\endgroup$
  • $\begingroup$ Frankly I doubt it. But why do you need it? Is there a specific reason why a similar model $\|x-u\|_2^2+D\|x-v\|_2^2$ won't work? And is there a specific reason why a numerical solution won't suffice? $\endgroup$ – Michael Grant Sep 12 '14 at 19:57
  • $\begingroup$ This subproblem comes up in a robust (mixed norm) formulation of a problem. That is precisely why the square is not desirable. One is required to solve this subproblem in the innermost loop of the iterations, so having a closed-form solution would really speed things up. This does have a closed-form solution in one dimension, but unfortunately this cannot be leveraged to higher dimensions due to the non-separable nature of the problem. $\endgroup$ – user171375 Sep 14 '14 at 6:06
4
$\begingroup$

With a little knowledge about proximal operators, it's easy to see this is equivalent to projection onto the $l_2$ ball, which has a closed form solution. Let $y = x-u$, $w=v-u$, $f(y) = \frac{1}{2C} \|y\|$. Then the problem is equivalent to:

$$ \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator{\prox}{prox} x^*-u = y^* = \argmin_y f(y) + \frac{1}{2}\|y-w\|^2 = \prox_f(w) $$ A basic property of proximal operators is: $$ \prox_f(w) + \prox_{f^*}(w) = w $$

The dual function $f^*$ is the indicator of a ball of radius $1/2C$, so the prox operator is just projection onto a ball:

$$ \prox_{f^*}(w) = \min\left(\|w\|, \frac{1}{2 C}\right) \frac{w}{\|w\|} $$

Plugging this in gives:

$$ x^* = v - \min\left(\|v-u\|, \frac{1}{2 C}\right)\frac{v-u}{\|v-u\|} $$

As a sanity check, as $C \rightarrow +\infty$, $x^* \rightarrow v$, and for $C \le \frac{1}{2\|v-u\|}$, $x^* = u$.

$\endgroup$
  • $\begingroup$ Nice! That solved the problem. $\endgroup$ – user171375 Sep 15 '14 at 3:26
  • $\begingroup$ One way to interpret this would be to write the unconstrained problem \min_x ||x-u|| + ||x-v||^2 as the constrained problem \min_x ||x-v|| s.t. ||x-u|| \leq R (for some R), which is precisely given by a projection. Of course, this is made precise by the proximal calculation given above. $\endgroup$ – user171375 Sep 16 '14 at 4:32

Your Answer

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