3.4. The differentiable case [02M0]

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.4. The differentiable case

In this section we make explicit the Legendre-Fenchel duality for smooth concave functions, following [Roc70, Chapter 26].

In the differentiable and strictly concave case, the decompositions $\Pi(f)$ and $\Pi(f^{\vee})$ consist of the collection of all points of ${\operatorname{dom}}(\partial f)$ and of ${\operatorname{dom}}(\partial f^{\vee})$ respectively. The Legendre-Fenchel correspondence agrees with the gradient map, and it is called the Legendre transform in this context.

Recall that a function $f\colon N_{\mathbb{R}}\to{\underline{\mathbb{R}}}$ is differentiable at a point $u\in N_{\mathbb{R}}$ with $f(u)>-\infty$ , if there exists some linear form $\nabla f(u)\in M_{\mathbb{R}}$ such that

f(v)=f(u)+\langle\nabla f(u),v-u\rangle+o(||v-u||),

where $||\cdot||$ denotes any fixed norm on $N_{\mathbb{R}}$ . This linear form $\nabla(f)(u)$ is the gradient of $f$ in the classical sense. It can be shown that a concave function $f$ is differentiable at a point $u\in{\operatorname{dom}}(f)$ if and only if $\partial f(u)$ consists of a single element. If this is the case, then $\partial f(u)=\{\nabla f(u)\}$ [Roc70, Theorem 25.1]. Hence, the gradient and the sup-differential agree in the differentiable case.

Let $C\subset N_{\mathbb{R}}$ be a convex set. A function $f\colon C\to\mathbb{R}$ is strictly concave if $f(tu_{1}+(1-t)u_{2})>tf(u_{1})+(1-t)f(u_{2})$ for all different $u_{1},u_{2}\in C$ and $0<t<1$ .

Definition 3.51.

Let $C\subset N_{\mathbb{R}}$ be an open convex set and $||\cdot||$ any fixed norm on $M_{\mathbb{R}}$ . A differentiable concave function $f\colon C\to\mathbb{R}$ is of Legendre type if it is strictly concave and $\lim_{i\to\infty}\|\nabla f(u_{i})\|\to\infty$ for every sequence $(u_{i})_{i\geq 1}$ converging to a point in the boundary of $C$ . In particular, any differentiable and strictly concave function on $N_{\mathbb{R}}$ is of Legendre type.

The stability set of a function of Legendre type has maximal dimension. Therefore its relative interior agrees with its interior and, in this case, we will use the classical notation $\operatorname{stab}(f)^{\circ}$ for the interior of $\operatorname{stab}(f)$ .

The following result summarizes the basics properties of the Legendre-Fenchel duality acting on functions of Legendre type.

Theorem 3.52.

Let $f\colon C\to\mathbb{R}$ be a concave function of Legendre type defined on an open set $C\subset N_{\mathbb{R}}$ and let $D=\nabla f(C)\subset M_{\mathbb{R}}$ be the image of the gradient map. Then

(1)

$D=\operatorname{stab}(f)^{\circ}$ ;
(2)

$f^{\vee}|_{D}$ is a concave function of Legendre type;
(3)

$\nabla f\colon C\to D$ is a homeomorphism and $(\nabla f)^{-1}=\nabla f^{\vee}$ ;
(4)

for all $x\in D$ we have $f^{\vee}(x)=\langle x,(\nabla f)^{-1}(x)\rangle-f((\nabla f)^{-1}(x))$ .

Proof.

This follows from [Roc70, Theorem 26.5]. ∎

Example 3.53.

Consider the function

f_{\operatorname{FS}}\colon\mathbb{R}^{n}\longrightarrow\mathbb{R},\quad u\longmapsto-\frac{1}{2}\log\Big(1+\sum_{i=1}^{n}\operatorname{e}^{-2u_{i}}\Big).

Let $\Delta^{n}=\{(x_{1},\dots,x_{n})\subset\mathbb{R}^{n}\mid x_{i}\geq 0,\sum x_{i}\leq 1\}$ be the standard simplex of $\mathbb{R}^{n}$ . For $(x_{1},\dots,x_{n})\in\Delta^{n}$ , write $x_{0}=1-\sum_{i=1}^{n}x_{i}$ and set

(3.54)

\varepsilon_{n}\colon\Delta^{n}\longrightarrow\mathbb{R},\quad x\longmapsto-\sum_{i=0}^{m}x_{i}\log(x_{i}).

We have $\displaystyle\nabla f_{{\operatorname{FS}}}(u)=\frac{1}{1+\sum_{i=1}^{n}\operatorname{e}^{-2u_{i}}}\left(\operatorname{e}^{-2u_{1}},\dots,\operatorname{e}^{-2u_{n}}\right)$ and so

