3.2. The Legendre-Fenchel dual of a concave function [02KT]

Original official author HTML, exact retained edition. Historical TeX conversion verdicts remain unchanged. Cited-edition alignment and mathematical self-containment are not assessed.

Complete original source context · Original author HTML

3.2. The Legendre-Fenchel dual of a concave function

Let $N_{\mathbb{R}}$ and $M_{\mathbb{R}}$ be as in the previous section.

Set ${\underline{\mathbb{R}}}=\mathbb{R}\cup\{-\infty\}$ with the natural order and arithmetic operations. Unless otherwise stated, we will use the conventions $(-\infty)-(-\infty)=0$ and $0\cdot(-\infty)=0$ . A function $f\colon N_{\mathbb{R}}\to{\underline{\mathbb{R}}}$ is concave if

f(tu_{1}+(1-t)u_{2})\geq tf(u_{1})+(1-t)f(u_{2})

for all $u_{1},u_{2}\in N_{\mathbb{R}}$ , $0<t<1$ and $f$ is not identically $-\infty$ . Observe that a function $f$ is concave in our sense if and only if $-f$ is a proper convex function in the sense of [Roc70]. The effective domain ${\operatorname{dom}}(f)$ of such a function is the subset of points of $N_{\mathbb{R}}$ where $f$ takes finite values. It is a convex set. A concave function $f\colon N_{\mathbb{R}}\to{\underline{\mathbb{R}}}$ defines a concave function with finite values $f\colon{\operatorname{dom}}(f)\to\mathbb{R}$ . Conversely, if $f\colon C\to\mathbb{R}$ is a concave function defined on some convex set $C$ , we can extend it to the whole of $N_{\mathbb{R}}$ by declaring that its value at any point of $N_{\mathbb{R}}\setminus C$ is $-\infty$ . We will move freely from the point of view of concave functions on the whole of $N_{\mathbb{R}}$ with possibly infinite values to the point of view of real-valued concave functions on arbitrary convex sets.

A concave function is closed if it is upper semicontinuous. This includes the case of continuous concave functions defined on closed convex sets. Given an arbitrary concave function, there exists a unique minimal closed concave function above $f$ . This function is called the closure of $f$ and is denoted by ${\operatorname{cl}}(f)$ .

Let $f$ be a concave function on $N_{\mathbb{R}}$ . The Legendre-Fenchel dual of $f$ is the function

f^{\vee}\colon M_{\mathbb{R}}\longrightarrow{\underline{\mathbb{R}}},\quad x\longmapsto\inf_{u\in N_{\mathbb{R}}}(\langle x,u\rangle-f(u)).

It is a closed concave function. The Legendre-Fenchel duality is an involution between such functions: if $f$ is closed, then $f^{\vee\vee}=f$ [Roc70, Cor. 12.2.1]. In fact, for any concave function $f$ we have $f^{\vee\vee}={\operatorname{cl}}(f)$ .

The effective domain of $f^{\vee}$ is called the stability set of $f$ . It can be described as

\operatorname{stab}(f)={\operatorname{dom}}(f^{\vee})=\{x\in M_{\mathbb{R}}\mid\langle x,u\rangle-f(u)\text{ is bounded below}\}.

Example 3.16.

The indicator function of a convex set $C\subset N_{\mathbb{R}}$ is the concave function $\iota_{C}$ defined as $\iota_{C}(u)=0$ for $u\in C$ and $\iota_{C}(u)=-\infty$ for $u\not\in C$ . Observe that $\iota_{C}$ is the logarithm of the characteristic function of $C$ . This function is closed if and only if $C$ is a closed set.

The support function of a convex set $C$ is the function

\Psi_{C}\colon M_{\mathbb{R}}\longrightarrow\mathbb{R},\quad x\longmapsto\inf_{u\in C}\langle x,u\rangle.

It is a closed concave function. A function $f\colon M_{\mathbb{R}}\to\mathbb{R}$ is called conical if $f(\lambda x)=\lambda f(x)$ for all $\lambda\geq 0$ . The support function $\Psi_{C}$ is conical. The converse is also true: all conical closed concave functions are of the form $\Psi_{C}$ for a closed convex set $C$ .

We have $\iota_{C}^{\vee}=\Psi_{C}$ and $\Psi_{C}^{\vee}={\operatorname{cl}}(\iota_{C})=\iota_{{\overline{C}}}$ . Thus, the Legendre-Fenchel duality defines a bijective correspondence between indicator functions of closed convex subsets of $N_{\mathbb{R}}$ and closed concave conical functions on $M_{\mathbb{R}}$ .

