3.3. Operations on concave functions and duality [02LH]

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