sum-and-inf-convolution

Fenchel Duality: When “Addition” Meets “Infimal Convolution”

Introduction

If you’re familiar with the Fourier transform, you’ll remember that convolution in the time domain corresponds to multiplication in the frequency domain. In convex analysis, there’s a beautiful analogous phenomenon: the infimal convolution of two convex functions, under the Fenchel transform, turns into ordinary addition.

This post presents two core duality theorems, along with concise proofs.

---

Setup

Let $f, g : \mathbb{R}^n \to (-\infty, +\infty]$ be proper, closed (lsc), convex functions.

Infimal convolution:

$$(f \,\square\, g)(x) = \inf_{y} \big[f(y) + g(x-y)\big]$$

Fenchel conjugate:

$$f^*(x^*) = \sup_{x} \big[\langle x^*, x\rangle - f(x)\big]$$

---

Theorem 1 — Infimal Convolution Becomes Addition

$$(f \,\square\, g)^* = f^* + g^*$$

This holds always, with no extra conditions needed beyond $f, g$ being proper.

Proof

Expand the definition:

$$(f\,\square\,g)^*(x^*) = \sup_{x}\Big[\langle x^*,x\rangle - \inf_{y}\big(f(y)+g(x-y)\big)\Big]$$

Push the sup inside, flipping $\inf \to \sup$:

$$= \sup_{x,y}\Big[\langle x^*,x\rangle - f(y) - g(x-y)\Big]$$

Change variables $z = x - y$ (a bijection):

$$= \sup_{y,z}\Big[\langle x^*,y\rangle + \langle x^*,z\rangle - f(y) - g(z)\Big]$$

Since $y$ and $z$ are now independent, the sup separates:

$$= \underbrace{\sup_y\big[\langle x^*,y\rangle - f(y)\big]}_{f^*(x^*)} \;+\; \underbrace{\sup_z\big[\langle x^*,z\rangle - g(z)\big]}_{g^*(x^*)}$$

$$\Rightarrow\quad (f\,\square\,g)^*(x^*) = f^*(x^*) + g^*(x^*). \qquad \blacksquare$$

Intuition: taking the conjugate is a kind of “straightening out” operation — it converts the blending operation (inf-convolution) into a stacking operation (addition).

---

Theorem 2 — The Reverse Direction (and Why the Closure Appears)

$$(f^* + g^*)^* = \overline{f\,\square\,g}$$

where $\overline{h}$ denotes the closed convex hull of $h$.

Proof

Take the conjugate of both sides of Theorem 1:

$$(f\,\square\,g)^{**} = (f^*+g^*)^*$$

Since $f\,\square\,g$ is convex and proper, the Fenchel–Moreau theorem gives:

$$h^{**} = \overline{h}$$

Applying this with $h = f\,\square\,g$:

$$(f^*+g^*)^* = \overline{f\,\square\,g}. \qquad \blacksquare$$

Why the Closure?

This is the point that’s easy to overlook: the infimal convolution of two closed convex functions need not already be closed. There can be a lower-semicontinuity “gap” at the boundary of the domain. Taking the biconjugate is precisely what “patches” that gap.

When can the closure be dropped? — When a constraint qualification holds, for instance:

• $\operatorname{ri}(\operatorname{dom} f) \cap \operatorname{ri}(\operatorname{dom} g) \neq \varnothing$ (finite dimensions), or
• the Attouch–Brézis condition (a generalization to Hilbert/Banach spaces), or
• one of the two functions is polyhedral.

In these cases, $f\,\square\,g$ is automatically closed, the infimum in its definition is attained, and:

$$f\,\square\,g = (f^*+g^*)^*.$$

---

Summary Table

Left-hand side	Right-hand side after $(\cdot)^*$	Condition
$f\,\square\,g$	$f^*+g^*$	always true
$f^*+g^*$	$\overline{f\,\square\,g}$	always true
$f^*+g^*$	$f\,\square\,g$	needs a constraint qualification

---

Closing Thoughts

These two theorems are the “mirror image” of the more famous formula for the conjugate of a sum:

$$(f+g)^* = \overline{f^*\,\square\,g^*}$$

Both express a theme running through all of convex analysis: the Fenchel conjugate transforms algebraic structure — addition $\leftrightarrow$ infimal convolution — much the way the Fourier transform turns convolution into multiplication. This is no coincidence: both are variants of the “Legendre transform” applied to different function algebras.