Next result shows that the Legendre-Fenchel duality is monotonous.

Proposition 3.17.

Let $f$ and $g$ be concave functions such that $g(u)\leq f(u)$ for all $u\in N_{\mathbb{R}}$ . Then ${\operatorname{dom}}(g)\subset{\operatorname{dom}}(f)$ , $\operatorname{stab}(g)\supset\operatorname{stab}(f)$ and $g^{\vee}(x)\geq f^{\vee}(x)$ for all $x\in M_{\mathbb{R}}$ .

Proof.

It follows directly from the definitions. ∎

The Legendre-Fenchel duality is continuous with respect to uniform convergence.

Proposition 3.18.

Let $(f_{i})_{i\geq 1}$ be a sequence of concave functions which converges uniformly to a function $f$ . Then $f$ is a concave function and the sequence $(f_{i}^{\vee})_{i\geq 1}$ converges uniformly to $f^{\vee}$ . In particular, there is some $i_{0}\geq 1$ such that ${\operatorname{dom}}(f_{i})={\operatorname{dom}}(f)$ and $\operatorname{stab}(f_{i})=\operatorname{stab}(f)$ for all $i\geq i_{0}$ .

Proof.

It is a direct consequence of Proposition 3.17. ∎

The classical Legendre duality of strictly concave differentiable functions can be described in terms of the gradient map $\nabla f$ , called in this setting the ‘‘Legendre transform’’. We will next show that the Legendre transform can be extended to the general concave case as a correspondence between convex decompositions.

Let $f$ be a concave function on $N_{\mathbb{R}}$ . The sup-differential of $f$ at a point $u\in N_{\mathbb{R}}$ is defined as the set

\partial f(u)=\{x\in M_{\mathbb{R}}\mid\langle x,v-u\rangle\geq f(v)-f(u)\text{ for all }v\in N_{\mathbb{R}}\}.

For an arbitrary concave function, the sup-differential is a generalization of the gradient. In general, $\partial f(u)$ may contain more than one point, so the sup-differential has to be regarded as a multi-valued function.

We say that $f$ is sup-differentiable at a point $u\in N_{\mathbb{R}}$ if $\partial f(u)\neq\emptyset$ . The effective domain of $\partial f$ , denoted ${\operatorname{dom}}(\partial f)$ , is the set of points where $f$ is sup-differentiable. For a subset $E\subset N_{\mathbb{R}}$ we define

\partial f(E)=\bigcup_{u\in E}\partial f(u).

In particular, the image of $\partial f$ is defined as $\operatorname{im}(\partial f)=\partial f(N_{\mathbb{R}})$ .

The sup-differential $\partial f(u)$ is a closed convex set for all $u\in{\operatorname{dom}}(\partial f)$ . It is bounded if and only if $u\in\operatorname{ri}({\operatorname{dom}}(f))$ . Hence, in the particular case when ${\operatorname{dom}}(f)=N_{\mathbb{R}}$ , we have that $\partial f(u)$ is a bounded closed convex subset of $M_{\mathbb{R}}$ for all $u\in N_{\mathbb{R}}$ . The effective domain of the sup-differential is not necessarily convex but it differs very little from being convex, in the sense that it satisfies

(3.19)

\operatorname{ri}({\operatorname{dom}}(f))\subset{\operatorname{dom}}(\partial f)\subset{\operatorname{dom}}(f).

Let $f$ be a closed concave function and consider the pairing

(3.20)

P_{f}\colon M_{\mathbb{R}}\times N_{\mathbb{R}}\longrightarrow{\underline{\mathbb{R}}},\quad(u,x)\longmapsto f(u)+f^{\vee}(x)-\langle x,u\rangle.

This pairing satisfies $P_{f}(u,x)\leq 0$ for all $u,x$ .

Proposition 3.21.

Let $f$ be a closed concave function on $N_{\mathbb{R}}$ . For $u\in N_{\mathbb{R}}$ and $x\in M_{\mathbb{R}}$ , the following conditions are equivalent:

(1)

$x\in\partial f(u)$ ;
(2)

$u\in\partial f^{\vee}(x)$ ;
(3)

$P_{f}(u,x)=0$ .

Proof.

This is proved in [Roc70, Theorem 23.5]. ∎

