21.3 Legendre duality and convex envelopesEC0F5475F1C8

Proof. The conjugate is the supremum of the continuous affine functions $p\mapsto \langle p,x\rangle -F(x)$, $x\in \operatorname {dom}F$, so it is convex and lower semicontinuous. Since $\operatorname {dom}F\neq \varnothing $, we have $F^*(p)\geq \langle p,x_0\rangle -F(x_0)>-\infty $ for any $x_0\in \operatorname {dom}F$. By proposition 21.2.4, $F$ has a subgradient $p_0$ at some point $x_1\in \operatorname {ri}(\operatorname {dom}F)$, and then $F^*(p_0)=\langle p_0,x_1\rangle -F(x_1)<+\infty $. Thus $F^*$ is closed and proper. The definition of $F^*$ gives $F(x)\geq \langle p,x\rangle -F^*(p)$ for all $p$, that is, $F^{**}\leq F$.

We next show that $F^{**}=F$ when $F$ is closed. An affine function $\langle p,\cdot \rangle -c$ lies below $F$ if and only if $c\geq F^*(p)$. Hence $F^{**}$ is the supremum of all affine minorants of $F$, and it suffices to find, for every $x$ and every real $r<F(x)$, an affine minorant of $F$ whose value at $x$ exceeds $r$. The point $(x,r)$ does not belong to the closed convex set $\operatorname {epi}F$, so by lemma 21.2.3(1), applied in $N_{\mathbb R}\times \mathbb R$, there are $a\in M_{\mathbb R}$, $c\in \mathbb R$ and $\delta >0$ with

Letting $s\to +\infty $ shows that $c\geq 0$. If $c>0$, taking $s=F(y)$ gives the affine minorant $y\mapsto r+(\delta -\langle a,y-x\rangle )/c$, whose value at $x$ is $r+\delta /c>r$. If $c=0$, then $\langle a,y\rangle \geq \langle a,x\rangle +\delta $ for all $y\in \operatorname {dom}F$. Let $L_0$ be an affine minorant of $F$, which exists by the first paragraph. For $k>0$ the affine functions

are again minorants of $F$, since the added term is at most $-k\delta /2$ on $\operatorname {dom}F$, and their values at $x$ tend to $+\infty $ as $k\to \infty $. In both cases the required minorant exists, so $F^{**}=F$. For a general proper convex $F$, a continuous affine function lies below $F$ if and only if it lies below the largest lower semicontinuous minorant $\overline F$. Therefore $F^*=(\overline F)^*$, and since $\overline F$ is closed and proper by proposition 21.2.6, $F^{**}=(\overline F)^{**}=\overline F$.

Let $F$ be closed. By definition, $p\in \partial F(x)$ means that $x\in \operatorname {dom}F$ and $\langle p,y\rangle -F(y)\leq \langle p,x\rangle -F(x)$ for all $y$, that is, the supremum defining $F^*(p)$ is attained at $x$; equivalently, $F(x)+F^*(p)=\langle p,x\rangle $. (If $x\notin \operatorname {dom}F$, both conditions fail, since then $F(x)+F^*(p)=+\infty $.) Applying this to the closed proper function $F^*$ and using $F^{**}=F$, we find that $x\in \partial F^*(p)$ if and only if $F^*(p)+F(x)=\langle p,x\rangle $. This proves the equivalences. If $p\in \operatorname {ri}(\operatorname {dom}F^*)$, then $F^*$ has a subgradient $x$ at $p$ by proposition 21.2.4, and $p\in \partial F(x)$ by the equivalences; this is the first inclusion. If $p\in \partial F(x)$, then $F^*(p)=\langle p,x\rangle -F(x)<+\infty $, which gives the second. The closures coincide because $\operatorname {ri}(\operatorname {dom}F^*)$ is dense in $\operatorname {dom}F^*$ by lemma 21.2.3(4). Finally, $\chi _ P^*=h_ P$ by the definitions, and $\chi _ P$ is a closed proper convex function, so $h_ P^*=\chi _ P^{**}=\chi _ P$. $\square$

