Proximal operator

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

{prox}_{f} (v) = \arg min_{x \in 𝒳} (f (x) + \frac{1}{2} ‖ x - v ‖_{𝒳}^{2}) .

For any function in this class, the minimizer of the right-hand side above is unique, hence making the proximal operator well-defined. The proximal operator is used in proximal gradient methods, which is frequently used in optimization algorithms associated with non-differentiable optimization problems such as total variation denoising.

Properties

The $prox$ of a proper, lower semi-continuous convex function $f$ enjoys several useful properties for optimization.

Fixed points of ${prox}_{f}$ are minimizers of $f$ : ${x \in 𝒳 | {prox}_{f} x = x} = \arg min f$ .
Global convergence to a minimizer is defined as follows: If $\arg min f \neq \emptyset$ , then for any initial point $x_{0} \in 𝒳$ , the recursion $(\forall n \in ℕ) x_{n + 1} = {prox}_{f} x_{n}$ yields convergence $x_{n} \to x \in \arg min f$ as $n \to + \infty$ . This convergence may be weak if $𝒳$ is infinite dimensional.
The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where $f$ is the 0- $\infty$ characteristic function $ι_{C}$ of a nonempty, closed, convex set $C$ we have that

\begin{matrix} {prox}_{ι_{C}} (x) & = \underset{y}{argmin} {\begin{matrix} \frac{1}{2} {‖ x - y ‖}_{2}^{2} & if y \in C \\ + \infty & if y \notin C \end{matrix} \\ = \underset{y \in C}{argmin} \frac{1}{2} {‖ x - y ‖}_{2}^{2} \end{matrix}

showing that the proximity operator is indeed a generalisation of the projection operator.

The proximal operator is firmly non-expansive: $(\forall (x, y) \in 𝒳^{2}) ‖ {prox}_{f} x - {prox}_{f} y ‖^{2} \leq ⟨ x - y, {prox}_{f} x - {prox}_{f} y ⟩$ .
The proximal operator of a function is related to the gradient of the Moreau envelope $M_{λ f}$ of a function $λ f$ by the following identity: $\nabla M_{λ f} (x) = \frac{1}{λ} (x - {p r o x}_{λ f} (x))$ .
The proximity operator of $f$ is characterized by inclusion $p = {prox}_{f} (x) \Leftrightarrow x - p \in \partial f (p)$ , where $\partial f$ is the subdifferential of $f$ , given by

\partial f (x) = {u \in ℝ^{N} ∣ \forall y \in ℝ^{N}, (y - x)^{T} u + f (x) \leq f (y)}

In particular, If

f

is differentiable then the above equation reduces to

p = {prox}_{f} (x) \Leftrightarrow x - p = \nabla f (p)

.

Notes

↑ An (extended) real-valued function f on a Hilbert space is said to be proper if it is not identically equal to $+ \infty$ , and $- \infty$ is not in its image.

References

↑ Neal Parikh and Stephen Boyd (2013). "Proximal Algorithms" (PDF). Foundations and Trends in Optimization. 1 (3): 123–231. Retrieved 2019-01-29.
↑ 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.

[1] An (extended) real-valued function f on a Hilbert space is said to be proper if it is not identically equal to $+ \infty$ , and $- \infty$ is not in its image.

[2] Neal Parikh and Stephen Boyd (2013). "Proximal Algorithms" (PDF). Foundations and Trends in Optimization. 1 (3): 123–231. Retrieved 2019-01-29.

[3] 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.

Proximal operator

Properties

Notes

References

See also

External links