\displaystyle\frac{1}{2}\varepsilon_{n}(\nabla f_{{\operatorname{FS}}}(u))

\displaystyle=\frac{\sum_{i=1}^{n}\operatorname{e}^{-2u_{i}}u_{i}}{1+\sum_{i=1}^{n}\operatorname{e}^{-2u_{i}}}+\frac{1}{2}\log\Big(1+\sum_{i=1}^{n}\operatorname{e}^{-2u_{i}}\Big)=\langle\nabla f_{\operatorname{FS}}(u),u\rangle-f_{\operatorname{FS}}(u),

which shows that $\operatorname{stab}(f_{{\operatorname{FS}}})=\Delta^{n}$ and that $f_{\operatorname{FS}}^{\vee}=\frac{1}{2}\varepsilon_{n}$ .

The fact that the sup-differential agrees with the gradient and is single-valued can simplify some statements. It is interesting to make explicit the computation of the Legendre-Fenchel dual of the inverse image by an affine map of a concave function of Legendre type.

Proposition 3.55.

Let $A\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ be an affine map defined as $A=H+u_{0}$ for an injective linear map $H$ and a point $u_{0}\in N_{\mathbb{R}}$ . Let $f\colon C\to\mathbb{R}$ be a concave function of Legendre type defined on an open convex set $C\subset N_{\mathbb{R}}$ such that $C\cap\operatorname{im}(A)\not=\emptyset$ . Then $A^{*}f$ is a concave function of Legendre type on $A^{-1}(C)$ ,

\operatorname{stab}(A^{\ast}f)^{\circ}=\operatorname{im}(\nabla(A^{*}f))=H^{\vee}(\operatorname{im}(\nabla f))=H^{\vee}(\operatorname{stab}(f)^{\circ}),

and, for all $v\in A^{-1}C$ ,

(A^{\ast}f)^{\vee}(\nabla(A^{\ast}f)(v))=f^{\vee}(\nabla f(Av))-\langle\nabla f(Av),u_{0}\rangle.

Moreover, there is a section $\imath_{A,f}$ of $H^{\vee}|_{\operatorname{stab}(f)^{\circ}}$ such that the diagram

(3.56)

