Interesting Examples of Convex Non Smooth Functions with Non Trivial Proximal Operators

Question

I'm experimenting with optimizing convex functional with proximal operator methods. The main problem is I cannot come up with interesting non-smooth functions. I use various combinations of indicator functions and $ {L}_{1} $ norms, but those are boring. Could you please suggest any interesting ideas?

Answer 1

I might not fully understand your question, but $x \mapsto |x|$ is convex and not smooth at $0$, so doesn't it satisfy your needs?

More generally, if $V$ is a normed space and $\{p_1, \dots, p_n\} \subset V$, then $x \mapsto \| x - p_1 \| + \dots + \| x - p_n \|$ will be convex (as the sum of convex functions) with singular points precisely at $p_1, \dots, p_n$.

Answer 2

For any nonempty convex subset $S$ of a normed linear space, the distance to $S$ is a convex function.

The Legendre transform of a convex function is a convex function.

In equilibrium statistical mechanics of lattice systems, the pressure in a convex function of the interaction. First-order phase transitions occur where it is non-differentiable.

Answer 3

An interesting set of examples of nonsmooth convex functions are the Lovasz extensions of submodular set functions. In general they are nonsmooth at points where components are equal (e.g. $x$ such that $x_i = x_j$ for some $i \ne j$).

If you want a very interesting function, one that's NP-hard just to evaluate, consider the optimal value of max-cut as a function of the weights:

$$ f(w) = \max_{x \in \{-1,1\}^n} \sum_{i,j} x_i w_{ij} x_j $$

This is the maximum of linear functions of $w$, so it's clearly a convex function of $w$, but evaluating it in general requires solving a maximum cut problem. (Even though it's an NP-hard problem, you can still solve by brute force when the number of dimensions is small if you just want a toy example.) It's the convex conjugate of the indicator function of the cut polyhedron.