3.5. The piecewise affine case [02M8]

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.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. ∎