Infimal convolution and Moreau envelopes

For functions f and g on $\mathbb R^d$, their infimal convolution at x is the infimum over z of f(z)+g(x−z). Convexity of both functions gives convexity of this value function where it is a proper extended-real function, but properness and attainment do not follow automatically. With f(z)=exp(z) and g identically zero, the value is zero at every x, yet no finite z attains it. With f(z)=z and g(w)=−w, the value is negative infinity everywhere. Both input functions in the second example are proper closed convex.

Conjugation exchanges infimal convolution with addition whenever the extended-value expressions are well-defined: the supremum over x and the infimum decomposition can be reparameterized by the independent components z and w. This identity does not itself say that the original infimum is attained or that the infimal convolution is closed. Such details become especially important when attempting to reverse the relation through biconjugation. The quadratic regularization used next supplies stronger structure than a general decomposition problem, so its existence and smoothness conclusions should not be generalized indiscriminately.

Let f be proper lower semicontinuous convex on finite-dimensional Euclidean space. For every x and λ>0, the quadratic-regularized objective has a unique minimizer, denoted prox_{λf}(x). A proper closed convex function admits an affine lower bound. Adding the positive quadratic to that bound prevents escape to infinity, yielding compact sublevels and existence. Strong convexity of the quadratic then gives uniqueness. This reasoning explains why a proximal point exists even when f itself has no minimizer or an unbounded effective domain.

The optimality relation is (x−z)/λ∈∂f(z). It locates the supporting slope at the new point z, unlike an explicit gradient step that uses a slope at the old point x. For f(z)=α|z| with α>0, considering positive, negative and zero candidates yields soft thresholding: keep the sign of x and reduce its magnitude by λα, stopping at zero. For an indicator of a nonempty closed convex set, the proximal map is the nearest-point projection, independent of λ because multiplying a zero-or-infinity indicator by a positive scalar does not alter feasibility.

The envelope is finite and continuously differentiable everywhere, with gradient (x−prox_{λf}(x))/λ. This gradient is Lipschitz with constant at most 1/λ. A full proof uses the firm nonexpansiveness of the proximal map, developed in the next lesson, together with the minimizing inequalities for nearby input points. The differentiability statement is not obtained by differentiating the original nonsmooth f. It arises because the quadratic forces a unique well-behaved minimizing output. The same results extend to proper lower semicontinuous convex functions on real Hilbert spaces.

The envelope lies below f because choosing z=x is allowed whenever f(x) is finite. Their infimum values agree, and their minimizer sets coincide, including the possibility that both sets are empty. Indeed, a zero envelope gradient means the proximal output equals its input, and the optimality relation then gives zero in ∂f. Smoothing does not manufacture a minimizer when the original problem lacks one. It changes the function values and geometry away from the minimizer, so an envelope value should not be reported as the original objective value without also evaluating f at the relevant point.