What is Moreau’s Decomposition Theorem?

Let f: \mathbb{R}^n \mapsto \mathbb{R} be a convex function. Moreau’s Decomposition Theorem is the following result:

Theorem (Moreau Decomposition). For all x \in \mathbb{R}^n,

x = \textbf{prox}_{f} (x) + \textbf{prox}_{f^*} (x),

where \textbf{prox}_{f} is the proximal operator for f and f^* is the convex conjugate of f.

Here is the proof: Let z = \textbf{prox}_{f} (x). Then,

\begin{aligned} z = \textbf{prox}_{f} (x) \quad &\Leftrightarrow \quad x - z \in \partial f(z) \\  &\Leftrightarrow \quad z \in \partial f^*(x-z) \\  &\Leftrightarrow \quad x - (x-z) \in \partial f^*(x-z) \\  &\Leftrightarrow \quad x - z = \textbf{prox}_{f^*} (x) \\  &\Leftrightarrow \quad x = \textbf{prox}_{f} (x) + \textbf{prox}_{f^*} (x). \end{aligned}

The second equivalence is a result involving convex conjugates and subdifferentials (see this post for statement and proof) while the 4th equivalence is a property of the proximal operator (see the note at the end of this post).

Extended Moreau Decomposition

The extended version of Moreau’s Decomposition Theorem involves a scaling factor \lambda > 0. It states that for all x,

\begin{aligned} x = \textbf{prox}_{\lambda f} (x) + \textbf{prox}_{\lambda^{-1} f^*} (x / \lambda). \end{aligned}

Proof: Applying Moreau decomposition to the function \lambda f gives

x = \textbf{prox}_{\lambda f} (x) + \textbf{prox}_{(\lambda f)^*} (x).

Using the definitions of the proximal operator and the convex conjugate,

\begin{aligned} \textbf{prox}_{(\lambda f)^*} (x) &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| x - u \|_2^2 + (\lambda f)^* (u) \right\} \\  &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| x - u \|_2^2 + \sup_v \left[ u^\top v - \lambda f(v) \right] \right\} \\  &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \|(x/\lambda) - (u / \lambda) \|_2^2 + \frac{1}{\lambda} \sup_v \left[ (u / \lambda)^\top v - f(v) \right] \right\} \\  &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \|(x/\lambda) - (u / \lambda) \|_2^2 + \frac{1}{\lambda} f^*( u / \lambda) \right\} \\  &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| (x / \lambda) - u \|_2^2 + \lambda^{-1}f^* (u) \right\} \\  &= \textbf{prox}_{\lambda^{-1} f^*} (x / \lambda). \end{aligned}


  1. Gu, Q. (2016). “SYS 6003: Optimization. Lecture 25.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s