3.6. Differences of concave functions [02N5]

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