Proof. (1) The epigraph of a supremum is the intersection of the epigraphs. Let $(F_ i)$ be a decreasing net of convex functions with limit $F=\inf _ iF_ i$, let $x,y\in N_{\mathbb R}$ and $0<\lambda <1$, and let $a>F(x)$ and $b>F(y)$ be real numbers. Choose indices $i_1,i_2$ with $F_{i_1}(x)<a$ and $F_{i_2}(y)<b$, and an index $i$ following both. Then $F_ i(x)<a$ and $F_ i(y)<b$, and convexity of $\operatorname {epi}F_ i$ gives

Since $a$ and $b$ are arbitrary, this shows that $\operatorname {epi}F$ is convex; this also covers the case where $F(x)$ or $F(y)$ equals $-\infty $.

(2) If $H(x)<a$ and $H(x')<a'$, we can choose admissible combinations for $x$ and $x'$ with values below $a$ and $a'$; mixing them with weights $1-\lambda $ and $\lambda $ gives an admissible combination for $(1-\lambda )x+\lambda x'$ with value below $(1-\lambda )a+\lambda a'$. Hence $H$ is convex. Combinations with $q=1$ show $H\leq F_ i$ for each $i$. If $G$ is convex and $G\leq F_ i$ for all $i$, then for every admissible combination the points $(x_ j,F_{i_ j}(x_ j))$ lie in $\operatorname {epi}G$, and so does their convex combination with the weights $\lambda _ j$, since a convex set contains the convex combinations of its points; that is,

Hence $G\leq H$. For the conjugate, the supremum defining $H^*(p)$ is the supremum over all admissible combinations of

and combinations with $q=1$ give equality. Since affine functions are convex, an affine function lies below $H$ if and only if it lies below $\inf _ iF_ i$. Suppose that $H$ has an affine minorant. Then $H$ is proper, so $\overline H$ is a closed proper convex function by proposition 21.2.6, and $\overline H=H^{**}=(\sup _ iF_ i^*)^*$ by theorem 21.3.2. A lower semicontinuous convex function below $\inf _ iF_ i$ lies below $H$, and therefore below $\overline H$.

(3) Convexity of $F\mathbin \square G$ follows as in (2), by mixing decompositions $x=y+z$ and $x'=y'+z'$ whose values $F(y)+G(z)$ are close to the infima. The two suprema over $y$ and $z$ in

are independent, which gives the conjugate formula.

(4) If $n=0$, then $F$ and $G$ are constants and both sides equal $-F(0)-G(0)$; so let $n\geq 1$. Let $J(p)=\inf _{q+r=p}(F^*(q)+G^*(r))$. Each conjugate is bounded below by minus its value at the origin: $F^*\geq -F(0)$ and $G^*\geq -G(0)$. Moreover, for every $R>0$, choosing $x$ with $|x|=R$ and $\langle q,x\rangle =R|q|$ gives

and the analogous bound holds for $G^*$. Consequently, if $p$ stays bounded and $F^*(q)+G^*(r)$ stays bounded above, then $q$ and $r=p-q$ stay bounded: for instance $F^*(q)\leq F^*(q)+G^*(r)+G(0)$, and the last bound with $R=1$ controls $|q|$. Lower semicontinuity of $F^*$ and $G^*$ therefore implies that the infimum defining $J(p)$ is attained whenever it is finite: a minimizing sequence of decompositions has a convergent subsequence. The same argument, applied to $p_ k\to p$ and decompositions attaining $J(p_ k)$, shows that $J$ is lower semicontinuous. By (3), $J=F^*\mathbin \square G^*$ is convex; it is bounded below by $-F(0)-G(0)$, and it is proper, since $J(q_0+r_0)\leq F^*(q_0)+G^*(r_0)<+\infty $ for subgradients $q_0\in \partial F(0)$ and $r_0\in \partial G(0)$. Finite convex functions are continuous, so $F$ and $G$ are closed and $F^{**}=F$, $G^{**}=G$. By (3), $J^*=F^{**}+G^{**}=F+G$, and theorem 21.3.2 gives $J=J^{**}=(F+G)^*$. $\square$