3. The Legendre-Fenchel duality [02KA]

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. The Legendre-Fenchel duality

In this section we explain the notions of convex analysis that we will use in our study of the arithmetic of toric varieties. The central theme is the Legendre-Fenchel duality of concave functions. A basic reference in this subject is the classical book by Rockafellar [Roc70] and we will refer to it for many of the proofs.

Although the usual references in the literature deal with convex functions, we will work instead with concave functions. These are the functions which arise in the theory of toric varieties. In this respect, we remark that the functions which are called “convex” in the classical books on toric varieties [KKMS73, Ful93] are concave in the sense of convex analysis.

3.1. Convex sets and convex decompositions

Let $N_{\mathbb{R}}\simeq\mathbb{R}^{n}$ be a real vector space of dimension $n$ and $M_{\mathbb{R}}=N_{\mathbb{R}}^{\vee}$ its dual space. The pairing between $x\in M_{\mathbb{R}}$ and $u\in N_{\mathbb{R}}$ will be alternatively denoted by $\langle x,u\rangle$ , $x(u)$ or $u(x)$ .

A non-empty subset $C$ of $N_{\mathbb{R}}$ is convex if, for each pair of points $u_{1},u_{2}\in C$ , the line segment

{\overline{u_{1}u_{2}}}=\{tu_{1}+(1-t)u_{2}\mid 0\leq t\leq 1\}

is contained in $C$ . Throughout this text, convex sets are assumed to be non-empty. A non-empty subset $\sigma\subset N_{\mathbb{R}}$ is a cone if $\lambda\sigma=\sigma$ for all $\lambda\in\mathbb{R}_{>0}$ .

The affine hull of a convex set $C$ , denoted $\operatorname{aff}(C)$ , is the minimal affine space which contains it. The dimension of $C$ is defined as the dimension of its affine hull. The relative interior of $C$ , denoted $\operatorname{ri}(C)$ , is defined as the interior of $C$ relative to its affine hull. The recession cone of $C$ , denoted by $\operatorname{rec}(C)$ , is the set

\operatorname{rec}(C)=\{u\in N_{\mathbb{R}}\mid C+u\subset C\}.

It is a cone of $N_{\mathbb{R}}$ . The cone of $C$ is defined as

\operatorname{c}(C)={\overline{\mathbb{R}_{>0}(C\times\{1\})}}\subset N_{\mathbb{R}}\times\mathbb{R}_{\geq 0}.

It is a closed cone. If $C$ is closed, then $\operatorname{rec}(C)=\operatorname{c}(C)\cap(N_{\mathbb{R}}\times\{0\})$ .

Definition 3.1.

Let $C$ be a convex set. A convex subset $F\subset C$ is called a face of $C$ if, for every closed line segment ${\overline{u_{1}u_{2}}}\subset C$ such that $\operatorname{ri}({\overline{u_{1}u_{2}}})\cap F\not=\emptyset$ , the inclusion ${\overline{u_{1}u_{2}}}\subset F$ holds. A face of $C$ of codimension 1 is called a facet. A non-empty subset $F\subset C$ is called an exposed face of $C$ if there exists $x\in M_{\mathbb{R}}$ such that

F=\{u\in C\mid\langle x,u\rangle\leq\langle x,v\rangle,\,\forall v\in C\}.

Any exposed face of a convex set is a face, and the facets of a convex set are always exposed. However, a convex set may have faces which are not exposed. For instance, think about the four points of junction of the straight lines and bends of the boundary of the inner area of a racing track in a stadium.

Definition 3.2.

Let $\Pi$ be a non-empty collection of convex subsets of $N_{\mathbb{R}}$ . The collection $\Pi$ is called a convex subdivision if it satisfies the conditions:

(1)

every face of an element of $\Pi$ is also in $\Pi$ ;
(2)

every two elements of $\Pi$ are either disjoint or they intersect in a common face.

If $\Pi$ satisfies only (2), then it is called a convex decomposition. The support of $\Pi$ is defined as the set $|\Pi|=\bigcup_{C\in\Pi}C$ . We say that $\Pi$ is complete if its support is the whole of $N_{\mathbb{R}}$ . For a given set $E\subset N_{\mathbb{R}}$ , we say that $\Pi$ is a convex subdivision (or decomposition) in $E$ whenever $|\Pi|\subset E$ . A convex subdivision in $E$ is called complete if $|\Pi|=E$ .

For instance, the collection of all faces of a convex set defines a convex subdivision of this set. The collection of all exposed faces of a convex set is a convex decomposition, but it is not necessarily a convex subdivision.

In this text, we will be mainly concerned with the polyhedral case.

Definition 3.3.

A convex polyhedron of $N_{\mathbb{R}}$ is a convex set defined as the intersection of a finite number of closed halfspaces. It is called strongly convex if it does not contain any line. A convex polyhedral cone is a convex polyhedron $\sigma$ such that $\lambda\sigma=\sigma$ for all $\lambda>0$ . A polytope is a bounded convex polyhedron.

For a convex polyhedron, there is no difference between faces and exposed faces.

By the Minkowski-Weyl theorem, polyhedra can be explicitly described in two dual ways, either by the H-representation, as an intersection of half-spaces, or by the V-representation, as the Minkowski sum of a cone and a polytope [Roc70, Theorem 19.1]. An H-representation of a polyhedron $\Lambda$ in $N_{\mathbb{R}}$ is a finite set of affine equations $\{(a_{j},\alpha_{j})\}_{1\leq j\leq k}\subset M_{\mathbb{R}}\times\mathbb{R}$ so that

(3.4)

\Lambda=\bigcap_{1\leq j\leq k}\{u\in N_{\mathbb{R}}\mid\langle a_{j},u\rangle+\alpha_{j}\geq 0\}.

With this representation, the recession cone can be written as

\operatorname{rec}(\Lambda)=\bigcap_{1\leq j\leq k}\{u\in N_{\mathbb{R}}\mid\langle a_{j},u\rangle\geq 0\}.

A V-representation of a polyhedron $\Lambda^{\prime}$ in $N_{\mathbb{R}}$ consists in a set of vectors $\{b_{j}\}_{1\leq j\leq k}$ in the tangent space $T_{0}N_{\mathbb{R}}(\simeq N_{\mathbb{R}})$ and a non-empty set of points $\{b_{j}\}_{k+1\leq j\leq l}\subset N_{\mathbb{R}}$ such that

(3.5)

\Lambda^{\prime}=\operatorname{cone}(b_{1},\dots,b_{k})+\operatorname{conv}(b_{k+1},\dots,b_{l})

where

\operatorname{cone}(b_{1},\dots,b_{k}):=\bigg\{\sum_{j=1}^{k}\lambda_{j}b_{j}\bigg|\ \lambda_{j}\geq 0\bigg\}

is the cone generated by the given vectors (with the convention that $\operatorname{cone}(\emptyset)=\{0\}$ ) and

\operatorname{conv}(b_{k+1},\dots,b_{l}):=\bigg\{\sum_{j=k+1}^{l}\lambda_{j}b_{j}\bigg|\ \lambda_{j}\geq 0,\ \sum_{j=k+1}^{l}\lambda_{j}=1\bigg\}

is the convex hull of the given set of points. With this second representation, the recession cone can be obtained as

\operatorname{rec}(\Lambda^{\prime})=\operatorname{cone}(b_{1},\dots,b_{k}).

Definition 3.6.

A polyhedral complex in $N_{\mathbb{R}}$ is a finite convex subdivision whose elements are convex polyhedra. A polyhedral complex is called strongly convex if all of its polyhedra are strongly convex. It is called conic if all of its elements are cones. A strongly convex conic polyhedral complex is called a fan. If $\Pi$ is a polyhedral complex, we will denote by $\Pi^{i}$ the subset of $i$ -dimensional polyhedra of $\Psi$ . In particular, if $\Sigma$ is a fan, $\Sigma^{i}$ is its subset of $i$ -dimensional cones.

There are two natural processes for linearizing a polyhedral complex.

Definition 3.7.

The recession of $\Pi$ is defined as the collection of polyhedral cones of $N_{\mathbb{R}}$ given by

\operatorname{rec}(\Pi)=\{\operatorname{rec}(\Lambda)\mid\Lambda\in\Pi\}.

The cone of $\Pi$ is defined as the collection of cones in $N_{\mathbb{R}}\times\mathbb{R}$ given by

\operatorname{c}(\Pi)=\big\{\operatorname{c}(\Lambda)\mid\Lambda\in\Pi\big\}\cup\big\{\sigma\times\{0\}\mid\sigma\in\operatorname{rec}(\Pi)\big\}.

It is natural to ask whether the recession or the cone of a given polyhedral complex is a complex too. The following example shows that this is not always the case.

Example 3.8.

Let $\Pi$ be the polyhedral complex in $\mathbb{R}^{3}$ containing the faces of the polyhedra

\Lambda_{1}=\{(x_{1},x_{2},0)|\,x_{1},x_{2}\geq 0\},\quad\Lambda_{2}=\{(x_{1},x_{2},1)|\,x_{1}+x_{2},x_{1}-x_{2}\geq 0\}.

Then $\operatorname{rec}(\Lambda_{1})$ and $\operatorname{rec}(\Lambda_{2})$ are two cones in $\mathbb{R}^{2}\times\{0\}$ whose intersection is the cone $\{(x_{1},x_{2},0)|x_{2},x_{1}-x_{2}\geq 0\}$ . This cone is neither a face of $\operatorname{rec}(\Lambda_{1})$ nor of $\operatorname{rec}(\Lambda_{2})$ . Hence $\operatorname{rec}(\Pi)$ is not a complex and, consequently, neither is $\operatorname{c}(\Pi)$ . In Figure 1 we see the polyhedron $\Lambda_{1}$ in light grey, the polyhedron $\Lambda_{2}$ in darker grey and $\operatorname{rec}(\Lambda_{2})$ as dashed lines.

Figure 1.

Therefore, to assure that $\operatorname{rec}(\Pi)$ or $\operatorname{c}(\Pi)$ are complexes, we need to impose some condition on $\Pi$ . This question has been addressed in [BS10]. Because our applications, we are mostly interested in the case when $\Pi$ is complete. It turns out that this assumption is enough to avoid the problem raised in Example 3.8.

Proposition 3.9.

Let $\Pi$ be a complete polyhedral complex in $N_{\mathbb{R}}$ . Then $\operatorname{rec}(\Pi)$ and $\operatorname{c}(\Pi)$ are complete conic polyhedral complexes in $N_{\mathbb{R}}$ and $N_{\mathbb{R}}\times\mathbb{R}_{\geq 0}$ , respectively. If, in addition, $\Pi$ is strongly convex, then both $\operatorname{rec}(\Pi)$ and $\operatorname{c}(\Pi)$ are fans.

Proof.

This is a particular case of [BS10, Theorem 3.4]. ∎

Definition 3.10.

Let $\Pi_{1}$ and $\Pi_{2}$ be two polyhedral complexes in $N_{\mathbb{R}}$ . The complex of intersections of $\Pi_{1}$ and $\Pi_{2}$ is defined as the collection of polyhedra

\Pi_{1}\cdot\Pi_{2}=\{\Lambda_{1}\cap\Lambda_{2}|\Lambda_{1}\in\Pi_{1},\Lambda_{2}\in\Pi_{2}\}.

Lemma 3.11.

The collection $\Pi_{1}\cdot\Pi_{2}$ is a polyhedral complex. If $\Pi_{1}$ and $\Pi_{2}$ are complete, then

