= Infimal convolution
{title2=$E\mathbin\square F$}
= Inf-convolution
{synonym}
An <infimal convolution> is the cheapest way to split a prescribed total between two costs. Suppose two activities contribute $u$ and $v$ to a required total $x$, costing $f(u)$ and $g(v)$. Their combined cost is optimized over all splits $u+v=x$, rather than charging both activities for the entire total.
For <proper extended-real functions> $f,g:X\to\mathbb R\cup\{+\infty\}$ on a <real vector space> $X$, define
$$
h(x)=(f\mathbin\square g)(x)=\inf_{u\in X}\{f(u)+g(x-u)\}=\inf_{u+v=x}\{f(u)+g(v)\}.
$$
The definition does not require <convexity>. An infinite cost forbids that contribution, as with an <indicator functional of a constraint set>. If no split has two finite costs, set $h(x)=+\infty$; if the costs of admissible splits are unbounded below, $h(x)=-\infty$. Thus proper inputs need not produce a <proper extended-real function>. The notation $E\mathbin\square F$ denotes the same operation. See https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf#page=17[Parikh and Boyd, Proximal Algorithms, §3.1] for the standard <convex analysis> definition and its connection to the <Moreau envelope>.
An <infimum> is a best lower bound, whereas a <minimum> is a value realized by some split. Writing $\min$ in place of $\inf$ requires an attaining pair $(u_*,v_*)$. For <convex functions>, mixing two nearly optimal splits and applying <convexity> to each cost proves that their <infimal convolution> is <convex> whenever it is proper; one must use nearly optimal splits because exact minimizers need not exist. Its <convex conjugate> is $f^*+g^*$ whenever the <extended real number> arithmetic is well defined; see <conjugate of an infimal convolution> for the precise identity. This turns the optimization over splits into addition in the conjugate variables.
\b[Two quadratic costs: share the load according to its price.] Let $X=\mathbb R$ and let the <convex quadratic functions> be
$$
f(u)=\frac a2u^2,\qquad g(v)=\frac b2v^2,\qquad a,b>0.
$$
For fixed $x$, eliminate $v=x-u$. The <derivative> of the total cost is $au-b(x-u)$, so equal marginal costs give
$$
u_* =\frac b{a+b}x,\qquad v_* =\frac a{a+b}x,\qquad au_*=bv_*.
$$
The cheaper activity receives more of a positive total: when $a<b$ and $x>0$, $u_*>v_*$. Completing the square gives an exact certificate for every competing split:
$$
\frac a2u^2+\frac b2(x-u)^2
=\frac{ab}{2(a+b)}x^2+\frac{a+b}{2}\left(u-\frac b{a+b}x\right)^2.
$$
Consequently the <infimum> is a unique <minimum>, and
$$
(f\mathbin\square g)(x)=\frac12\frac{ab}{a+b}x^2.
$$
The effective quadratic coefficient is $c=ab/(a+b)$, with $1/c=1/a+1/b$. It is smaller than either $a$ or $b$: allowing both activities reduces the cost compared with assigning everything to either one. If $a=b$, each receives half the total and $c=a/2$. This is a simple <quadratic optimization> problem whose answer preserves the form of the original costs.
\Image[/infimal-convolution-quadratic-split.png]
{title=Optimizing the split of two quadratic costs gives a cheaper quadratic total cost}
{description=An exact illustrative calculation, not measured data: $a=1$, $b=3$ and $x=3$ give $(u_*,v_*)=(2.25,0.75)$ and cost $3.375$, compared with cost $4.5$ for an equal split. The right panel compares the optimized cost $3x^2/8$ with assigning the whole total to either activity.}
\b[Smoothing a corner by splitting its cost.] Take the <absolute value function> $f(u)=|u|$ and the <convex quadratic function> $g(v)=v^2/(2t)$, with $t>0$. This <infimal convolution> is the <Moreau envelope> of the <absolute value function>:
$$
u_*=\operatorname{sgn}(x)\max(|x|-t,0),\qquad v_*=x-u_*,\qquad
(f\mathbin\square g)(x)=\begin{cases}x^2/(2t),&|x|\leq t,\\|x|-t/2,&|x|>t.\end{cases}
$$
Here $\operatorname{sgn}$ is the <sign function>, with $\operatorname{sgn}(0)=0$. The optimal $u_*$ is <soft thresholding>. In the central region, the <quadratic function> carries the whole total; outside it, $v_*$ stays at $t\operatorname{sgn}(x)$ and the <absolute value function> carries the excess. At $t=1$ the result is the <Huber loss> in the normalization $x^2/2$ near zero and $|x|-1/2$ outside. Its <derivative> is $x$ for $|x|\leq1$ and $\operatorname{sgn}(x)$ outside, so the corner becomes a continuous change of slope. Parikh and Boyd's https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf#page=18[§3.1 discussion of Moreau smoothing]{ref} uses twice this normalization for the <Huber loss>; the explicit formula here fixes the convention. This is also the one-dimensional case of the existing <Moreau envelope of the Euclidean norm>.
\Image[/infimal-convolution-huber-smoothing.png]
{title=Splitting absolute-value and quadratic costs produces a smooth Huber loss}
{description=Exact illustrative curves with $t=1$, not measured data. The left panel compares $|x|$ with its <Moreau envelope>; the right shows the optimal contributions $u_*$ and $v_*$, whose sum is $x$. Beyond the cutoffs $x=\pm1$, the quadratic contribution remains clipped while the absolute-value contribution grows.}
Back to article page
