Infimal convolution ($E\square F$)

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$, defineThe 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\square F$ denotes the same operation. See 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_{\ast },v_{\ast })$. 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^{\ast }+g^{\ast }$ 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.

Two quadratic costs: share the load according to its price. Let $X=\mathbb{R}$ and let the convex quadratic functions beFor fixed $x$, eliminate $v=x-u$. The derivative of the total cost is $au-b(x-u)$, so equal marginal costs giveThe cheaper activity receives more of a positive total: when $a<b$ and $x>0$, $u_{\ast }>v_{\ast }$. Completing the square gives an exact certificate for every competing split:Consequently the infimum is a unique minimum, andThe 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.

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:Here $\mathrm{sgn}$ is the sign function, with $\mathrm{sgn}(0)=0$. The optimal $u_{\ast }$ is soft thresholding. In the central region, the quadratic function carries the whole total; outside it, $v_{\ast }$ stays at $t\mathrm{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|\le 1$ and $\mathrm{sgn}(x)$ outside, so the corner becomes a continuous change of slope. Parikh and Boyd's ^[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.

If two nonnegative finite-valued convex functions are defined on all of a finite-dimensional space, their infimal convolution is finite, convex and continuous everywhere. Convex perturbation duality then gives strong duality and dual attainment at every argument. It does not require or imply attainment of the primal decomposition infimum.

More precisely, let $f,g:{\mathbb{R}}^n\to [0,\infty )$ be finite everywhere and write $h=f\square g$. Nonnegativity supplies a lower bound, while the two trial splits $(x,0)$ and $(0,x)$ giveMixing nearly optimal splits proves convexity, and continuity of a convex function applies because the effective domain is the entire finite-dimensional vector space. These statements concern the optimized value, rather than existence of an optimal split. For the continuity theorem and dual attainment under the equality constraint $u+v=x$, see Bertsekas, Convex Optimization Theory: A Summary, Propositions 1.3.11 and 5.3.3(a). The equality has a feasible point in the whole space for every $x$, and the displayed bound makes its optimal value finite.

A finite value without any optimal split. On $\mathbb{R}$, take the convex functions $f(u)=e^u$ and $g(v)=0$. Both are nonnegative and finite everywhere, butfor every $x$. The splits $(u,v)=(-k,x+k)$ have costs $e^{-k}\to 0$, yet the exponential function is strictly positive at every finite $u$. No split attains the infimum. The value function is even constant and differentiable; regularity of the value function does not prevent optimizing splits from escaping to infinity. For example, $k=1,3,6$ gives costs approximately $0.367879$, $0.049787$ and $0.002479$.

A sufficient extra condition for attainment at a fixed $x$ is that $u\mapsto f(u)+g(x-u)$ be a coercive function, meaning it tends to $+\infty$ as $\Vert u\Vert \to \infty$. Under the finite-valued assumptions it is a continuous function, so a sufficiently large closed ball contains a global minimum by the extreme value theorem. If this cost is also a strictly convex function, the optimal split is unique. The quadratic example above satisfies both conditions; the exponential function example does not satisfy coercivity.

Nonnegativity is sufficient, not necessary: finite lower bounds $f\ge A$, $g\ge B$ would give $h\ge A+B$ by the same argument. Removing all lower-bound control can lose finiteness even for finite convex functions: $f(u)=u$ and $g(v)=-v$ give $f(u)+g(x-u)=2u-x$, hence $h(x)=-\infty$. Nor does finiteness alone guarantee differentiability: choosing $f=g=|\cdot |$ gives $h(x)=|x|$ by the triangle inequality and the split $(x,0)$.

Under the finite-valued assumptions, subgradients of an infimal convolution are obtained as its attained dual optimizers. Equivalently $z\in \partial (h^{\ast }+k^{\ast })(p)$. Splitting the latter subdifferential into two separate ones needs a subdifferential sum rule qualification; solving the aggregate dual objective avoids that extra assumption.

For proper convex functions whose infimal convolution is well defined, $(f\square g{)}^{\ast }=f^{\ast }+g^{\ast }$. The proof separates a supremum over independent variables after writing $x=u+y$. No attainment of the infimum is needed.