Proximal operator

In mathematical optimization, the proximal operator is an operator associated with a proper, lower semi-continuous convex function ${\displaystyle f}$ from a Hilbert space ${\displaystyle {\mathcal {X}}}$ to ${\displaystyle [-\infty ,+\infty ]}$, and is defined by: [1]

${\displaystyle \operatorname {prox} _{f}(v)=\arg \min _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2}}\|x-v\|_{2}^{2}\right).}$

For any function in this class, the minimizer of the right-hand side above is unique, hence making the proximal operator well-defined. The ${\displaystyle {\text{prox}}}$ of a function enjoys several useful properties for optimization, enumerated below. Note that all of these items require ${\displaystyle f}$ to be proper (i.e. not identically ${\displaystyle +\infty }$, and never take a value of ${\displaystyle -\infty }$), convex, and lower semi-continuous.

A function is said to be firmly non-expansive if ${\displaystyle (\forall (x,y)\in {\mathcal {X}}^{2})\quad \|{\text{prox}}_{f}x-{\text{prox}}_{f}y\|^{2}\leq \langle x-y\ |\ {\text{prox}}_{f}x-{\text{prox}}_{f}y\rangle }$. Fixed points of ${\displaystyle {\text{prox}}_{f}}$ are minimizers of ${\displaystyle f}$: ${\displaystyle \{x\in {\mathcal {X}}\ |\ {\text{prox}}_{f}x=x\}=\arg \min f}$.

Global convergence to a minimizer is defined as follows: If ${\displaystyle \arg \min f\neq \varnothing }$, then for any initial point ${\displaystyle x_{0}\in {\mathcal {X}}}$, the recursion ${\displaystyle (\forall n\in \mathbb {N} )\quad x_{n+1}={\text{prox}}_{f}x_{n}}$ yields convergence ${\displaystyle x_{n}\to x\in \arg \min f}$ as ${\displaystyle n\to +\infty }$. This convergence may be weak if ${\displaystyle {\mathcal {X}}}$ is infinite dimensional.[2]

It is frequently used in optimization algorithms associated with non-differentiable optimization problems such as total variation denoising.

If ${\displaystyle f(x)}$ is the 0-${\displaystyle \infty }$ indicator function of a nonempty, closed, convex set, then it is lower semi-continuous, proper, and convex and ${\displaystyle {\text{prox}}_{f}}$ is the orthogonal projector onto that set.

See also

• Proximal gradient method

References

1. Neal Parikh and Stephen Boyd (2013). "Proximal Algorithms" (PDF). Foundations and Trends in Optimization. 1 (3): 123–231. Retrieved 2019-01-29.
2. Bauschke, Heinz H.; Combettes, Patrick L. (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. New York: Springer. doi:10.1007/978-3-319-48311-5. ISBN 978-3-319-48310-8.

External links

• The Proximity Operator repository: a collection of proximity operators implemented in Matlab and Python.
• ProximalOperators.jl: a Julia package implementing proximal operators.
• ODL: a Python library for inverse problems that utilizes proximal operators.