# Why is the finding proximal operator a convex problem?

I have been researching and the proximal operator seems to be defined as:

$$\DeclareMathOperator*{\argmin}{argmin}\DeclareMathOperator{\prox}{prox} \prox_f(v)=\argmin_x\left(f(x)+\frac{1}{2}\|x-v\|^2_2\right)$$

I have found it stated several times that this is always a convex problem with a unique minimizer. I have not, however, been able to find a proof of this statement. So, why does the proximal operator have a unique solution?

In addition, this article (link credit Mark L. Stone, see comments) hints that $f(x)$ must be convex for the proximal operator to be a convex problem. If this condition is required by the proof, why would someone use proximal optimization methods over simple gradient descent?

• Change the - sign to + sign, then read web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf . – Mark L. Stone Jul 13 '16 at 19:35
• Thanks. I have read that PDF with a little more detail than before posting now, but I still don't see an exact answer to my main question in there. I'll edit the question with respect to what I found on the second read of that link though. – KFox Jul 13 '16 at 21:32
• If $f(x)$ is convex, then the proximal operator is strictly convex; so has a unique global minimum. It's possible that the proximal operator could be convex, even if $f(x)$ is not. The main attraction of proximal operator methods seems to be dealing with convex, but non-differentiable, $f(x)$, for which gradient-based methods aren't directly applicable (in reality, methods such as BFGS can sometimes "blast' their way through or past isolated non-differentiable points, if not at the optimum). Proximal operator becomes attractive when prox problems are easy to solve (maybe even in closed form).. – Mark L. Stone Jul 13 '16 at 21:55
• I recently learned that the sum of two convex functions (even with different domains) is convex. This, in combination with your comment, answers my question. Thanks! – KFox Jul 13 '16 at 21:59
• If you make it through chapters 2 and 3 of stanford.edu/~boyd/cvxbook (by one of the same authors as the paper), you'll understand much more complicated operations than addition which preserve convexity. – Mark L. Stone Jul 13 '16 at 22:02

The Prox operator you wrote assumes $f \left( \cdot \right)$ is a Convex Function.