{{Short description|Function in mathematical optimization}} In mathematical optimization, the '''proximal''' operator is an operator associated with a proper,<ref group="note">An (extended) real-valued function ''f'' on a Hilbert space is said to be ''proper'' if it is not identically equal to <math>+\infty</math>, and <math>-\infty</math> is not in its image.</ref> lower semi-continuous convex function <math>f</math> from a Hilbert space <math>\mathcal{X}</math> to <math>[-\infty,+\infty]</math>, and is defined by:<ref>{{cite journal|url=https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf |title=Proximal Algorithms |author=Neal Parikh and Stephen Boyd |journal= Foundations and Trends in Optimization |volume=1 |issue=3 |year=2013 |pages=123–231 |access-date=2019-01-29}}</ref>
::<math>\operatorname{prox}_f(v) = \arg \min_{x\in\mathcal{X}} \left(f(x) + \frac 1 2 \|x - v\|_\mathcal{X}^2\right).</math> 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 <math>\text{prox}</math> of a proper, lower semi-continuous convex function <math>f</math> enjoys several useful properties for optimization.
* Fixed points of <math>\text{prox}_f</math> are minimizers of <math>f</math>: <math>\{x\in \mathcal{X}\ |\ \text{prox}_fx = x\} = \arg \min f</math>. * Global convergence to a minimizer is defined as follows: If <math>\arg \min f \neq \varnothing</math>, then for any initial point <math>x_0 \in \mathcal{X}</math>, the recursion <math>(\forall n \in \mathbb{N})\quad x_{n+1} = \text{prox}_f x_n</math> yields convergence <math>x_n \to x \in \arg \min f </math> as <math>n \to +\infty</math>. This convergence may be weak if <math>\mathcal{X}</math> is infinite dimensional.<ref>{{Cite book |last=Bauschke |first=Heinz H. |title=Convex Analysis and Monotone Operator Theory in Hilbert Spaces |last2=Combettes |first2=Patrick L. |publisher=Springer |year=2017 |isbn=978-3-319-48310-8 |series=CMS Books in Mathematics |location=New York |doi=10.1007/978-3-319-48311-5}}</ref> * The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where <math>f</math> is the 0-<math>\infty</math> characteristic function <math>\iota_C</math> of a nonempty, closed, convex set <math>C</math> we have that : <math> \begin{align} \operatorname{prox}_{\iota_C}(x) &= \operatorname{argmin}\limits_y \begin{cases} \frac{1}{2} \left\| x-y \right\|_2^2 & \text{if } y \in C \\ + \infty & \text{if } y \notin C \end{cases} \\ &=\operatorname{argmin}\limits_{y \in C} \frac{1}{2} \left\| x-y \right\|_2^2 \end{align} </math> : showing that the proximity operator is indeed a generalisation of the projection operator.
* A function is firmly non-expansive if <math>(\forall (x,y) \in \mathcal{X}^2) \quad \|\text{prox}_fx - \text{prox}_fy\|^2 \leq \langle x-y\ , \text{prox}_fx - \text{prox}_fy\rangle</math>. * The proximal operator of a function is related to the gradient of the Moreau envelope <math>M_{\lambda f}</math> of a function <math>\lambda f</math> by the following identity: <math>\nabla M_{\lambda f}(x) = \frac{1}{\lambda} (x - \mathrm{prox}_{\lambda f}(x))</math>. * The proximity operator of <math>f</math> is characterized by inclusion <math> p=\operatorname{prox}_f(x) \Leftrightarrow x-p \in \partial f(p) </math>, where <math> \partial f </math> is the subdifferential of <math>f</math>, given by : <math> \partial f(x) = \{ u \in \mathbb{R}^N \mid \forall y \in \mathbb{R}^N, (y-x)^\mathrm{T}u+f(x) \leq f(y)\} </math> In particular, If <math>f</math> is differentiable then the above equation reduces to <math> p=\operatorname{prox}_f(x) \Leftrightarrow x-p = \nabla f(p) </math>.
== Notes == {{reflist|group=note}}
==References== {{Reflist}}
== See also == * Proximal gradient method
==External links== * The [http://proximity-operator.net/ Proximity Operator repository]: a collection of proximity operators implemented in Matlab and Python. * [https://github.com/kul-forbes/ProximalOperators.jl ProximalOperators.jl]: a Julia package implementing proximal operators. * [https://github.com/odlgroup/odl ODL]: a Python library for inverse problems that utilizes proximal operators.
Category:Mathematical optimization