Moreau envelope

The Moreau envelope (or the Moreau-Yosida regularization)

M

f

{\displaystyle M_{f}}

of a proper lower semi-continuous convex function

f

{\displaystyle f}

is a smoothed version of

f

{\displaystyle f}

. It was proposed by Jean-Jacques Moreau in 1965.

The Moreau envelope has important applications in mathematical optimization: minimizing over

M

f

{\displaystyle M_{f}}

and minimizing over

f

{\displaystyle f}

are equivalent problems in the sense that the sets of minimizers of

f

{\displaystyle f}

and

M

f

{\displaystyle M_{f}}

are the same. However, first-order optimization algorithms can be directly applied to

M

f

{\displaystyle M_{f}}

, since

f

{\displaystyle f}

may be non-differentiable while

M

f

{\displaystyle M_{f}}

is always continuously differentiable. Indeed, many proximal gradient methods can be interpreted as a gradient descent method over

M

f

{\displaystyle M_{f}}

.

Definition

The Moreau envelope of a proper lower semi-continuous convex function

f

{\displaystyle f}

from a Hilbert space

X

{\displaystyle {\mathcal {X}}}

to

(

−

∞

,

+

∞

]

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

is defined as

M

f

(

v

)

=

inf

x

∈

X

(

f

(

x

)

+

1

2

‖

x

−

v

‖

2

2

)

.

{\displaystyle M_{f}(v)=\inf _{x\in {\mathcal {X}}}\left(f(x)+{\frac {1}{2}}\|x-v\|_{2}^{2}\right).}

Given a parameter

λ

∈

R

{\displaystyle \lambda \in \mathbb {R} }

, the Moreau envelope of

λ

f

{\displaystyle \lambda f}

is also called as the Moreau envelope of

f

{\displaystyle f}

with parameter

λ

{\displaystyle \lambda }

.

Properties

The Moreau envelope can also be seen as the infimal convolution between

f

{\displaystyle f}

and

(

1

/

2

)

‖

⋅

‖

2

2

{\displaystyle (1/2)\|\cdot \|_{2}^{2}}

.

The proximal operator of a function is related to the gradient of the Moreau envelope by the following identity:

∇

M

λ

f

(

x

)

=

1

λ

(

x

−

p

r

o

x

λ

f

(

x

)

)

{\displaystyle \nabla M_{\lambda f}(x)={\frac {1}{\lambda }}(x-\mathrm {prox} _{\lambda f}(x))}

. By defining the sequence

x

k

+

1

=

p

r

o

x

λ

f

(

x

k

)

{\displaystyle x_{k+1}=\mathrm {prox} _{\lambda f}(x_{k})}

and using the above identity, we can interpret the proximal operator as a gradient descent algorithm over the Moreau envelope.