# Proximal Operator of Piecewise Linear Functions

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.

• 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 – tibL Sep 26 '16 at 9:36