Proximal operator

In mathematical optimization, the proximal operator is an operator associated with a proper, lower semi-continuous convex function

f

{\displaystyle f}

from a Hilbert space

X

{\displaystyle {\mathcal {X}}}

to

[

−

∞

,

+

∞

]

{\displaystyle [-\infty ,+\infty ]}

, and is defined by:

prox

f

⁡

(

v

)

=

arg

⁡

min

x

∈

X

(

f

(

x

)

+

1

2

‖

x

−

v

‖

X

2

)

.

{\displaystyle \operatorname {prox} _{f}(v)=\arg \min _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2}}\|x-v\|_{\mathcal {X}}^{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 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

{\displaystyle {\text{prox}}}

of a proper, lower semi-continuous convex function

f

{\displaystyle f}

enjoys several useful properties for optimization.

Fixed points of

prox

f

{\displaystyle {\text{prox}}_{f}}

are minimizers of

f

{\displaystyle f}

:

{

x

∈

X

|

prox

f

x

=

x

}

=

arg

⁡

min

f

{\displaystyle \{x\in {\mathcal {X}}\ |\ {\text{prox}}_{f}x=x\}=\arg \min f}

.

Global convergence to a minimizer is defined as follows: If

arg

⁡

min

f

≠

∅

{\displaystyle \arg \min f\neq \varnothing }

, then for any initial point

x

0

∈

X

{\displaystyle x_{0}\in {\mathcal {X}}}

, the recursion

(

∀

n

∈

N

)

x

n

+

1

=

prox

f

x

n

{\displaystyle (\forall n\in \mathbb {N} )\quad x_{n+1}={\text{prox}}_{f}x_{n}}

yields convergence

x

n

→

x

∈

arg

⁡

min

f

{\displaystyle x_{n}\to x\in \arg \min f}

as

n

→

+

∞

{\displaystyle n\to +\infty }

. This convergence may be weak if

X

{\displaystyle {\mathcal {X}}}

is infinite dimensional.

The proximal operator can be seen as a generalization of the projection operator. Indeed, in the specific case where

f

{\displaystyle f}

is the 0-

∞

{\displaystyle \infty }

characteristic function

ι

C

{\displaystyle \iota _{C}}

of a nonempty, closed, convex set

C

{\displaystyle C}

we have that

prox

ι

C

⁡

(

x

)

=

argmin

y

⁡

{

1

2

‖

x

−

y

‖

2

2

if

y

∈

C

+

∞

if

y

∉

C

=

argmin

y

∈

C

⁡

1

2

‖

x

−

y

‖

2

2

{\displaystyle {\begin{aligned}\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{aligned}}}

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

The proximal operator is firmly non-expansive:

(

∀

(

x

,

y

)

∈

X

2

)

‖

prox

f

x

−

prox

f

y

‖

2

≤

⟨

x

−

y

,

prox

f

x

−

prox

f

y

⟩

{\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 }

.