If $f$ is closed, then $\operatorname{im}(\partial f)={\operatorname{dom}}(\partial f^{\vee})$ and so the image of the sup-differential is close to be a convex set, in the sense that

(3.22)

\operatorname{ri}(\operatorname{stab}(f))\subset\operatorname{im}(\partial f)\subset\operatorname{stab}(f).

Definition 3.23.

We denote by $\Pi(f)$ the collection of all sets of the form

C_{x}:=\partial f^{\vee}(x)

for some $x\in\operatorname{stab}(f)$ .

Lemma 3.24.

Let $x\in\operatorname{stab}(f)$ . Then $C_{x}=\{u\in N_{\mathbb{R}}\mid P_{f}(u,x)=0\}.$ In other words, the set $C_{x}$ is characterized by the condition

(3.25)

f(u)=\langle x,u\rangle-f^{\vee}(x)\text{ for }u\in C_{x}\quad\text{and}\quad f(u)<\langle x,u\rangle-f^{\vee}(x)\text{ for }u\not\in C_{x}.

Thus the restriction of $f$ to $C_{x}$ is an affine function with linear part given by $x$ , and $C_{x}$ is the maximal subset where this property holds.

Proof.

The first statement follows from the equivalence of (2) and (3) in Proposition 3.21. The second statement follows from the definition of $P_{f}$ and its non-positivity. ∎

The hypograph of a concave function $f$ is defined as the set

\operatorname{hypo}(f)=\{(u,\lambda)\mid u\in N_{\mathbb{R}},\lambda\leq f(u)\}\subset N_{\mathbb{R}}\times\mathbb{R}.

A face of the hypograph is called non-vertical if it projects injectively in $N_{\mathbb{R}}$ .

Proposition 3.26.

Let $f$ be a closed concave function on $N_{\mathbb{R}}$ . For a subset $C\subset N_{\mathbb{R}}$ , the following conditions are equivalent:

(1)

$C\in\Pi(f)$ ;
(2)

$C=\{u\in N_{\mathbb{R}}\mid x\in\partial f(u)\}$ for a $x\in M_{\mathbb{R}}$ ;
(3)

there exist $x_{C}\in M_{\mathbb{R}}$ and $\lambda_{C}\in\mathbb{R}$ such that the set $\{(u,\langle x_{C},u\rangle-\lambda_{C})\mid u\in C\}$ is an exposed face of the hypograph of $f$ .

In particular, the correspondence

C_{x}\mapsto\{(u,\langle x,u\rangle-f^{\vee}(x))\mid u\in C_{x}\}

is a bijection between $\Pi(f)$ and the set of non-vertical exposed faces of $\operatorname{hypo}(f)$ .

Proof.

The equivalence between the conditions (1) and (2) comes directly from Proposition 3.21. The equivalence with the condition (3) follows from (3.25). ∎

Proposition 3.27.

Let $f$ be a closed concave function. Then $\Pi(f)$ is a convex decomposition of ${\operatorname{dom}}(\partial f)$ .

Proof.

The collection of non-vertical exposed faces of $\operatorname{hypo}(f)$ forms a convex decomposition in $N_{\mathbb{R}}\times\mathbb{R}$ . Using Proposition 3.26 we obtain that $\Pi(f)$ is a convex decomposition of $|\Pi(f)|={\operatorname{dom}}(\partial f)$ . ∎

We need the following result in order to properly define the Legendre-Fenchel correspondence for an arbitrary concave function as a bijective correspondence between convex decompositions.

Lemma 3.28.

Let $f$ be a closed concave function and $C\in\Pi(f)$ . Then for any $u_{0}\in\operatorname{ri}(C)$ ,

\bigcap_{u\in C}\partial f(u)=\partial f(u_{0}).

Proof.

Fix $x_{0}\in{\operatorname{dom}}(\partial f^{\vee})$ such that $C=C_{x_{0}}$ and $u_{0}\in\operatorname{ri}(C)$ . Let $x\in\partial f(u_{0})$ . Then

(3.29)

\langle x,v-u_{0}\rangle\geq f(v)-f(u_{0})\quad\text{for all }v\in N_{\mathbb{R}}.

