Let $f:\mathbb R^n \to \mathbb R$ be a piecewise linear function, i.e., $$ f(x) = \max_i \langle a_i, x\rangle + b_i, $$ for some $i \geq 1$. I'm interested in efficiently solving the proximal operator for small values of $n$. $$ \text{prox}_{\tau f}(y) := \arg \min_x ~ f(x) + \frac{\| x-y \|^2}{2 \tau} $$ Clearly, by adding an additional variable, this can be transformed into a quadratic program which then can be solved using e.g. active set or interior point methods.

However, for $n=1$ there exists a simple and efficient solution (which is very similar to the shrinkage operator for the absolute value function).

I'm looking for efficient algorithms for the cases $n=2$ or $n=3$, but surprisingly couldn't find any literature on this topic.

  • $\begingroup$ Well as you said it's equivalent to the QP problem which has been studied extensively and the algorithms are very efficient, when $n=1$ the QP problem is also trivial $\endgroup$ – tibL Sep 26 '16 at 9:36

Your Answer

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

Browse other questions tagged or ask your own question.