\operatorname{rec}(\Pi_{1}\cdot\Pi_{2})=\operatorname{rec}(\Pi_{1})\cdot\operatorname{rec}(\Pi_{2}).

Proof.

Using the H-representation of polyhedra, one verifies that, if $\Lambda_{1}$ and $\Lambda_{2}$ are polyhedra with non-empty intersection, then any face of $\Lambda_{1}\cap\Lambda_{2}$ is the intersection of a face of $\Lambda_{1}$ with a face of $\Lambda_{2}$ . This implies that $\Pi_{1}\cdot\Pi_{2}$ is a polyhedral complex.

Now suppose that $\Pi_{1}$ and $\Pi_{2}$ are complete. Let $\sigma\in\operatorname{rec}(\Pi_{1}\cdot\Pi_{2})$ . This means that $\sigma=\operatorname{rec}(\Lambda)$ and $\Lambda=\Lambda_{1}\cap\Lambda_{2}$ with $\Lambda_{i}\in\Pi_{i}$ . It is easy to verify that $\Lambda\not=\emptyset$ implies $\operatorname{rec}(\Lambda)=\operatorname{rec}(\Lambda_{1})\cap\operatorname{rec}(\Lambda_{2})$ . Therefore $\sigma\in\operatorname{rec}(\Pi_{1})\cdot\operatorname{rec}(\Pi_{2})$ . This shows

\operatorname{rec}(\Pi_{1}\cdot\Pi_{2})\subset\operatorname{rec}(\Pi_{1})\cdot\operatorname{rec}(\Pi_{2}).

Since both complexes are complete, they agree. ∎

We consider now an integral structure in $N_{\mathbb{R}}$ . Let $N\simeq\mathbb{Z}^{n}$ be a lattice of rank $n$ such that $N_{\mathbb{R}}=N\otimes\mathbb{R}$ . Set $M=N^{\vee}=\operatorname{Hom}(N,\mathbb{Z})$ for its dual lattice so $M_{\mathbb{R}}=M\otimes\mathbb{R}$ . We also set $N_{\mathbb{Q}}=N\otimes\mathbb{Q}$ and $M_{\mathbb{Q}}=M\otimes\mathbb{Q}$ .

Definition 3.12.

Let $\Lambda$ be a polyhedron in $N_{\mathbb{R}}$ . We say that $\Lambda$ is a lattice polyhedron if it admits a V-representation with integral vectors and points. We say that it is rational if it admits a V-representation with rational coefficients.

Observe that any rational polyhedron admits an H-representation with integral coefficients.

Definition 3.13.

Let $\Pi$ be a strongly convex polyhedral complex in $N_{\mathbb{R}}$ . We say that $\Pi$ is lattice (respectively rational) if all of its elements are lattice (respectively rational) polyhedra. For short, a strongly convex rational polyhedral complex is called an SCR polyhedral complex. A conic SCR polyhedral complex is called a rational fan.

Remark 3.14.

The statement of Proposition 3.9 is compatible with rational structures. Namely, if $\Pi$ is rational, the same is true for $\operatorname{rec}(\Pi)$ and $\operatorname{c}(\Pi)$ .

Corollary 3.15.

The correspondence $\Pi\mapsto\operatorname{c}(\Pi)$ is a bijection between the set of complete polyhedral complexes in $N_{\mathbb{R}}$ and the set of complete conical polyhedral complexes in $N_{\mathbb{R}}\times\mathbb{R}_{\geq 0}$ . Its inverse is the correspondence that, to each conic polyhedral complex $\Sigma$ in $N_{\mathbb{R}}\times\mathbb{R}_{\geq 0}$ corresponds the complex in $N_{\mathbb{R}}$ obtained by intersecting $\Sigma$ with the hyperplane $N_{\mathbb{R}}\times\{1\}$ . These bijections preserve rationality and strong convexity.

Proof.

This is [BS10, Corollary 3.12]. ∎

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.

3.3. Operations on concave functions and duality

In this section we consider the basic operations on concave functions and their interplay with the Legendre-Fenchel duality.

Let $f_{1}$ and $f_{2}$ be two concave functions such that their stability sets are not disjoint. Their sup-convolution is the function

f_{1}\boxplus f_{2}\colon M_{\mathbb{R}}\longrightarrow{\underline{\mathbb{R}}},\quad v\longmapsto\sup_{u_{1}+u_{2}=v}(f_{1}(u_{1})+f_{2}(u_{2})).

This is a concave function whose effective domain is the Minkowski sum ${\operatorname{dom}}(f_{1})+{\operatorname{dom}}(f_{2})$ . This operation is associative and commutative whenever the terms are defined.

The operations of pointwise addition and sup-convolution are dual to each other. When working with general concave functions, there are some technical issues in this duality that will disappear when considering uniform limits of piecewise affine concave functions.

Proposition 3.38.

Let $f_{1},\dots,f_{l}$ be concave functions.

(1)

If $\operatorname{stab}(f_{1})\cap\dots\cap\operatorname{stab}(f_{l})\not=\emptyset$ , then

$(f_{1}\boxplus\dots\boxplus f_{l})^{\vee}=f_{1}^{\vee}+\dots+f_{l}^{\vee}.$
(2)

If ${\operatorname{dom}}(f_{1})\cap\dots\cap{\operatorname{dom}}(f_{l})\not=\emptyset$ , then

$({\operatorname{cl}}(f_{1})+\dots+{\operatorname{cl}}(f_{l}))^{\vee}={\operatorname{cl}}(f_{1}^{\vee}\boxplus\dots\boxplus f_{l}^{\vee}).$
(3)