Let $u\in C$ . By (3.25), we have $f(u)-f(u_{0})=\langle x_{0},u-u_{0}\rangle$ and so the above inequality implies $\langle x,u-u_{0}\rangle\geq\langle x_{0},u-u_{0}\rangle.$ The fact $u_{0}\in\operatorname{ri}(C)$ implies $u_{0}+\lambda(u_{0}-u)\in C$ for some small $\lambda>0$ . Applying the same argument to this element we obtain the reverse inequality $\langle x,u-u_{0}\rangle\leq\langle x_{0},u-u_{0}\rangle$ and so

(3.30)

\langle x-x_{0},u-u_{0}\rangle=0.

In particular, $f(u)-f(u_{0})=\langle x_{0},u-u_{0}\rangle=\langle x,u-u_{0}\rangle$ and from (3.29) we obtain

\langle x,v-u\rangle=\langle x,v-u_{0}\rangle+f(u_{0})-f(u)\geq f(v)-f(u)\quad\text{for all }v\in N_{\mathbb{R}}.

Hence $x\in\bigcap_{u\in C}\partial f(u)$ and so $\partial f(u_{0})\subset\bigcap_{u\in C}\partial f(u)$ , which implies the stated equality. ∎

Definition 3.31.

Let $f$ be a closed concave function. The Legendre-Fenchel correspondence of $f$ is defined as

{\mathcal{L}}f\colon\Pi(f)\longrightarrow\Pi(f^{\vee}),\quad C\longmapsto\bigcap_{u\in C}\partial f(u).

By Lemma 3.28, ${\mathcal{L}}f(C)=\partial f(u_{0})$ for any $u_{0}\in\operatorname{ri}(C)$ . Hence,

{\mathcal{L}}f(C)\in\Pi(f^{\vee}).

Definition 3.32.

Let $E,E^{\prime}$ be subsets of $N_{\mathbb{R}}$ and $M_{\mathbb{R}}$ respectively, and $\Pi,\Pi^{\prime}$ convex decompositions of $E$ and $E^{\prime}$ , respectively. We say that $\Pi$ and $\Pi^{\prime}$ are dual convex decompositions if there exists a bijective map $\Pi\to\Pi^{\prime},C\mapsto C^{\ast}$ such that

(1)

for all $C,D\in\Pi$ we have $C\subset D$ if and only if $C^{\ast}\supset D^{\ast}$ ;
(2)

for all $C\in\Pi$ the sets $C$ and $C^{\ast}$ are contained in orthogonal affine spaces of $N_{\mathbb{R}}$ and $M_{\mathbb{R}}$ , respectively.

Theorem 3.33.

Let $f$ be a closed concave function, then ${\mathcal{L}}f$ is a duality between $\Pi(f)$ and $\Pi(f^{\vee})$ with inverse $({\mathcal{L}}f)^{-1}={\mathcal{L}}f^{\vee}$ .

Proof.

We will prove first that ${\mathcal{L}}f^{\vee}=({\mathcal{L}}f)^{-1}$ . Fix $C\in\Pi(f)$ and set $C^{\prime}={\mathcal{L}}f(C)$ . Let $y_{0}\in M_{\mathbb{R}}$ such that $C=C_{y_{0}}$ and let $u_{0}\in\operatorname{ri}(C)$ . Hence $u_{0}\in C_{y_{0}}=\partial f^{\vee}(y_{0})$ and so $y_{0}\in\partial f(u_{0})=C^{\prime}$ by Proposition 3.21 and Lemma 3.28. Hence

{\mathcal{L}}f^{\vee}({\mathcal{L}}f(C))={\mathcal{L}}f^{\vee}(C^{\prime})=\bigcap_{x\in C^{\prime}}\partial f^{\vee}(x)\subset\partial f^{\vee}(y_{0})=C.

On the other hand, let $x_{0}\in\operatorname{ri}(C^{\prime})$ . In particular, $x_{0}\in\partial f(u_{0})$ and so $u_{0}\in\partial f^{\vee}(x_{0})={\mathcal{L}}f^{\vee}(C^{\prime})$ for all $u_{0}\in C$ . It implies

C\subset{\mathcal{L}}f^{\vee}(C^{\prime})={\mathcal{L}}f^{\vee}({\mathcal{L}}f(C)).

Thus ${\mathcal{L}}f^{\vee}({\mathcal{L}}f(C))=C$ and applying the same argument to $f^{\vee}$ we conclude that ${\mathcal{L}}f^{\vee}=({\mathcal{L}}f)^{-1}$ and that ${\mathcal{L}}f$ is bijective.

