21.11.21 Legendre transform67B012704E18

Proof. For proper $F$, all assertions are the finite-dimensional Fenchel theorem, whose separation proof is given earlier: $F^*$ is closed and proper, $(\operatorname{cl}F)^*=F^*$, and $F^{**}=\operatorname{cl}F$.

For completeness consider improper convex functions. If $F\equiv+\infty$, then $F^*\equiv-\infty$ and $F^{**}\equiv+\infty$. Otherwise an improper $F$ takes $-\infty$ somewhere, so every $F^*(p)$ is $+\infty$, its biconjugate is identically $-\infty$, and this is exactly the closure prescribed in the definition. Its conjugate is again identically $+\infty$. Neither conjugate is proper in these improper cases. This proves the equivalence of properness and all the identities also at the extended-valued extremes.

Proof. Put $H=\operatorname{cl}\operatorname{CE}F$. Since $H\leq F$, order reversal gives $H^*\geq F^*$. Fix $p$ with $F^*(p)$ finite. The affine function $\ell(x)=\langle p,x\rangle-F^*(p)$ lies below $F$, hence below its convex envelope and below its lower semicontinuous regularization, because $\ell$ itself is continuous. Thus $\langle p,x\rangle-H(x)\leq F^*(p)$ for all $x$, proving $H^*(p)\leq F^*(p)$.

If $F^*(p)=+\infty$, the reverse inequality already gives equality. If $F^*(p)=-\infty$, then $F$ is identically $+\infty$; its closed convex envelope is also identically $+\infty$, and the equality is immediate. This treats every possible value of the conjugate.

Proof. Subgradients at points outside the effective domain are empty by definition. On the relative interior, existence and the directional formula follow from local convex regularity applied in the affine span $A$ of the domain. To view a subgradient as a functional on $N$, extend its restriction to the direction space of $A$ by a linear functional. Any functional vanishing on that direction space may be added without changing the subgradient inequality. Thus for a direction outside that space the supremum in the directional formula is $+\infty$, just as the one-sided directional derivative is; for tangent directions it is the relative formula.

At an interior point of the domain, local Lipschitz continuity bounds all subgradients: if $|F(x+v)-F(x)|\leq L|v|$ for small $v$, the subgradient inequality for $v$ and $-v$ gives $|\langle p,v\rangle|\leq L|v|$, hence $|p|\leq L$. Conversely, suppose the subgradient set is nonempty at a point $x$ of the domain which is not interior. A supporting hyperplane to the closure of the convex domain at $x$ supplies a nonzero $q$ with $\langle q,y-x\rangle\leq0$ for every $y$ in the domain. If $p$ is a subgradient, then so is $p+tq$ for every $t\geq0$, so the set is unbounded. Supporting hyperplanes also exist when the domain lies in a proper affine subspace, by taking an annihilating functional. This proves the final equivalence.

Proof. If $p\in\partial F(x)$, the subgradient inequality gives $F^*(p)=\langle p,x\rangle-F(x)<+\infty$, proving the first inclusion. Now assume $F$ is closed and let $p$ lie in the relative interior of $\operatorname{Dom}F^*$. The conjugate is closed and proper by Fenchel duality, so it has a subgradient $x$ at $p$. The same duality theorem gives $p\in\partial F(x)$. Thus the relative interior is contained in the subgradient image. Taking closures in the two inclusions and using that a nonempty convex set has the same closure as its relative interior proves the equality of closures.

Proof. For every decomposition $p=\sum_i p_i$, the defining inequalities for the conjugates give $(\sum_iF_i)^*(p)\leq\sum_iF_i^*(p_i)$. It remains to prove the reverse inequality when the left side is finite. The case $r=1$ is immediate.

For $r\geq2$, put \[V(z_1,\ldots,z_{r-1})=\inf_x\left\{\sum_{i<r}F_i(x+z_i)+F_r(x)-\langle p,x\rangle\right\}.\] This is convex, being an infimum over the fibers of a convex epigraph. Its value at zero is $-(\sum_iF_i)^*(p)$, which is finite. Choose $x_0$ in the common relative interior in the hypothesis. The product of the effective domains has $(x_0,\ldots,x_0)$ in its relative interior. The linear map $(x_1,\ldots,x_r)\mapsto(x_1-x_r,\ldots,x_{r-1}-x_r)$ maps a relative neighborhood of this point onto a relative neighborhood of zero in its image affine span: a surjective linear map between finite-dimensional spaces has a continuous linear right inverse. Consequently zero lies in the relative interior of $\operatorname{Dom}V$.

The function $V$ cannot take $-\infty$ anywhere. If it did, combining that point with a point of its effective domain on the opposite side of zero would force $V(0)=-\infty$. It is therefore proper, and existence of supporting slopes gives $p_1,\ldots,p_{r-1}$ with $V(z)\geq V(0)+\sum_{i<r}\langle p_i,z_i\rangle$. Set $p_r=p-\sum_{i<r}p_i$. Substituting arbitrary $x_i=x+z_i$ in this inequality yields \[\sum_i\bigl(F_i(x_i)-\langle p_i,x_i\rangle\bigr)\geq V(0).\] Taking independent infima proves $\sum_iF_i^*(p_i)\leq-V(0)=(\sum_iF_i)^*(p)$. Together with the first inequality this is equality. If the conjugate on the left is $+\infty$, the first inequality forces every decomposition cost to be $+\infty$, so the formula still holds.