\begin{split}\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 6.68056pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&&&\cr&&&&\cr&&&&\crcr}}}\ignorespaces{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 30.68056pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{A^{-1}C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 44.9521pt\raise-31.77112pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-2.39168pt\hbox{$\scriptstyle{A}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 44.9521pt\raise-56.26447pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 4.61508pt\raise-9.61292pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.99155pt\hbox{$\scriptstyle{A^{\ast}f}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 6.68056pt\raise-27.1882pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 75.80656pt\raise 6.54709pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.79709pt\hbox{$\scriptstyle{\nabla(A^{\ast}f)}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 113.22365pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 83.22365pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 113.22365pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{\operatorname{stab}(A^{\ast}f)^{\circ}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 120.53372pt\raise-31.77112pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-0.4903pt\hbox{$\scriptstyle{\imath_{A,f}}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 141.02927pt\raise-55.59778pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 162.78406pt\raise-9.19276pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-2.0228pt\hbox{$\scriptstyle{(A^{\ast}f)^{\vee}}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 192.83488pt\raise-28.29074pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern 196.51544pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-6.68056pt\raise-31.93112pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{\mathbb{R}}$}}}}}}}{\hbox{\kern 41.9521pt\raise-31.93112pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 83.22365pt\raise-31.93112pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 138.02927pt\raise-31.93112pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 192.83488pt\raise-31.93112pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{\mathbb{R}}$}}}}}}}{\hbox{\kern-3.0pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 38.02086pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 13.3779pt\raise-53.84778pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.75pt\hbox{$\scriptstyle{f}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 6.68056pt\raise-36.62186pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 83.62549pt\raise-69.65334pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-1.75pt\hbox{$\scriptstyle{\nabla f}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 119.27226pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 83.22365pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 119.27226pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{\operatorname{stab}(f)^{\circ}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 163.9963pt\raise-54.31502pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise-2.21725pt\hbox{$\scriptstyle{f^{\vee}-u_{0}}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern 192.83488pt\raise-35.53888pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern 196.51544pt\raise-63.54224pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.55554pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{split}

commutes.

Proof.

This follows readily from Proposition 3.46. ∎

The section $\imath_{A,f}$ embeds $\operatorname{stab}(A^{\ast}f)^{\circ}$ as a real submanifold of $\operatorname{stab}(f)^{\circ}$ . Varying $u_{0}$ in a suitable space of parameters, we obtain a foliation of $\operatorname{stab}(f)^{\circ}$ by “parallel” submanifolds. We illustrate this phenomenon with an example in dimension 2.

Example 3.57.

Consider the function $f\colon\mathbb{R}^{2}\to\mathbb{R}$ given by

f(u_{1},u_{2})=-\frac{1}{2}\log\left(1+\operatorname{e}^{-2u_{1}}+\operatorname{e}^{-4u_{1}-2u_{2}}+\operatorname{e}^{-2u_{1}-4u_{2}}\right).

It is a concave function of Legendre type whose stability set is the polytope $\Delta=\operatorname{conv}((0,0),(1,0),(2,1),(1,2))$ . The restriction of its Legendre-Fenchel dual to $\Delta^{\circ}$ is also a concave function of Legendre type.

For $c\in\mathbb{R}$ , consider the affine map

A_{c}\colon\mathbb{R}\to\mathbb{R}^{2},\quad u\longmapsto(-u,u+c).

We write $A_{c}=H+(0,c)$ for a linear function $H$ . The dual of $H$ is the function $H^{\vee}\colon\mathbb{R}^{2}\to\mathbb{R}$ , $(x_{1},x_{2})\mapsto x_{2}-x_{1}$ . Then $\operatorname{stab}(A_{c}^{*}f)^{\circ}=H^{\vee}(\Delta^{\circ})$ is the open interval $(-1,1)$ . By Proposition 3.55, there is a map $\imath_{A_{c},f}$ embedding $(-1,1)$ into $\Delta^{\circ}$ in such a way that $\imath_{A_{c},f}\circ\nabla(A_{c}^{*}f)=(\nabla f)\circ A_{c}$ . For $u\in\mathbb{R}$ ,

	$\displaystyle\nabla(A_{c}^{*}f)(u)$	$\displaystyle=\frac{\operatorname{e}^{-2u-4c}-\operatorname{e}^{2u}-\operatorname{e}^{2u-2c}}{1+\operatorname{e}^{2u}+\operatorname{e}^{2u-2c}+\operatorname{e}^{-2u-4c}}\in(-1,1),$
	$\displaystyle(\nabla f)\circ A_{c}(u)$	$\displaystyle=\frac{\left(\operatorname{e}^{2u}+2\operatorname{e}^{2u-2c}+\operatorname{e}^{-2u-4c},\operatorname{e}^{2u-2c}+2\operatorname{e}^{-2u-4c}\right)}{1+\operatorname{e}^{2u}+\operatorname{e}^{2u-2c}+\operatorname{e}^{-2u-4c}}\in\Delta^{\circ}.$

From this, we compute $\imath_{A_{c},f}(x)=\left(x_{1},x_{2}\right)$ with

\left\{\begin{aligned} x_{1}&=\frac{-\operatorname{e}^{-2c}}{2(1+\operatorname{e}^{-2c})}x+\frac{2+3\operatorname{e}^{-2c}}{2(1+\operatorname{e}^{-2c})}\left(\frac{x^{2}}{\sqrt{\rho_{c}^{2}+(1-\rho_{c}^{2})x^{2}}+\rho_{c}}+\frac{\rho_{c}}{1+\rho_{c}}\right),\\ x_{2}&=\frac{2+\operatorname{e}^{-2c}}{2(1+\operatorname{e}^{-2c})}x+\frac{2+3\operatorname{e}^{-2c}}{2(1+\operatorname{e}^{-2c})}\left(\frac{x^{2}}{\sqrt{\rho_{c}^{2}+(1-\rho_{c}^{2})x^{2}}+\rho_{c}}+\frac{\rho_{c}}{1+\rho_{c}}\right),\end{aligned}\right.

where we have set $\rho_{c}=2\operatorname{e}^{-2c}\sqrt{1+\operatorname{e}^{-2c}}$ for short. In particular, the image of the map $\imath_{A_{c},f}$ is an arc of conic: namely the intersection of $\Delta^{\circ}$ with the conic of equation

(x_{2}-x_{1})^{2}=(1-\rho_{c}^{2})L_{c}(x_{1},x_{2})^{2}+2\rho_{c}L_{c}(x_{1},x_{2}),

with $L_{c}(x_{1},x_{2})=\frac{2+\operatorname{e}^{-2c}}{2+3\operatorname{e}^{-2c}}x_{1}+\frac{\operatorname{e}^{-2c}}{2+3\operatorname{e}^{-2c}}x_{2}-\frac{\rho_{c}}{1+\rho_{c}}$ . Varying $c\in\mathbb{R}$ , these arcs of conics form a foliation of $\Delta^{\circ}$ , they all pass through the vertex $(1,2)$ as $x\to 1$ , and their other end as $x\to-1$ parameterizes the relative interior of the edge $\operatorname{conv}((1,0),(2,1))$ , see Figure 2.

Refer to caption — Figure 2. A foliation of $\Delta^{\circ}$ by curves