Now we have to prove that ${\mathcal{L}}$ is a duality between $\Pi(f)$ and $\Pi(f^{\vee})$ . Let $C,D\in\Pi(f)$ such that $C\subset D$ . Clearly, ${\mathcal{L}}f(C)\supset{\mathcal{L}}f(D)$ . The reciprocal follows by applying the same argument to $f^{\vee}$ . The fact that $C$ and ${\mathcal{L}}f(C)$ lie in orthogonal affine spaces has already been shown during the proof of Lemma 3.28 above, see (3.30). ∎

Definition 3.34.

Let $f$ be a closed concave function. The pair of convex decompositions $(\Pi(f),\Pi(f^{\vee}))$ will be called the dual pair of convex decompositions induced by $f$ .

In particular, for $C\in\Pi(f)$ put $C^{*}:={\mathcal{L}}f(C)$ . For any $u_{0}\in\operatorname{ri}(C)$ and $x_{0}\in\operatorname{ri}(C^{*})$ , we have

C=\{u\in N_{\mathbb{R}}\mid P_{f}(u,x_{0})=0\}\quad\text{and}\quad C^{*}=\{x\in M_{\mathbb{R}}\mid P_{f}(u_{0},x)=0\}.

Following (3.25), the restrictions $f|_{C}$ and $f^{\vee}|_{C^{*}}$ are affine functions. Observe that we can recover the Legendre-Fenchel dual from the Legendre-Fenchel correspondence by writing, for $x\in C^{\ast}$ and any $u\in C$ ,

(3.35)

f^{\vee}(x)=\langle x,u\rangle-f(u).

Example 3.36.

Let $\|\cdot\|_{2}$ denote the Euclidean norm on $\mathbb{R}^{2}$ and $B_{1}$ the unit ball. Consider the concave function $f\colon B_{1}\to\mathbb{R}$ defined as $f(u)=-\|u\|_{2}$ . Then $\operatorname{stab}(f)=\mathbb{R}^{2}$ and the Legendre-Fenchel dual is the function defined by $f^{\vee}(x)=0$ if $\|x\|_{2}\leq 1$ and $f^{\vee}(x)=1-\|x\|_{2}$ otherwise. The decompositions $\Pi(f)$ and $\Pi(f^{\vee})$ consist of a collection of pieces of three different types and the Legendre-Fenchel correspondence ${\mathcal{L}}f\colon\Pi(f)\to\Pi(f^{\vee})$ is given, for $z\in S^{1}$ , by

{\mathcal{L}}f(\{0\})=B_{1},\quad{\mathcal{L}}f([0,1]\cdot z)=\{z\},\quad{\mathcal{L}}f(\{z\})=\mathbb{R}_{\geq 1}\cdot z.

In the above example both decompositions are in fact subdivisions. But this is not always the case, as shown by the next example.

Example 3.37.

Let $f\colon[0,1]\to\mathbb{R}$ the function defined by

f(u)=\begin{cases}-u\log(u),&\text{ if }0\leq u\leq\operatorname{e}^{-1},\\ \operatorname{e}^{-1},&\text{ if }\operatorname{e}^{-1}\leq u\leq 1-\operatorname{e}^{-1},\\ -(1-u)\log(1-u),&\text{ if }1-\operatorname{e}^{-1}\leq u\leq 1.\end{cases}

Then $\operatorname{stab}(f)=\mathbb{R}$ and the Legendre-Fenchel dual is the function $f^{\vee}(x)=x-\operatorname{e}^{x-1}$ for $x\leq 0$ and $f^{\vee}(x)=-\operatorname{e}^{-x-1}$ for $x\geq 0$ . Then ${\operatorname{dom}}(\partial f)=(0,1)$ and ${\operatorname{dom}}(\partial f^{\vee})=\mathbb{R}$ . Moreover,

\Pi(f)=(0,\operatorname{e}^{-1})\cup\{[\operatorname{e}^{-1},1-\operatorname{e}^{-1}]\}\cup(1-\operatorname{e}^{-1},1),\quad\Pi(f^{\vee})=\mathbb{R}.

The Legendre-Fenchel correspondence sends bijectively $(0,\operatorname{e}^{-1})$ to $\mathbb{R}_{>0}$ and $(1-\operatorname{e}^{-1},1)$ to $\mathbb{R}_{<0}$ , and sends the element $[\operatorname{e}^{-1},1-\operatorname{e}^{-1}]$ to the point $\{0\}$ . In this example, $\Pi(f)$ is not a subdivision while $\Pi(f^{\vee})$ is.