If $\operatorname{ri}({\operatorname{dom}}(f_{1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{l}))\not=\emptyset$ , then

$(f_{1}+\dots+f_{l})^{\vee}=f_{1}^{\vee}\boxplus\dots\boxplus f_{l}^{\vee}.$

Proof.

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

Remark 3.39.

When some of the $f_{i}$ , say $f_{1},\dots,f_{k}$ , are piecewise affine, the statement (3) of the previous proposition holds under the weaker hypothesis [Roc70, Theorem 20.1]

{\operatorname{dom}}(f_{1})\cap\dots\cap{\operatorname{dom}}(f_{k})\cap\operatorname{ri}({\operatorname{dom}}(f_{k+1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{l}))\not=\emptyset.

Let $f$ be a concave function. For $\lambda>0$ , the left and right scalar multiplication of $f$ by $\lambda$ are the functions defined, for $u\in N_{\mathbb{R}}$ , by $(\lambda f)(u)=\lambda f(u)$ and $(f\lambda)(u)=\lambda f(u/\lambda)$ respectively. For a point $u_{0}\in N_{\mathbb{R}}$ , the translate of $f$ by $u_{0}$ is the concave function defined as $(\tau_{u_{0}}f)(u)=f(u-u_{0})$ for $u\in N_{\mathbb{R}}$ .

Proposition 3.40.

Let $f$ be a concave function on $N_{\mathbb{R}}$ , $\lambda>0$ , $u_{0}\in N_{\mathbb{R}}$ and $x_{0}\in M_{\mathbb{R}}$ . Then

(1)

${\operatorname{dom}}(\lambda f)={\operatorname{dom}}(f)$ , $\operatorname{stab}(\lambda f)=\lambda\operatorname{stab}(f)$ and $(\lambda f)^{\vee}=f^{\vee}\lambda$ ;
(2)

${\operatorname{dom}}(f\lambda)=\lambda{\operatorname{dom}}(f)$ , $\operatorname{stab}(f\lambda)=\operatorname{stab}(f)$ and $(f\lambda)^{\vee}=\lambda f^{\vee}$ ;
(3)

${\operatorname{dom}}(\tau_{u_{0}}f)={\operatorname{dom}}(f)+u_{0}$ , $\operatorname{stab}(\tau_{u_{0}}f)=\operatorname{stab}(f)$ and $(\tau_{u_{0}}f)^{\vee}=f^{\vee}+u_{0}$ ;
(4)

${\operatorname{dom}}(f+x_{0})={\operatorname{dom}}(f)$ , $\operatorname{stab}(f+x_{0})=\operatorname{stab}(f)+x_{0}$ and $(f+x_{0})^{\vee}=\tau_{x_{0}}f^{\vee}$ .

Proof.

This follows easily from the definitions. ∎

We next consider direct and inverse images of concave functions by affine maps. Let $Q_{\mathbb{R}}$ be a another finite dimensional real vector space and set $P_{\mathbb{R}}=Q_{\mathbb{R}}^{\vee}$ for its dual space. For a linear map $H\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ we denote by $H^{\vee}\colon M_{\mathbb{R}}\to P_{\mathbb{R}}$ the dual map. We need the following lemma in order to properly define direct images.

Lemma 3.41.

Let $H\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ be a linear map and $g$ a concave function on $Q_{\mathbb{R}}$ . If $\operatorname{stab}(g)\cap\operatorname{im}(H^{\vee})\not=\emptyset$ then, for all $u\in N_{\mathbb{R}}$ ,

\sup_{v\in H^{-1}(u)}g(v)<\infty.

Proof.

Let $x\in M_{\mathbb{R}}$ such that $H^{\vee}(x)\in\operatorname{stab}(g)$ . By the definition of the stability set, $\sup_{v\in Q_{\mathbb{R}}}(g(v)-\langle H^{\vee}(x),v\rangle)<\infty$ . Thus, for any $u\in N_{\mathbb{R}}$ ,

	$\displaystyle\sup_{v\in Q_{\mathbb{R}}}(g(v)-\langle H^{\vee}(x),v\rangle)$	$\displaystyle=\sup_{v\in Q_{\mathbb{R}}}(g(v)-\langle x,H(v)\rangle)$
		$\displaystyle\geq\sup_{v\in H^{-1}(u)}(g(v)-\langle x,H(v)\rangle)=\sup_{v\in H^{-1}(u)}g(v)-\langle x,u\rangle$

and so $\sup_{v\in H^{-1}(u)}g(v)$ is bounded above, as stated. ∎

Definition 3.42.

Let $A\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ be an affine map defined as $A=H+u_{0}$ for a linear map $H$ and a point $u_{0}\in N_{\mathbb{R}}$ . Let $f$ be a concave function on $N_{\mathbb{R}}$ such that ${\operatorname{dom}}(f)\cap\operatorname{im}(A)\not=\emptyset$ and $g$ a concave function on $Q_{\mathbb{R}}$ such that $\operatorname{stab}(g)\cap\operatorname{im}(H^{\vee})\not=\emptyset$ . Then the inverse image of $f$ by $A$ is defined as

A^{\ast}f\colon Q_{\mathbb{R}}\longrightarrow\mathbb{R},\quad v\longmapsto f\circ A(v),

and the direct image of $g$ by $A$ is defined as

A_{\ast}g\colon N_{\mathbb{R}}\longrightarrow\mathbb{R},\quad u\longmapsto\sup_{v\in A^{-1}(u)}g(v).

It is easy to see that the inverse image $A^{\ast}f$ is concave with effective domain ${\operatorname{dom}}(A^{\ast}f)=A^{-1}({\operatorname{dom}}(f))$ . Similarly, the direct image $A_{\ast}g$ is concave with effective domain ${\operatorname{dom}}(A_{\ast}g)=A({\operatorname{dom}}(g))$ , thanks to Lemma 3.41.

The inverse image of a closed function is also closed. In contrast, the direct image of a closed function is not necessarily closed: consider for instance the indicator function $\iota_{C}$ of the set $C=\{(x,y)\in\mathbb{R}^{2}\mid xy\geq 1,x>0\}$ , which is a closed concave function. Let $A\colon\mathbb{R}^{2}\to\mathbb{R}$ be the first projection. Then $A_{\ast}\iota_{C}$ is the indicator function of the subset $\mathbb{R}_{>0}$ , which is not a closed concave function.

We now turn to the behaviour of the sup-differential with respect to the basic operations. A first important property is the additivity.

Proposition 3.43.

For each $i=1,\dots,l$ , let $f_{i}$ be a concave function and $\lambda_{i}>0$ a real number. Then

(1)

$\partial\left(\sum_{i}\lambda_{i}f_{i}\right)\supset\sum_{i}\lambda_{i}\partial(f_{i})$ ;
(2)

if $\operatorname{ri}({\operatorname{dom}}(f_{1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{l}))\neq\emptyset$ , then

(3.44) $\partial\bigg(\sum_{i}\lambda_{i}f_{i}\bigg)=\sum_{i}\lambda_{i}\partial(f_{i}).$

Proof.

This is [Roc70, Theorem 23.8]. ∎

As in Remark 3.39, if $f_{1},\dots,f_{k}$ are piecewise affine, then (3.44) holds under the weaker hypothesis

{\operatorname{dom}}(f_{1})\cap\dots\cap{\operatorname{dom}}(f_{k})\cap\operatorname{ri}({\operatorname{dom}}(f_{k+1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{l}))\neq\emptyset.

The following result gives the behaviour of the sup-differential with respect to linear maps

Proposition 3.45.

Let $H\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ be a linear map, $u_{0}\in N_{\mathbb{R}}$ and $A=H+u_{0}$ the associated affine map. Let $f$ be a concave function on $N_{\mathbb{R}}$ , then

(1)

$\partial(A^{*}f)(v)\supset H^{\vee}\partial f(Av)$ for all $v\in Q_{\mathbb{R}}$ ;
(2)

if either $\operatorname{ri}({\operatorname{dom}}(f))\cap\operatorname{im}(A)\neq\emptyset$ or $f$ is piecewise affine and ${\operatorname{dom}}(f)\cap\operatorname{im}(A)\neq\emptyset$ , then for all $v\in Q_{\mathbb{R}}$ we have

$\partial(A^{*}f)(v)=H^{\vee}\partial f(Av).$

Proof.

The linear case $u_{0}=0$ is [Roc70, Theorem 23.9]. The general case follows from the linear case and the commutativity of the sup-differential and the translation. ∎

We summarize the behaviour of direct and inverse images of affine maps with respect to the Legendre-Fenchel duality.

Proposition 3.46.

(1)

$\operatorname{stab}(A_{\ast}g)=(H^{\vee})^{-1}(\operatorname{stab}(g))$ and

$(A_{\ast}g)^{\vee}=(H^{\vee})^{\ast}(g^{\vee})+u_{0};$
(2)

$H^{\vee}(\operatorname{stab}(f))\subset\operatorname{stab}(A^{\ast}f)\subset{\overline{H^{\vee}(\operatorname{stab}(f))}}$ and

$(A^{\ast}{\operatorname{cl}}(f))^{\vee}={\operatorname{cl}}((H^{\vee})_{\ast}(f^{\vee}-u_{0}));$

(3)

if $\operatorname{ri}({\operatorname{dom}}(f))\cap\operatorname{im}(A)\not=\emptyset$ then $\operatorname{stab}(A^{\ast}f)=H^{\vee}(\operatorname{stab}(f))$ and, for all $y$ in this set,

(A^{\ast}f)^{\vee}(y)=(H^{\vee})_{\ast}(f^{\vee}-u_{0})(y)=\max_{x\in(H^{\vee})^{-1}(y)}(f^{\vee}(x)-\langle x,u_{0}\rangle).

Moreover, for $y\in\operatorname{ri}(\operatorname{stab}(A^{\ast}f))$ , a point $x\in(H^{\vee})^{-1}(y)$ realizes this maximum if and only if $x\in\partial f(Av)$ for a $v\in Q_{\mathbb{R}}$ such that $y\in\partial(A^{*}f)(v)$ .

Observe that the last assertion in the above proposition can be also expressed as

(3.47)

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

Proof.

By Proposition 3.40(3,4),

A^{\ast}(f)=(H+{u_{0}})^{\ast}(f)=H^{\ast}(\tau_{-u_{0}}f),\quad A_{\ast}g=(H+{u_{0}})_{\ast}g=\tau_{u_{0}}(H_{\ast}g).

Then, except for the last assertion, the result follows by combining this with the case when $A$ is a linear map, treated in [Roc70, Theorem 16.3].

To prove the last assertion of the proposition, we first note that the concave function

(f^{\vee}-u_{0})|_{(H^{\vee})^{-1}(y)}

attains its maximum at a point $x$ if and only if its sup-differential at $x$ contains $0$ . We fix a point $x_{0}$ in $(H^{\vee})^{-1}(y)$ and we consider the affine inclusion

\iota\colon\operatorname{Ker}(H^{\vee})\hookrightarrow M_{\mathbb{R}},\quad z\mapsto z+x_{0}.

We denote by $\iota^{\vee}\colon N_{\mathbb{R}}\to N_{\mathbb{R}}/\operatorname{im}(H)$ the dual of the linear part of $\iota$ . Set $F=\iota^{*}(f^{\vee}-u_{0})$ , then for $z\in\operatorname{Ker}(H^{\vee})$ , by Proposition 3.45, we have

\partial F(z)=\iota^{\vee}(\partial f^{\vee}(z+x_{0})-u_{0})

and so $0\in\partial F(z)$ if and only if $\partial f^{\vee}(z+x_{0})\cap\operatorname{im}(A)\not=\emptyset$ . Hence $x=z+x_{0}$ realizes the maximum if and only if $x\in\partial f(Av)$ for some $v\in Q_{\mathbb{R}}$ such that $y\in\partial(A^{*}f)(v)$ , as stated. ∎

In particular, the operations of direct and inverse image of linear maps are dual to each other. In the notation of Proposition 3.46 and assuming for simplicity $\operatorname{ri}({\operatorname{dom}}(f))\cap\operatorname{im}(H)\not=\emptyset$ , we have

(H_{\ast}g)^{\vee}=(H^{\vee})^{\ast}(g^{\vee}),\quad(H^{\ast}f)^{\vee}=(H^{\vee})_{\ast}(f^{\vee}),

while the stability sets relate by $\operatorname{stab}(H_{\ast}g)=(H^{\vee})^{-1}(\operatorname{stab}(g))$ and $\operatorname{stab}(H^{\ast}f)=H^{\vee}(\operatorname{stab}(f))$ .

The last concept we recall in this section is the notion of recession of a concave function.

Definition 3.48.

The recession function of a concave function $f\colon N_{\mathbb{R}}\to{\underline{\mathbb{R}}}$ , denoted $\operatorname{rec}(f)$ , is the function

\operatorname{rec}(f)\colon N_{\mathbb{R}}\longrightarrow{\underline{\mathbb{R}}},\quad u\longmapsto\inf_{v\in{\operatorname{dom}}(f)}(f(u+v)-f(v)).

This is a concave conical function. If $f$ is closed, its recession function can be defined as the limit

(3.49)

\operatorname{rec}(f)(u)=\lim_{\lambda\to\infty}\lambda^{-1}f(v_{0}+\lambda u)

for any $v_{0}\in{\operatorname{dom}}(f)$ [Roc70, Theorem 8.5].

It is clear from the definition that ${\operatorname{dom}}(\operatorname{rec}(f))\subset\operatorname{rec}({\operatorname{dom}}(f))$ . The equality does not hold in general, as can be seen by considering the concave function $\mathbb{R}\to\mathbb{R}$ , $u\mapsto-\exp(u)$ .

If $f$ is closed then the function $\operatorname{rec}(f)$ is closed [Roc70, Theorem 8.5]. Hence it is natural to regard recession functions as support functions.

Proposition 3.50.

Let $f$ be a concave function. Then $\operatorname{rec}(f^{\vee})$ is the support function of ${\operatorname{dom}}(f)$ . If $f$ is closed, then $\operatorname{rec}(f)$ is the support function of $\operatorname{stab}(f)$ .

Proof.

This is [Roc70, Theorem 13.3]. ∎

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

3.5. The piecewise affine case

The Legendre-Fenchel duality for piecewise affine concave functions can be described in combinatorial terms. Moreover, some technical issues of the general theory disappear when dealing with piecewise affine concave functions on convex polyhedra and uniform limits of such functions.

Definition 3.58.

Let $C\subset N_{\mathbb{R}}$ be a convex polyhedron. A function $f\colon C\to\mathbb{R}$ is piecewise affine if there a finite cover of $C$ by closed subsets such that the restriction of $f$ to each of these subsets is an affine function. A concave function $f\colon N_{\mathbb{R}}\to{\underline{\mathbb{R}}}$ is said to be piecewise affine if ${\operatorname{dom}}(f)$ is a convex polyhedron and the restriction $f|_{{\operatorname{dom}}(f)}$ piecewise affine.

Lemma 3.59.

Let $f$ be a piecewise affine function defined on a convex polyhedron $C\subset N_{\mathbb{R}}$ . Then there exists a polyhedral complex $\Pi$ in $C$ such that the restriction of $f$ to each polyhedron of $\Pi$ is an affine function.

Proof.

This is an easy consequence of the max-min representation of piecewise affine functions in [Ovc02]. ∎

Definition 3.60.

Let $C$ be a convex polyhedron, $\Pi$ a polyhedral complex in $C$ and $f\colon C\to\mathbb{R}$ a piecewise affine function. We say that $\Pi$ and $f$ are compatible if $f$ is affine on each polyhedron of $\Pi$ . Alternatively, we say that $f$ is a piecewise affine function on $\Pi$ . If the function $f$ is concave, it is said to be strictly concave on $\Pi$ if $\Pi=\Pi(f)$ . The polyhedral complex $\Pi$ is said to be regular if there exists a concave piecewise affine function $f$ such that $\Pi=\Pi(f)$ .

As was the case for convex polyhedra, piecewise affine concave functions can be described in two dual ways, which we refer as the H-representation and the V-representation. For the H-representation, we consider a convex polyhedron

\Lambda=\bigcap_{1\leq j\leq k}\{u\in N_{\mathbb{R}}\mid\langle a_{j},u\rangle+\alpha_{j}\geq 0\}

as in (3.4) and a set of affine equations $\{(a_{j},\alpha_{j})\}_{k+1\leq j\leq l}\subset M_{\mathbb{R}}\times\mathbb{R}$ . We then define a concave function on $N_{\mathbb{R}}$ as

(3.61)

f(u)=\min_{k+1\leq j\leq l}(\langle a_{j},u\rangle+\alpha_{j})\quad\text{ for }u\in\Lambda

and $f(u)=-\infty$ for $u\notin\Lambda$ . With this representation, the recession function of $f$ is given by

\operatorname{rec}(f)(u)=\min_{k+1\leq j\leq l}\langle a_{j},u\rangle,\quad\text{ for }u\in\operatorname{rec}(\Lambda)

and $\operatorname{rec}(f)(u)=-\infty$ for $u\notin\operatorname{rec}(\Lambda)$ . In particular,

(3.62)

{\operatorname{dom}}(\operatorname{rec}(f))=\operatorname{rec}({\operatorname{dom}}(f)),\quad\operatorname{stab}(\operatorname{rec}(f))=\operatorname{stab}(f).

For the V-representation, we consider a polyhedron

\Lambda^{\prime}=\operatorname{cone}(b_{1},\dots,b_{k})+\operatorname{conv}(b_{k+1},\dots,b_{l})

as in (3.5), a set of slopes $\{\beta_{j}\}_{1\leq j\leq k}\subset\mathbb{R}$ and a set of values $\{\beta_{j}\}_{k+1\leq j\leq l}\subset\mathbb{R}$ . We then define a concave function on $M_{\mathbb{R}}$ as

(3.63)

g(u)=\sup\bigg\{\sum_{j=1}^{l}\lambda_{j}\beta_{j}\bigg|\ \lambda_{j}\geq 0,\ \sum_{j=k+1}^{l}\lambda_{j}=1,\ \sum_{j=1}^{l}\lambda_{j}b_{j}=u\bigg\}.

With this second representation, we obtain the recession function as

\operatorname{rec}(g)(u)=\sup\bigg\{\sum_{j=1}^{k}\lambda_{j}\beta_{j}\bigg|\ \lambda_{j}\geq 0,\ \sum_{j=1}^{k}\lambda_{j}b_{j}=u\bigg\}.

As we have already mentioned, the Legendre-Fenchel duality of piecewise affine concave functions can be described in combinatorial terms.

Proposition 3.64.

Let $\Lambda$ be a polyhedron in $N_{\mathbb{R}}$ and $f$ a piecewise affine concave function with ${\operatorname{dom}}(f)=\Lambda$ given as

	$\displaystyle\Lambda$	$\displaystyle=\bigcap_{1\leq j\leq k}\{u\in N_{\mathbb{R}}\mid\langle a_{j},u\rangle+\alpha_{j}\geq 0\},$
	$\displaystyle f(u)$	$\displaystyle=\min_{k+1\leq j\leq l}(\langle a_{j},u\rangle+\alpha_{j})\quad\text{for }u\in\Lambda$

with $a_{j}\in M_{\mathbb{R}}$ and $\alpha_{j}\in\mathbb{R}$ . Then

	$\displaystyle\operatorname{stab}(f)$	$\displaystyle=\operatorname{cone}(a_{1},\dots,a_{k})+\operatorname{conv}(a_{k+1},\dots,a_{l}),$
	$\displaystyle f^{\vee}(x)$	$\displaystyle=\sup\bigg\{\sum_{j=1}^{l}-\lambda_{j}\alpha_{j}\bigg\|\ \lambda_{j}\geq 0,\sum_{j=k+1}^{l}\lambda_{j}=1,\ \sum_{j=1}^{l}\lambda_{j}a_{j}=x\bigg\}\ \text{ for }x\in\operatorname{stab}(f).$

Proof.

This is proved in [Roc70, pp. 172-174]. ∎

Example 3.65.

Let $\Lambda$ be a convex polyhedron in $N_{\mathbb{R}}$ . Then both the indicator function $\iota_{\Lambda}$ and the support function $\Psi_{\Lambda}$ are concave and piecewise affine. We have $\Psi_{\Lambda}^{\vee}=\iota_{\Lambda}$ . In particular, if we fix an isomorphism $N_{\mathbb{R}}\simeq\mathbb{R}^{n}$ , the function

\Psi_{\Delta^{n}}\colon N_{\mathbb{R}}\longrightarrow\mathbb{R},\quad(u_{1},\dots,u_{n})\longmapsto\min\{0,u_{1},\dots,u_{n}\}

is the support function of the standard simplex $\Delta^{n}=\operatorname{conv}(\boldsymbol{0},e^{\vee}_{1},\dots,e^{\vee}_{n})\subset M_{\mathbb{R}}$ , where $\{e_{1},\dots,e_{n}\}$ is the standard basis of $\mathbb{R}^{n}$ and $\{e_{1}^{\vee},\dots,e_{n}^{\vee}\}$ is the dual basis. Hence, $\operatorname{stab}(\Psi_{\Delta^{n}})=\Delta^{n}$ and $\Psi_{\Delta^{n}}^{\vee}=\iota_{\Delta^{n}}$ .

Let $\Lambda$ be a polyhedron in $N_{\mathbb{R}}$ and $f$ a piecewise affine concave function with ${\operatorname{dom}}(f)=\Lambda$ . Then ${\operatorname{dom}}(\partial f)=\Lambda$ and $\Pi(f)$ and $\Pi(f^{\vee})$ are convex decompositions of $\Lambda$ and of $\Lambda^{\prime}:=\operatorname{stab}(f)$ respectively. By Theorem 3.33, the Legendre-Fenchel correspondence

{\mathcal{L}}f\colon\Pi(f)\longrightarrow\Pi(f^{\vee})

is a duality in the sense of Definition 3.32. However in the polyhedral case, these decompositions are dual in a stronger sense. We need to introduce some more definitions before we can properly state this duality.

Definition 3.66.

Let $\Lambda$ be a polyhedron and $K$ a face of $\Lambda$ . The angle of $\Lambda$ at $K$ is defined as

\angle(K,\Lambda)=\{t(u-v)\mid u\in\Lambda,v\in K,t\geq 0\}.

It is a polyhedral cone.

Definition 3.67.

The dual of a convex cone $\sigma\subset N_{\mathbb{R}}$ is defined as

\sigma^{\vee}=\{x\in M_{\mathbb{R}}\mid\langle x,u\rangle\geq 0\text{ for all }u\in\sigma\}.

This is a convex closed cone.

If $\sigma$ is a convex closed cone, then $\sigma^{\vee\vee}=\sigma$ . For a piecewise affine concave function $f$ on $N_{\mathbb{R}}$ , by Proposition 3.64 we have

\operatorname{rec}({\operatorname{dom}}(f))^{\vee}=\operatorname{rec}(\operatorname{stab}(f)).

Definition 3.68.

Let $C,C^{\prime}$ be convex polyhedra in $N_{\mathbb{R}}$ and $M_{\mathbb{R}}$ , respectively, and $\Pi,\Pi^{\prime}$ polyhedral complexes in $C$ and $C^{\prime}$ , respectively. We say that $\Pi$ and $\Pi^{\prime}$ are dual polyhedral complexes if there is a bijective map $\Pi\to\Pi^{\prime},\Lambda\mapsto\Lambda^{*}$ such that

(1)

for all $\Lambda,K\in\Pi$ , the inclusion $K\subset\Lambda$ hols if and only if $K^{*}\supset\Lambda^{*}$ ;
(2)

for all $\Lambda,K\in\Pi$ , if $K\subset\Lambda$ , then $\angle(\Lambda^{*},K^{*})=\angle(K,\Lambda)^{\vee}$ .

For $\Lambda\in\Pi$ , the angle $\angle(\Lambda,\Lambda)$ is the linear subspace generated by differences of points in $\Lambda$ . Condition (2) above implies that $\angle(\Lambda,\Lambda)$ and $\angle(\Lambda^{*},\Lambda^{*})$ are orthogonal. In particular, $\dim(\Lambda)+\dim(\Lambda^{*})=n$ .

Proposition 3.69.

Let $f$ be a piecewise affine concave function with $\Lambda={\operatorname{dom}}(f)$ and $\Lambda^{\prime}=\operatorname{stab}(f)$ . Then $\Pi(f)$ and $\Pi(f^{\vee})$ are polyhedral complexes in $\Lambda$ and $\Lambda^{\prime}$ respectively. Moreover, they are dual of each other. In particular, the vertices of $\Pi(f)$ are in bijection with the polyhedra of $\Pi(f^{\vee})$ of maximal dimension.

Proof.

This is proved in [PR04, Proposition 1]. ∎

Example 3.70.

Consider the standard simplex $\Delta^{n}$ of Example 3.65. Its indicator function induces the standard polyhedral complex in $\Delta^{n}$ consisting of the collection of its faces. The dual of $\iota_{\Delta^{n}}$ , the support function $\Psi_{\Delta^{n}}$ , induces a fan $\Sigma_{\Delta^{n}}:=\Pi(\Psi_{\Delta^{n}})$ of $N_{\mathbb{R}}$ . The duality between these polyhedral complexes can be made explicit as

\Pi(\iota_{\Delta^{n}})\longrightarrow\Sigma_{\Delta^{n}},\quad F\longmapsto\angle(F,\Delta^{n})^{\vee}.

Example 3.71.

The previous example can be generalized to an arbitrary polytope $\Delta\subset M_{\mathbb{R}}$ . The indicator function $\iota_{\Delta}$ induces the standard decomposition of $\Delta$ into its faces and dually, the support function $\Psi_{\Delta}$ induces a polyhedral complex $\Sigma_{\Delta}:=\Pi(\Psi_{\Delta})$ made of cones. If $\Delta$ is of maximal dimension, then $\Sigma_{\Delta}$ is a fan.

The faces of $\Delta$ are in one-to-one correspondence with the cones of $\Sigma_{\Delta}$ through the Legendre-Fenchel correspondence. For a face $F$ of $\Delta$ , its corresponding cone is

\sigma_{F}:=F^{*}=\{u\in N_{\mathbb{R}}\mid\langle u,x-y\rangle\geq 0\mbox{ for all }x\in\Delta,y\in F\}.

Reciprocally, to each cone $\sigma$ corresponds a face of $\Delta$ of complementary dimension

F_{\sigma}:=\sigma^{*}=\{x\in\Delta\mid\langle x,u\rangle=\Psi_{\Delta}(u)\mbox{ for all }u\in\sigma\}.

On a cone $\sigma\in\Sigma$ , the function $\Psi_{\Delta}$ is defined by any vector $m_{\sigma}$ in the affine space $\operatorname{aff}(F_{\sigma})$ . The cone $\sigma$ is normal to $F_{\sigma}$ .

For piecewise affine concave functions, the operations of taking the recession function and the associated polyhedral convex commute with each other.

Proposition 3.72.

Let $f$ be a piecewise affine concave function on $N_{\mathbb{R}}$ . Then

\Pi(\operatorname{rec}(f))=\operatorname{rec}(\Pi(f)).

Proof.

Let $P_{f}(u,x)=f(u)+f^{\vee}(x)-\left<u,x\right>$ be the function introduced in (3.20). For each $x\in\operatorname{stab}(f)$ write $P_{f,x}(u)=P(u,x)$ . Let $C_{x}$ be as in Definition 3.23. By Lemma 3.24,

C_{x}=\{u\in{\operatorname{dom}}(f)\mid P_{f,x}(u)=0\}.

Write $P^{\prime}(v)=\operatorname{rec}(f)(v)-\left<u,x\right>$ . Then $P^{\prime}=\operatorname{rec}(P_{f,x})$ .

We claim that, for each $x\in\operatorname{stab}(f)$ ,

\operatorname{rec}(C_{x})=\{v\in{\operatorname{dom}}(\operatorname{rec}(f))\mid P^{\prime}(v)=0\}.

Let $v\in\operatorname{rec}(C_{x})$ . Clearly $v\in{\operatorname{dom}}(\operatorname{rec}(f))$ and, since $x\in\operatorname{stab}(f)$ , the set $C_{x}$ is non-empty. Let $u_{0}\in C_{x}$ . Then, for each $\lambda>0$ , $u_{0}+\lambda v\in C_{x}$ . Therefore,

P^{\prime}(v)=\lim_{\lambda\to\infty}\frac{P_{f,x}(u_{0}+\lambda v)-P_{f,x}(u_{0})}{\lambda}=0.

Conversely, let $v\in{\operatorname{dom}}(\operatorname{rec}(f))$ satisfying $P^{\prime}(v)=0$ and $u\in C_{x}$ . On the one hand, by the properties of the function $P_{f}$ , we have $P_{f,x}(u+v)\leq 0$ . On the other hand, since $P^{\prime}=\operatorname{rec}(P_{f,x})$ ,

P_{f,x}(u+v)-P_{f,x}(u)\geq P^{\prime}(v)=0.

Thus $P_{f,x}(u+v)\geq P_{f,x}(u)=0$ and finally $P_{f,x}(u+v)=0$ . This implies that, if $u\in C_{x}$ then $u+v\in C_{x}$ , showing $v\in\operatorname{rec}(C_{x})$ . Hence the claim is proved.

By definition $\Pi(f)=\{C_{x}\}_{x\in\operatorname{stab}(f)}$ . Hence $\operatorname{rec}(\Pi(f))=\{\operatorname{rec}(C_{x})\}_{x\in\operatorname{stab}(f)}$ . For each $x\in\operatorname{stab}(\operatorname{rec}(f))$ , write

C^{\prime}_{x}=\{v\in{\operatorname{dom}}(\operatorname{rec}(f))\mid P^{\prime}(v)=0\}.

Then $\Pi(\operatorname{rec}(f))=\{C^{\prime}_{x}\}_{x\in\operatorname{stab}(\operatorname{rec}(f))}$ . The result follows from the previous claim and the fact that $\operatorname{stab}(f)=\operatorname{stab}(\operatorname{rec}(f))$ by (3.62). ∎

Now we want to study the compatibility of Legendre-Fenchel duality and integral and rational structures. Let $N\simeq\mathbb{Z}^{n}$ be a lattice of rank $n$ such that $N_{\mathbb{R}}=N\otimes\mathbb{R}$ . Set $M=N^{\vee}=\operatorname{Hom}(N,\mathbb{Z})$ for its dual lattice, so $M_{\mathbb{R}}=M\otimes\mathbb{R}$ . We also set $N_{\mathbb{Q}}=N\otimes\mathbb{Q}$ and $M_{\mathbb{Q}}=M\otimes\mathbb{Q}$ .

Definition 3.73.

A piecewise affine concave function $f$ on $N_{\mathbb{R}}$ is an H-lattice (respectively, a V-lattice) concave function if it has an H-representation (respectively, a V-representation) with integral coefficients. We say that $f$ is a rational piecewise affine concave function if it has an H-representation (or equivalently, a V-representation) with rational coefficients.

Observe that the domain of a V-lattice concave function is a lattice polyhedron, whereas the domain of an H-lattice concave function is a rational polyhedron.

Remark 3.74.

The notion of H-lattice concave functions defined on the whole $N_{\mathbb{R}}$ coincides with the notion of tropical Laurent polynomials over the integers, that is, the elements of the group semi-algebra $\mathbb{Z}_{\text{trop}}[N]$ , where the arithmetic operations of the base semi-ring $\mathbb{Z}_{\text{trop}}=(\mathbb{Z},\oplus,\odot)$ are defined as $x\oplus y=\min(x,y)$ and $x\odot y=x+y$ .

Proposition 3.75.

Let $f$ be a piecewise affine concave function on $N_{\mathbb{R}}$ .

(1)

$f$ is an H-lattice concave function (respectively, a rational piecewise affine concave function) if and only if $f^{\vee}$ is a V-lattice concave function (respectively, a rational piecewise affine concave function).
(2)

$\operatorname{rec}(f)$ is an H-lattice concave function if and only if $\operatorname{stab}(f)$ is a lattice polyhedron.

Proof.

This follows easily from Proposition 3.64. ∎

Example 3.76.

If $\Delta$ is a lattice polytope, its indicator function is a V-lattice function, its support function $\Psi_{\Delta}$ is an H-lattice function and, when $\Delta$ has maximal dimension, the fan $\Sigma_{\Delta}$ is a rational fan. In particular, if the isomorphism $N\simeq\mathbb{R}^{n}$ of Example 3.65 is given by the choice of an integral basis $e_{1},\dots,e_{n}$ of $N$ , then $\Delta^{n}$ is a lattice polytope, the function $\Psi_{\Delta^{n}}$ is an H-lattice concave function and $\Sigma_{\Delta^{n}}$ is a rational fan. If we write $e_{0}=-\sum_{i=1}^{n}e_{i}$ , this is the fan generated by the vectors $e_{0},e_{1},\dots,e_{n}$ in the sense that each cone of $\Sigma_{\Delta^{n}}$ is the cone generated by a strict subset of the above set of vectors. Figure 3 illustrates the case $n=2$ .

Figure 3. The standard simplex

\Delta^{2}

, its associated fan and support function

Let $\Lambda$ and $\Lambda^{\prime}$ be polyhedra in $N_{\mathbb{R}}$ and in $M_{\mathbb{R}}$ , respectively. We set $\mathscr{P}(\Lambda,\Lambda^{\prime})$ for the space of piecewise affine concave functions with effective domain $\Lambda$ and stability set $\Lambda^{\prime}$ . We also set ${\overline{\mathscr{P}}}(\Lambda,\Lambda^{\prime})$ for the closure of this space with respect to uniform convergence. We set

\mathscr{P}(\Lambda)=\bigcup_{\Lambda^{\prime}}\mathscr{P}(\Lambda,\Lambda^{\prime}),\quad{\overline{\mathscr{P}}}(\Lambda)=\bigcup_{\Lambda^{\prime}}{\overline{\mathscr{P}}}(\Lambda,\Lambda^{\prime})

for the space of piecewise affine concave functions with effective domain $\Lambda$ and for its closure with respect to uniform convergence, respectively. We also set

\mathscr{P}=\bigcup_{\Lambda,\Lambda^{\prime}}\mathscr{P}(\Lambda,\Lambda^{\prime}),\quad{\overline{\mathscr{P}}}=\bigcup_{\Lambda,\Lambda^{\prime}}{\overline{\mathscr{P}}}(\Lambda,\Lambda^{\prime}).

When we need to specify the vector space $N_{\mathbb{R}}$ we will denote it as a subindex as in $\mathscr{P}_{N_{\mathbb{R}}}$ or ${\overline{\mathscr{P}}}_{N_{\mathbb{R}}}$ .

The following propositions contain the basic properties of the Legendre-Fenchel duality acting on ${\overline{\mathscr{P}}}$ . The elements in ${\overline{\mathscr{P}}}$ are continuous functions on polyhedra. In particular, they are closed concave functions. Observe that when working with uniform limits of piecewise affine concave functions, the technical issues in §3.2 disappear.

Proposition 3.77.

The concave piecewise affine functions and their uniform limits satisfy the following properties.

(1)

Let $f\in{\overline{\mathscr{P}}}_{N_{\mathbb{R}}}$ . Then $f^{\vee\vee}=f$ .
(2)

If $f\in\mathscr{P}(\Lambda,\Lambda^{\prime})$ (respectively $f\in{\overline{\mathscr{P}}}(\Lambda,\Lambda^{\prime})$ ) then $f^{\vee}\in\mathscr{P}(\Lambda^{\prime},\Lambda)$ (respectively $f^{\vee}\in{\overline{\mathscr{P}}}(\Lambda^{\prime},\Lambda)$ ).
(3)

If $f\in{\overline{\mathscr{P}}}(\Lambda)$ then ${\operatorname{dom}}(\operatorname{rec}(f))=\operatorname{rec}(\Lambda)$ .
(4)

Let $f_{i}\in\mathscr{P}(\Lambda_{i},\Lambda_{i}^{\prime})$ (respectively $f_{i}\in{\overline{\mathscr{P}}}(\Lambda_{i},\Lambda_{i}^{\prime})$ ), $i=1,2$ , with $\Lambda_{1}\cap\Lambda_{2}\not=\emptyset$ . Then $f_{1}+f_{2}\in\mathscr{P}(\Lambda_{1}\cap\Lambda_{2},\Lambda_{1}^{\prime}+\Lambda_{2}^{\prime})$ (respectively $f_{1}+f_{2}\in{\overline{\mathscr{P}}}(\Lambda_{1}\cap\Lambda_{2},\Lambda_{1}^{\prime}+\Lambda_{2}^{\prime})$ ) and $(f_{1}+f_{2})^{\vee}=f_{1}^{\vee}\boxplus f_{2}^{\vee}$ .
(5)

Let $f_{i}\in\mathscr{P}(\Lambda_{i},\Lambda_{i}^{\prime})$ (respectively $f_{i}\in{\overline{\mathscr{P}}}(\Lambda_{i},\Lambda_{i}^{\prime})$ ), $i=1,2$ , with $\Lambda_{1}^{\prime}\cap\Lambda_{2}^{\prime}\not=\emptyset$ . Then $f_{1}\boxplus f_{2}\in\mathscr{P}(\Lambda_{1}+\Lambda_{2},\Lambda_{1}^{\prime}\cap\Lambda_{2}^{\prime})$ (respectively $f_{1}+f_{2}\in{\overline{\mathscr{P}}}(\Lambda_{1}+\Lambda_{2},\Lambda_{1}^{\prime}\cap\Lambda_{2}^{\prime})$ ) and $(f_{1}\boxplus f_{2})^{\vee}=f_{1}^{\vee}+f_{2}^{\vee}$ .
(6)

Let $(f_{i})_{i\geq 1}\subset{\overline{\mathscr{P}}}$ be a sequence converging uniformly to a function $f$ . Then $f\in{\overline{\mathscr{P}}}$ .

Proof.

All the statements follow, either directly from the definition, or propositions 3.64 and 3.18. ∎

Proposition 3.78.

Let $A\colon Q_{\mathbb{R}}\to N_{\mathbb{R}}$ be an affine map defined as $A=H+u_{0}$ for a linear map $H$ and a point $u_{0}\in N_{\mathbb{R}}$ . Let $f\in\mathscr{P}_{N_{\mathbb{R}}}$ (respectively $f\in{\overline{\mathscr{P}}}_{N_{\mathbb{R}}}$ ) with ${\operatorname{dom}}(f)\cap\operatorname{im}(A)\not=\emptyset$ and $g\in\mathscr{P}_{Q_{\mathbb{R}}}$ (respectively $g\in{\overline{\mathscr{P}}}_{Q_{\mathbb{R}}}$ ) such that $\operatorname{stab}(g)\cap\operatorname{im}(H^{\vee})\not=\emptyset$ . Then $A^{\ast}f\in{\mathscr{P}}_{Q_{\mathbb{R}}}$ (respectively $A^{*}f\in{\overline{\mathscr{P}}}_{Q_{\mathbb{R}}}$ ) and $A_{*}g\in\mathscr{P}_{N_{\mathbb{R}}}$ (respectively $A_{*}g\in{\overline{\mathscr{P}}}_{N_{\mathbb{R}}}$ ). Moreover,

(1)

$\operatorname{stab}(A^{\ast}f)=H^{\vee}(\operatorname{stab}(f))$ , $(A^{\ast}f)^{\vee}=(H^{\vee})_{\ast}(f^{\vee}-u_{0})$ and, for all $y\in\operatorname{stab}(A^{\ast}f)$ ,

$(A^{\ast}f)^{\vee}(y)=\max_{x\in(H^{\vee})^{-1}(y)}(f^{\vee}(x)-\langle x,u_{0}\rangle);$
(2)

$\operatorname{stab}(A_{\ast}g)=(H^{\vee})^{-1}(\operatorname{stab}(g))$ , $(A_{\ast}g)^{\vee}=(H^{\vee})^{\ast}(g^{\vee})+u_{0}$ and, for all $u\in{\operatorname{dom}}(A_{*}g)$ ,

$A_{*}g(u)=\max_{v\in A^{-1}(u)}g(v).$

Proof.

These statements follow either from Proposition 3.46 or from [Roc70, Corollary 19.3.1]. ∎

We will be concerned mainly with functions in ${\overline{\mathscr{P}}}$ whose effective domain is either a polytope or the whole space $N_{\mathbb{R}}$ . These are the kind of functions that arise when considering proper toric varieties. The functions in $\mathscr{P}(N_{\mathbb{R}})$ can be realized as the inverse image of the support function of the standard simplex, while the functions of $\mathscr{P}(\Delta)$ can be realized as direct images of the indicator function of the standard simplex.

Lemma 3.79.

Let $f\in\mathscr{P}(N_{\mathbb{R}})$ and let $f(u)=\min_{0\leq i\leq r}(a_{i}(u)+\alpha_{i})$ be an H-representation of $f$ . Write $\boldsymbol{\alpha}=(\alpha_{i}-\alpha_{0})_{i=1,\dots,r}$ , and consider the linear map $H\colon N_{\mathbb{R}}\to\mathbb{R}^{r}$ given by $H(u)=(a_{i}(u)-a_{0}(u))_{i=1,\dots,r}$ and the affine map $A=H+\boldsymbol{\alpha}.$ Then

(1)

$f=A^{\ast}\Psi_{\Delta^{r}}+a_{0}+\alpha_{0};$
(2)

$f^{\vee}=\tau_{a_{0}}(H^{\vee})_{\ast}(\iota_{\Delta^{r}}-\boldsymbol{\alpha})-\alpha_{0}.$

This second function can be alternatively described as the function which parameterizes the upper envelope of the extended polytope

\operatorname{conv}((a_{1},-\alpha_{1}),\dots,(a_{l},-\alpha_{l}))\subset M_{\mathbb{R}}\times\mathbb{R}.

Proof.

Statement (1) follows from the explicit description of $\Psi_{\Delta^{r}}$ in Example 3.70. Statement (2) follows from Proposition 3.78. The last statement is a consequence of Proposition 3.64. ∎

The next proposition characterizes the elements of ${\overline{\mathscr{P}}}(N_{\mathbb{R}})$ and ${\overline{\mathscr{P}}}(\Delta)$ for a polytope $\Delta$ .

Proposition 3.80.

Let $\Delta$ be a convex polytope of $M_{\mathbb{R}}$ .

(1)

The space ${\overline{\mathscr{P}}}(\Delta,N_{\mathbb{R}})$ agrees with the space of all continuous concave functions on $\Delta$ .
(2)

A concave function $f$ belongs to ${\overline{\mathscr{P}}}(N_{\mathbb{R}},\Delta)$ if and only if ${\operatorname{dom}}(f)=N_{\mathbb{R}}$ and $|f-\Psi_{\Delta}|$ is bounded.

Proof.

We start by proving (1). By the properties of uniform convergence, it is clear that any element of ${\overline{\mathscr{P}}}(\Delta,N_{\mathbb{R}})$ is concave and continuous. Conversely, a continuous function $f$ on $\Delta$ is uniformly continuous because $\Delta$ is compact. Therefore, given $\varepsilon>0$ there is a $\delta>0$ such that $|f(u)-f(v)|<\varepsilon$ for all $u,v\in\Delta$ such that $\|u-v\|<\delta$ . By compactness, we can find a triangulation $\Delta=\bigcup_{i}\Delta_{i}$ with $\operatorname{diam}(\Delta_{i})<\delta$ . Let $\{b_{j}\}_{j}$ be the vertices of this triangulation and consider the function $g\in\mathscr{P}(\Delta,N_{\mathbb{R}})$ defined as

g(u)=\sup\bigg\{\sum_{j=1}^{l}\lambda_{j}f(b_{j})\bigg|\ \lambda_{j}\geq 0,\sum_{j}\lambda_{j}=1\sum_{j}\lambda_{j}a_{j}=x\bigg\}.

For $u\in\Delta$ , let $b_{j_{0}},\dots,b_{j_{n}}$ denote the vertices of an element of the triangulation containing $u$ . We write $u=\lambda_{j_{0}}u_{j_{0}}+\dots+\lambda_{j_{n}}u_{j_{n}}$ for some $\lambda_{j_{i}}\geq 0$ and $\lambda_{j_{0}}+\dots+\lambda_{j_{n}}=1$ . By concavity, we have

f(u)\geq g(u)\geq\sum_{k=0}^{n}\lambda_{j_{k}}f(u_{j_{k}})\geq f(u)-\varepsilon,

which shows that any continuous function on $\Delta$ can be arbitrarily approximated by elements of $\mathscr{P}(\Delta,N_{\mathbb{R}})$ .

We now prove (2). Let $f\in{\overline{\mathscr{P}}}(N_{\mathbb{R}},\Delta)$ . By definition, for each $\varepsilon>0$ we can find a function $g\in\mathscr{P}(N_{\mathbb{R}},\Delta)$ with $\sup|f-g|\leq\varepsilon$ . In particular, $|f-g|$ is bounded. Furthermore, $\operatorname{rec}(g)=\Psi_{\Delta}$ and $|g-\operatorname{rec}(g)|$ is bounded because $g\in\mathscr{P}(N_{\mathbb{R}})$ . Hence ${\operatorname{dom}}(f)={\operatorname{dom}}(g)=N_{\mathbb{R}}$ and $|f-\Psi_{\Delta}|$ is bounded.

Conversely, let $f$ be a concave function such that ${\operatorname{dom}}(f)=N_{\mathbb{R}}$ and $|f-\Psi_{\Delta}|$ is bounded. Then $\operatorname{stab}(f)=\operatorname{stab}(\Psi_{\Delta})=\Delta$ and $f^{\vee}$ is a continuous concave function on $\Delta$ . Hence we can apply (1) to $f^{\vee}$ to obtain functions $g_{i}\in\mathscr{P}(\Delta,N_{\mathbb{R}})$ approaching $f^{\vee}$ uniformly. We conclude that the functions $g_{i}^{\vee}\in\mathscr{P}(N_{\mathbb{R}},\Delta)$ approach $f$ uniformly and so $f\in{\overline{\mathscr{P}}}(N_{\mathbb{R}},\Delta)$ . ∎

Proposition 3.81.

Let $\Delta$ be a lattice polytope of $M_{\mathbb{R}}$ . Then the subset of rational piecewise affine concave functions in ${\overline{\mathscr{P}}}(\Delta,N_{\mathbb{R}})$ (respectively, in ${\overline{\mathscr{P}}}(N_{\mathbb{R}},\Delta)$ ) is dense with respect to uniform convergence.

Proof.

This follows from Proposition 3.80 and the density of rational numbers. ∎

3.6. Differences of concave functions

Let $C\subset N_{\mathbb{R}}$ be a convex set. A function $f\colon C\to\mathbb{R}$ is called a difference of concave functions or a DC function if it can be written as $f=g-h$ for concave functions $g,h\colon C\to\mathbb{R}$ . DC functions play an important role in non-convex optimization and have been widely studied, see for instance [HT99] and the references therein. We will be interested in a subclass of DC functions, namely those which are a difference of uniform limits of piecewise affine concave functions.

Definition 3.82.

For a convex polyhedron $\Lambda$ in $N_{\mathbb{R}}$ we set

{\mathscr{D}}(\Lambda)=\{g-h\mid g,h\in\mathscr{P}(\Lambda)\},\quad{\overline{\mathscr{D}}}(\Lambda)=\{g-h\mid g,h\in{\overline{\mathscr{P}}}(\Lambda)\}.

These spaces are closed under the operations of taking finite linear combinations, upper envelope and lower envelope.

Proposition 3.83.

Let $\Lambda$ be a convex polyhedron in $N_{\mathbb{R}}$ and $f_{1},\dots,f_{l}$ functions in ${\mathscr{D}}(\Lambda)$ (respectively, in ${\overline{\mathscr{D}}}(\Lambda)$ ). Then the functions

(1)

$\sum_{i}\lambda_{i}f_{i}$ for any $\lambda_{i}\in\mathbb{R}$ ,
(2)

$\max_{i}\{f_{i}\}$ , $\min_{i}\{f_{i}\}$

are also in ${\mathscr{D}}(\Lambda)$ (respectively, in ${\overline{\mathscr{D}}}(\Lambda)$ ).

Proof.

Statement (1) is obvious. For the statement (2), write $f_{i}=g_{i}-h_{i}$ with $g_{i},h_{i}$ in $\mathscr{P}(\Lambda)$ (respectively, in ${\overline{\mathscr{P}}}(\Lambda)$ ). Then the upper envelope admits the DC decomposition $\max_{i}\{f_{i}\}=g-h$ with

g:=\sum_{j}g_{j},\quad h:=\min_{i}\bigg(h_{i}+\sum_{j\neq i}g_{j}\bigg),

which are both concave functions in $\mathscr{P}(\Lambda)$ (respectively, in ${\overline{\mathscr{P}}}(\Lambda)$ ). This shows that $\max_{i}\{f_{i}\}$ is in $\mathscr{D}(\Lambda)$ (respectively, in ${\overline{\mathscr{D}}}(\Lambda)$ ). The statement for the lower envelope follows similarly. ∎

In particular, if $f$ lies in $\mathscr{D}(\Lambda)$ or in ${\overline{\mathscr{D}}}(\Lambda)$ , the same holds for the functions $|f|$ , $\max(f,0)$ and $\min(f,0)$ .

Corollary 3.84.

The space $\mathscr{D}(\Lambda)$ coincides with the space of piecewise affine functions on $\Lambda$ .

Proof.

This follows from the max-min representation of piecewise affine functions in [Ovc02] and Proposition 3.83(2). ∎

Some constructions for concave functions can be extended to this kind of functions. In particular, we can define the recession of a functions in ${\overline{\mathscr{D}}}(\Lambda)$ .

Definition 3.85.

Let $\Lambda$ be a polyhedron in $N_{\mathbb{R}}$ and $f\in{\overline{\mathscr{D}}}(\Lambda)$ . The recession function of $f$ is defined as

(3.86)

\operatorname{rec}(f)\colon\operatorname{rec}(\Lambda)\longrightarrow\mathbb{R},\quad u\longmapsto\lim_{\lambda\to\infty}\frac{f(v_{0}+\lambda u)-f(v_{0})}{\lambda}

for any $v_{0}\in\Lambda$ .

Write $f=g-h$ for any $g,h\in{\overline{\mathscr{P}}}(\Lambda)$ . By (3.49), we have that, for all $u\in\operatorname{rec}(\Lambda)$ , the limit (3.86) exists and

\operatorname{rec}(f)(u)=\operatorname{rec}(g)(u)-\operatorname{rec}(h)(u).

Observe that the recession function of a function in $\mathscr{D}(\Lambda)$ is a piecewise linear function on a subdivision of the cone $\operatorname{rec}(\Lambda)$ into polyhedral cones. Observe also that

|f-\operatorname{rec}(f)|\leq|g-\operatorname{rec}(g)|+|h-\operatorname{rec}(h)|=O(1).

We will be mostly interested in the case when $\Lambda=N_{\mathbb{R}}$ .

Proposition 3.87.

Let $\|\cdot\|$ be any metric on $N_{\mathbb{R}}$ and $f\in{\overline{\mathscr{D}}}(N_{\mathbb{R}})$ . Then there exists a constant $\kappa>0$ such that, for all $u,v\in N_{\mathbb{R}}$ ,

|f(u)-f(v)|\leq\kappa\|u-v\|.

A function which verifies the conclusion of this proposition is called Lipchitzian.

Proof.

Let $f=g-h$ with $g,h\in{\overline{\mathscr{P}}}(N_{\mathbb{R}})$ . The effective domain of the recessions of $g$ and of $h$ is the whole of $N_{\mathbb{R}}$ . By [Roc70, Theorem 10.5], both $g$ and $h$ are Lipchitzians, hence so is $f$ . ∎

Observe that ${\overline{\mathscr{D}}}(N_{\mathbb{R}})$ is not the completion of ${\mathscr{D}}(N_{\mathbb{R}})$ with respect to uniform convergence. It is easy to construct functions which are uniform limits of piecewise affine ones but do not verify the Lipschitz condition.

We will consider the integral and rational structures on the space of piecewise affine functions. We will use the notation previous to Definition 3.73.

Definition 3.88.

Let $\Lambda$ be a convex polyhedron and $f\in{\mathscr{D}}(\Lambda)$ . We say that $f$ is an H-lattice (respectively V-lattice) function if it can be written as the difference of two H-lattice (respectively V-lattice) concave functions. We say that $f$ is a rational piecewise affine function if it is the difference of two rational piecewise affine concave functions.

Proposition 3.89.

If $f$ is an H-lattice function (respectively a rational piecewise affine function) on $N_{\mathbb{R}}$ , then there is a complete polyhedral complex $\Pi$ in $N_{\mathbb{R}}$ such that, for every $\Lambda\in\Pi$ ,

f|_{\Lambda}(u)=\langle m_{\Lambda},u\rangle+l_{\Lambda},

with $(m_{\Lambda},l_{\Lambda})\in M\times\mathbb{Z}$ (respectively $(m_{\Lambda},l_{\Lambda})\in M_{\mathbb{Q}}\times\mathbb{Q}$ ). Conversely, every piecewise affine function on $N_{\mathbb{R}}$ such that its defining affine functions have integral (respectively rational) coefficients, is an H-lattice function (respectively a rational piecewise affine function).

Proof.

We will prove the statement for lattice functions. The statement for rational piecewise affine functions is proved with the same argument. If $f$ is an H-lattice function, we can write $f=g-h$ , where $g$ and $h$ are H-lattice concave functions. We obtain $\Pi$ as any common refinement of $\Pi(g)$ and $\Pi(h)$ to a polyhedral complex. Then the statement follows from the definition of H-lattice concave functions. The converse is an easy consequence of Corollary 3.84. ∎

Definition 3.90.

Let $f$ be a rational piecewise affine function on $N_{\mathbb{R}}$ , and let $\Pi$ and $\{(m_{\Lambda},l_{\Lambda})\}_{\Lambda\in\Pi}$ be as in Proposition 3.89. The family $\{(m_{\Lambda},l_{\Lambda})\}_{\Lambda\in\Pi}$ is called a set of defining vectors of $f$ .

Proposition 3.91.

Let $\Pi$ be a complete SCR polyhedral complex in $N_{\mathbb{R}}$ and $f$ an H-lattice function on $\Pi$ . Then $\operatorname{rec}(f)$ is a conic H-lattice function on the fan $\operatorname{rec}(\Pi)$ .

Proof.

Let $\Lambda\in\Pi$ and $(m,l)\in M\times\mathbb{Z}$ such that $f(u)=\langle m,u\rangle+l$ for $u\in\Lambda$ . Then, by the definition of $\operatorname{rec}(f)$ , it is clear that $\operatorname{rec}(f)|_{\operatorname{rec}(\Lambda)}(u)=\langle m,u\rangle$ . Hence, $\operatorname{rec}(f)$ is a conic H-lattice function on $\operatorname{rec}(\Pi)$ . ∎

3.7. Monge-Ampère measures

Let $f\colon C\to\mathbb{R}$ be a concave function of class ${\mathcal{C}}^{2}$ on an open convex set $C\subset\mathbb{R}^{n}$ . Its Hessian matrix

\operatorname{Hess}(f)(u):=\left(\frac{\partial^{2}f}{\partial u_{i}\partial u_{j}}(u)\right)_{1\leq i,j\leq n}

is a non-positive definite matrix which quantifies the curvature of $f$ at the point $u$ . The real Monge-Ampère operator is defined as $(-1)^{n}$ times the determinant of this matrix. This notion can be extended as a measure to the case of an arbitrary concave function. A good reference for Monge-Ampère measures is [RT77].

Let $\mu$ be a Haar measure of $M_{\mathbb{R}}$ . Assume that we choose linear coordinates $(x_{1},\dots,x_{n})$ of $M_{\mathbb{R}}$ such that $\mu$ is the measure associated to the differential form $\omega=\,\text{\rm d}x_{1}\land\dots\land\,\text{\rm d}x_{n}$ and the orientation of $M_{\mathbb{R}}$ defined by this system of coordinates. Let $(u_{1},\dots,u_{n})$ be the dual coordinates of $N_{\mathbb{R}}$ .

Definition 3.92.

Let $f$ be a concave function on $N_{\mathbb{R}}$ . The real Monge-Ampère measure of $f$ with respect to $\mu$ is defined, for a Borel subset $E$ of $N_{\mathbb{R}}$ , as

{\mathcal{M}}_{\mu}(f)(E)=\mu(\partial f(E)).

It is a measure with support contained in ${\operatorname{dom}}(\partial f)$ . The correspondence $f\mapsto{\mathcal{M}}_{\mu}(f)$ is called the Monge-Ampère operator.

When the measure $\mu$ is clear from the context, we will drop it from the notation. Moreover, since we are not going to consider complex Monge-Ampère measures, we will simply call ${\mathcal{M}}_{\mu}(f)$ the Monge-Ampère measure of $f$ .

The total mass of ${\mathcal{M}}_{\mu}(f)$ is equal to $\mu(\operatorname{stab}(f))$ . In particular, when $\operatorname{stab}(f)$ is bounded, ${\mathcal{M}}_{\mu}(f)$ is a finite measure.

Proposition 3.93.

The Monge-Ampère measure is a continuous map from the space of concave functions with the topology defined by uniform convergence on compact sets to the space of $\sigma$ -finite measures on $N_{\mathbb{R}}$ with the weak topology.

Proof.

This is proved in [RT77, §3]. ∎

The two basic examples of Monge-Ampère measures that we are interested in are the ones associated to smooth functions and the ones associated to piecewise linear functions.

Proposition 3.94.

Let $C$ be an open convex set in $N_{\mathbb{R}}$ and $f\in{\mathcal{C}}^{2}(C)$ a concave function. Then

{\mathcal{M}}_{\mu}(f)=(-1)^{n}\det(\operatorname{Hess}(f))\,\text{\rm d}u_{1}\land\dots\land\,\text{\rm d}u_{n},

where the Hessian matrix is calculated with respect to the coordinates $(u_{1},\dots,u_{n})$ .

Proof.

This is [RT77, Proposition 3.4] ∎

By contrast, the Monge-Ampère measure of a piecewise affine concave function, is a discrete measure supported on the vertices of a polyhedral complex.

Proposition 3.95.

Let $f$ be a piecewise affine concave function on $N_{\mathbb{R}}$ and $(\Pi(f),\Pi(f^{\vee}))$ the dual pair of polyhedral complexes associated to $f$ . Denote by $\Lambda\mapsto\Lambda^{\ast}$ the correspondence $\mathcal{L}f$ . Then

{\mathcal{M}}_{\mu}(f)=\sum_{v\in\Pi(f)^{0}}\mu(\partial f(v))\delta_{v}=\sum_{v\in\Pi(f)^{0}}\mu(v^{\ast})\delta_{v}=\sum_{\Lambda\in\Pi(f^{\vee})^{n}}\mu(\Lambda)\delta_{\Lambda^{\ast}},

where $\delta_{v}$ is the Dirac measure supported on $v$ .

Proof.

This follows easily from the definition of ${\mathcal{M}}(f)$ and the properties of the Legendre correspondence of piecewise affine functions. ∎

Example 3.96.

Let $\Delta\subset M_{\mathbb{R}}$ be a polytope and $\Psi_{\Delta}$ its support function. Then

{\mathcal{M}}_{\mu}(\Psi_{\Delta})=\mu(\Delta)\delta_{0}.

The following relation between Monge-Ampère measure and Legendre-Fenchel duality is one of the key ingredients in the computation of the height of a toric variety. We will consider the $(n-1)$ -differential form on $N_{\mathbb{R}}$

\lambda=\sum_{i=1}^{n}(-1)^{i-1}x_{i}\,\text{\rm d}x_{1}\land\dots\land\widehat{\,\text{\rm d}x_{i}}\land\dots\land\,\text{\rm d}x_{n}.

It satisfies $\,\text{\rm d}\lambda=n\omega$ .

Theorem 3.97.

Let $f\colon N_{\mathbb{R}}\to\mathbb{R}$ be a closed concave function, such that $D:=\operatorname{stab}(f)$ is a compact convex set with piecewise smooth boundary $\partial D$ . Then

(3.98)

-n!\int_{N_{\mathbb{R}}}f{\mathcal{M}}_{\mu}(f)=(n+1)!\int_{D}f^{\vee}\,\text{\rm d}\mu-n!\int_{\partial D}f^{\vee}\lambda.

Proof.

If the measure of $D$ is zero then both sides of equation (3.98) are zero. Therefore, the theorem is trivially true in this case. Thus, we may assume that $D$ has non-empty interior. Since $\operatorname{stab}(f)$ is compact, the right-hand side of (3.98) is continuous with respect to uniform convergence of functions, thanks to Proposition 3.18. Moreover, Proposition 3.93 and the fact that ${\mathcal{M}}_{\mu}(f)$ is finite imply that the left-hand side is also continuous with respect to uniform convergence. By the compacity of $D$ , we can find a sequence of strictly concave smooth functions $(f_{n})_{n\geq 1}$ that converges uniformly to $f$ . Hence, we may assume that $f$ is smooth and strictly concave. In this case, the Legendre transform $\nabla f\colon N_{\mathbb{R}}\to D^{\circ}$ is a diffeomeorphism.

By the definition of the Monge-Ampère measure,

(3.99)

-n!\int_{N_{\mathbb{R}}}f{\mathcal{M}}_{\mu}(f)=-n!\int_{D}f((\nabla f)^{-1}x)\,\text{\rm d}\mu(x),

which, in particular, shows that the integral on the left is convergent for smooth strictly concave functions with compact stability set. Therefore, it is convergent for any concave function within the hypothesis of the theorem.

By the properties of the Legendre transform,

(3.100)

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

Moreover,

	$\displaystyle\,\text{\rm d}(f^{\vee}\lambda)(x)$	$\displaystyle=\,\text{\rm d}f^{\vee}\land\lambda(x)+f^{\vee}\,\text{\rm d}\lambda(x)$
		$\displaystyle=\langle\nabla f^{\vee}(x),x\rangle\omega+nf^{\vee}\omega$
(3.101)			$\displaystyle=\langle(\nabla f)^{-1}(x),x\rangle\omega+nf^{\vee}\omega$

The result is obtained by combining equations (3.99), (3.100) and (3.101) with Stokes’ theorem. ∎

We now particularize Theorem 3.97 to the case when the Haar measure comes from a lattice and the convex set is a lattice polytope of maximal dimension.

Definition 3.102.

Let $L$ be a lattice and set $L_{\mathbb{R}}=L\otimes\mathbb{R}$ . We denote by $\operatorname{vol}_{L}$ the Haar measure on $L_{\mathbb{R}}$ normalized so that $L$ has covolume $1$ .

Let $N$ be a lattice of $N_{\mathbb{R}}$ and set $M=N^{\vee}$ for its dual lattice. For a concave function $f$ , we denote by $\mathcal{M}_{M}(f)$ the Monge-Ampère measure with respect to the normalized Haar measure $\operatorname{vol}_{M}$ .

Notation 3.103.

Let $\Lambda$ be a rational polyhedron in $M_{\mathbb{R}}$ and $\operatorname{aff}(\Lambda)$ its affine hull. We denote by $L_{\Lambda}$ the linear subspace of $M_{\mathbb{R}}$ associated to $\operatorname{aff}(\Lambda)$ and by $M(\Lambda)$ the induced lattice $M\cap L_{\Lambda}$ . By definition, $\operatorname{vol}_{M(\Lambda)}$ is a measure on $L_{\Lambda}$ , and we will denote also by $\operatorname{vol}_{M(\Lambda)}$ the measure induced on $\operatorname{aff}(\Lambda)$ . If $v\in N_{\mathbb{R}}$ is orthogonal to $L_{\Lambda}$ , we define $\langle v,\Lambda\rangle=\langle v,x\rangle$ for any $x\in\Lambda$ . Furthermore, when $\dim(\Lambda)=n$ and $F$ is a facet of $\Lambda$ , we will denote by $v_{F}\in N$ the vector of minimal length that is orthogonal to $L_{F}$ and satisfies $\langle v_{F},F\rangle\leq\langle v_{F},x\rangle$ for each $x\in\Lambda$ . In other words, $v_{F}$ is the minimal inner integral orthogonal vector of $F$ as a facet of $\Lambda$ .

Corollary 3.104.

Let $f$ be a concave function on $N_{\mathbb{R}}$ such that $\Delta=\operatorname{stab}(f)$ is a lattice polytope of dimension $n$ . Then

-n!\int_{N_{\mathbb{R}}}f{\mathcal{M}}_{M}(f)=(n+1)!\int_{\Delta}f^{\vee}\,\text{\rm d}\operatorname{vol}_{M}+\sum_{F}\langle v_{F},F\rangle n!\int_{F}f^{\vee}\,\text{\rm d}\operatorname{vol}_{M(F)},

where the sum is over the facets $F$ of $\Delta$ .

Proof.

We choose $(m_{1},\dots,m_{n})$ a basis of $M$ such that $(m_{2},\dots,m_{n})$ is a basis of $M(F)$ and $m_{1}$ points to the exterior direction. Expressing $\lambda$ in this basis we obtain

\lambda|_{F}=-\langle v_{F},F\rangle\,\text{\rm d}\operatorname{vol}_{M(F)}.

The result then follows from Theorem 3.97. ∎

In §6, we will see that we can express the height of a toric variety in terms of integrals of the form $\int_{\Delta}f^{\vee}\,\text{\rm d}\operatorname{vol}_{M}$ as in the above result. In some situations, it will be useful to translate those integrals to integrals on $N_{\mathbb{R}}$ .

Let $f\colon N_{\mathbb{R}}\to\mathbb{R}$ be a concave function and $g\colon\operatorname{stab}(f)\to\mathbb{R}$ an integrable function. We consider the signed measure on $N_{\mathbb{R}}$ defined, for a Borel subset $E$ of $N_{\mathbb{R}}$ , as

{\mathcal{M}}_{M,g}(f)(E)=\int_{\partial f(E)}g\,\text{\rm d}\operatorname{vol}_{M}.

Clearly, ${\mathcal{M}}_{M,g}(f)$ is uniformly continuous with respect to ${\mathcal{M}}_{M}(f)$ . By the Radon-Nicodym theorem, there is a ${\mathcal{M}}_{M}(f)$ -measurable function, that we denote $g\circ\partial f$ , such that

(3.105)

\int_{E}g\circ\partial f\,{\mathcal{M}}_{M}(f)=\int_{E}{\mathcal{M}}_{M,g}(f)=\int_{\partial f(E)}g\,\text{\rm d}\operatorname{vol}_{M}.

Example 3.106.

When the function $f$ is differentiable or piecewise affine, the measurable function $f^{\vee}\circ\partial f$ can be made explicit.

(1)

Let $f\in{\mathcal{C}}^{2}(N_{\mathbb{R}})$ . Proposition 3.94 and the change of variables formula imply $g\circ\partial f=g\circ\nabla f$ . For the particular case when $g=f^{\vee}$ , Theorem 3.52(4) implies, for $u\in N_{\mathbb{R}}$ ,

$f^{\vee}\circ\partial f(u)=\langle\nabla f(u),u\rangle-f(u).$

(2)

Let $f$ a piecewise affine concave function on $N_{\mathbb{R}}$ . By Proposition 3.95, ${\mathcal{M}}_{M}(f)$ is supported in the finite set $\Pi(f)^{0}$ and so is ${\mathcal{M}}_{M,g}(f)$ . For $v\in\Pi(f)^{0}$ write $v^{*}\in\Pi(f^{\vee})^{n}$ for the dual polyhedron. Then $g\circ\partial f(v)=\frac{1}{\operatorname{vol}_{M}(v^{*})}\int_{v^{*}}g\,\text{\rm d}\operatorname{vol}_{M}$ , which implies

f^{\vee}\circ\partial f(v)=\frac{1}{\operatorname{vol}_{M}(v^{*})}\int_{v^{*}}\langle x,v\rangle\,\text{\rm d}\operatorname{vol}_{M}-f(v).

The function $f^{\vee}\circ\partial f$ is defined as a ${\mathcal{M}}_{M}(f)$ -measurable function. Therefore, only its values at the points $v\in\Pi(f)^{0}$ are well defined. Nevertheless, we can extend the function $f^{\vee}\circ\partial f$ to the whole $N_{\mathbb{R}}$ by writing

f^{\vee}\circ\partial f(u)=\frac{1}{\operatorname{vol}_{\mu}(\partial f(u))}\int_{\partial f(u)}\langle x,u\rangle\,\text{\rm d}\mu-f(u)

for any Haar measure $\mu$ on the affine space determined by $\partial f(u)$ .

The Monge-Ampère operator is homogeneous of degree $n$ . It can be turned into a multi-linear operator which takes $n$ concave functions as arguments.

Definition 3.107.

Let $f_{1},\dots,f_{n}$ be concave functions on $N_{\mathbb{R}}$ . The mixed Monge-Ampère measure is defined by the formula

{\mathcal{M}}_{M}(f_{1},\dots,f_{n})=\frac{1}{n!}\sum_{j=1}^{n}(-1)^{n-j}\sum_{1\leq i_{1}<\cdots<i_{j}\leq n}{\mathcal{M}}_{M}(f_{i_{1}}+\dots+f_{i_{j}}).

It is a measure on $N_{\mathbb{R}}$ .

This operator was introduced by Passare and Rullgård [PR04]. It is multi-linear and symmetric in the variables $f_{i}$ .

Proposition 3.108.

The mixed Monge-Ampère measure is a continuous map from the space of $n$ -tuples of concave functions with the topology defined by uniform convergence on compact sets to the space of $\sigma$ -finite measures on $N_{\mathbb{R}}$ with the weak topology.

Proof.

The general mixed case reduces to the unmixed case $f_{1}=\dots=f_{n}$ , which is Proposition 3.93. ∎

Definition 3.109.

The mixed volume of a family of compact convex sets $Q_{1},\dots,Q_{n}$ of $M_{\mathbb{R}}$ is defined as

(3.110)

\operatorname{MV}_{M}(Q_{1},\dots,Q_{n})=\sum_{j=1}^{n}(-1)^{n-j}\sum_{1\leq i_{1}<\cdots<i_{j}\leq n}\operatorname{vol}_{M}(Q_{i_{1}}+\cdots+Q_{i_{j}})

Since $\operatorname{MV}_{M}(Q,\dots,Q)=n!\,\operatorname{vol}_{M}(Q)$ , the mixed volume is a generalization of the volume of a convex body. The mixed volume is symmetric and linear in each variable $Q_{i}$ with respect to the Minkowski sum, and monotone with respect to inclusion [Ewa96, Chapter IV].

The next result generalizes [PR04, Proposition 3] and shows that the mixed Monge-Ampère measure can be defined in terms of mixed volumes if the effective domains of the functions overlap sufficiently.

Proposition 3.111.

Let $f_{1},\dots,f_{n}$ be concave functions such that $\operatorname{ri}({\operatorname{dom}}(f_{1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{n}))\neq\emptyset$ and $E\subset N_{\mathbb{R}}$ a Borel subset. Then

{\mathcal{M}}_{M}(f_{1},\dots,f_{n})(E)=\frac{1}{n!}\operatorname{MV}_{M}(\partial f_{1}(E),\dots,\partial f_{n}(E)).

If $f_{1},\dots,f_{k}$ are piecewise affine, this formula holds under the weaker hypothesis ${\operatorname{dom}}(f_{1})\cap\dots\cap{\operatorname{dom}}(f_{k})\cap\operatorname{ri}({\operatorname{dom}}(f_{k+1}))\cap\dots\cap\operatorname{ri}({\operatorname{dom}}(f_{n}))\neq\emptyset$ .

Proof.

This follows from Proposition 3.43 and the definition of the mixed Monge-Ampère measures and of mixed volumes. ∎

In particular, this gives the total mass of the mixed Monge-Ampère measure.

Corollary 3.112.

In the setting of Proposition 3.111, we have

{\mathcal{M}}_{M}(f_{1},\dots,f_{n})(N_{\mathbb{R}})=\frac{1}{n!}\operatorname{MV}_{M}(\operatorname{stab}(f_{1}),\dots,\operatorname{stab}(f_{n})).

Proof.

This follows readily from the above proposition and (3.22). ∎

Following [PS08a], we introduce an extension of the notion of integral of a concave function.

Definition 3.113.

Let $Q_{i}$ , $i=0,\dots,n$ , be a family of compact convex subset of $M_{\mathbb{R}}$ and $g_{i}\colon Q_{i}\to\mathbb{R}$ a concave function on $Q_{i}$ . The mixed integral of $g_{0},\dots,g_{n}$ is defined as

\operatorname{MI}_{M}(g_{0},\dots,g_{n})=\sum_{j=0}^{n}(-1)^{n-j}\sum_{0\leq i_{0}<\cdots<i_{j}\leq n}\int_{Q_{i_{0}}+\cdots+Q_{i_{j}}}g_{i_{0}}\boxplus\cdots\boxplus g_{i_{j}}\,\text{\rm d}\operatorname{vol}_{M}.

For a compact convex subset $Q\subset M_{\mathbb{R}}$ and a concave function $g$ on $Q$ , we have $\operatorname{MI}_{M}(g,\dots,g)=(n+1)!\int_{Q}g\,\text{\rm d}\operatorname{vol}_{M}$ . The mixed integral is symmetric and additive in each variable $g_{i}$ with respect to the sup-convolution. For a scalar $\lambda\in\mathbb{R}_{\geq 0}$ , we have $\operatorname{MI}_{M}(\lambda g_{0},\dots,\lambda g_{n})=\lambda\operatorname{MI}_{M}(g_{0},\dots,g_{n})$ . We refer to [PS08a, PS08b] for the proofs and more information about this notion.