Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 1, 297-302.

Max-Min Representation of Piecewise Linear Functions

Sergei Ovchinnikov

Mathematics Department, San Francisco State University San Francisco, CA 94132 e-mail: sergei@sfsu.edu

Abstract. It is shown that a piecewise linear function on a convex domain in ℝ^{d} can be represented as a boolean polynomial in terms of its linear components.

1. Introduction

Let f be a piecewise linear function on ℝ defined by

f(x) = \begin{cases}g_{1}(x) = 2 x + 1, & x ≤ 1, \\ g_{2}(x) = 5 − 2 x, & 1 ≤ x ≤ 2, \\ g_{3}(x) = 0.5 x, & x ≥ 2. \end{cases}

The graph of this function is shown in Fig. 1.

[figure: x; y; g_{1}; g_{2}; g_{3}]

Fig. 1 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2002 Heldermann Verlag

This function can be also represented as follows.

f(x) = [g_{1}(x) ∧ g_{2}(x)] ∨ [g_{1}(x) ∧ g_{3}(x)], ∀x ∈ ℝ,  (1)

where ∧ and ∨ stand for operations Min and Max, respectively. In other words, f is represented as Max-Min boolean polynomial in variables g_{1}, g_{2}, g_{3} and the polynomial is written in its disjunctive normal form.

The main goal of the paper is to establish this representation for piecewise linear functions on closed convex domains in ℝ^{d} (Theorem 2.1). We also discuss the optimization problem for this representation.

2. Representation theorem

In the paper, a closed domain in ℝ^{d} is the closure of an open set in ℝ^{d} and a linear function on ℝ^{d} is a function in the form

h(x) = a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{d}x_{d} + b,

where x = (x_{1}, …, x_{d}). We begin with the following definition.

Definition 2.1. Let Γ be a closed convex domain in ℝ^{d}. A function f : Γ → ℝ is said to be piecewise linear if there is a finite family Q of closed domains such that Γ = ∪Q and f is linear on every domain in Q. A linear function g on ℝ^{d} which coincides with f on some Q ∈ Q is said to be a component of f.

Clearly, any piecewise linear function on Γ is continuous. The following theorem is the main result of the paper.

Theorem 2.1. Let f be a piecewise linear function on Γ and {g_{1}, …, g_{n}} be the set of its distinct components. There exists a family {S_{j}}_{j∈J} of incomparable (with respect to ⊆) subsets of {1, …, n} such that

f(x) = ⋁_{j∈J} ⋀_{i∈S_{j}} g_{i}(x), ∀x ∈ Γ.  (2)

Here, ∨ and ∧ are operations of maximum and minimum, respectively. The expression on the right side in (2) is a disjunctive normal form of a Max-Min polynomial in the variables g_{i}.

We begin our proof with a simple geometric observation.

Lemma 2.1. Let f be a piecewise linear function on [a, b] ⊂ ℝ and {g_{1}, …, g_{n}} be the set of its components. There exists k such that

g_{k}(a) ≤ f(a) and g_{k}(b) ≥ f(b).  (3)

Proof. Let {ℓ_{1}, … ℓ_{m}} be the set of closed line segments on ℝ^{2} constituting the graph of f. We assume that these line segments are enumerated in the direction from a to b. Let g_{n(i)} be the component defining ℓ_{i}, and let m be the slope of the line segment [(a, f(a)), (b, f(b))]. If the slope of g_{n(1)} (resp. g_{n(m)}) is greater than or equal to m, then g_{n(1)} (resp. g_{n(m)}) satisfies conditions (3). It remains to consider the case when the slopes of g_{n(1)} and g_{n(m)} are smaller than m (see Fig. 2).

[figure: x; y; (a, f(a)); (b, f(b)); ℓ_{1}; ℓ_{p}; ℓ_{m}]

Fig. 2

Clearly, there is ℓ_{p} with the slope greater than m that intersects the line segment [(a, f(a)), (b, f(b))]. Then g_{n(p)} satisfies conditions (3).

The statement of the next lemma follows immediately from Lemma 2.1.

Lemma 2.2. Let f be a piecewise linear function on Γ and {g_{1}, …, g_{n}} be the set of its components. For given points a, b ∈ Γ, there is k such that

g_{k}(a) ≤ f(a) and g_{k}(b) ≥ f(b).  (4)

Proof. Consider the restriction of f to [a, b] and apply Lemma 2.1.

Now we proceed with the proof of Theorem 2.1.

Proof. For a given a ∈ Γ, let us define

S_{a} = {i ∈ {1, …, n} : g_{i}(a) ≥ f(a)}  (5)

and

F_{a}(x) = ⋀_{i∈S_{a}} g_{i}(x).

Clearly, F_{a}(a) = f(a). By Lemma 2.2, for any b ∈ Γ,

F_{b}(a) = ⋀_{i∈S_{b}} g_{i}(a) ≤ f(a).

Hence,

f(x) = ⋁_{a∈Γ} ⋀_{i∈S_{a}} g_{i}(x), ∀x ∈ Γ.  (6)

Let {S_{j}}_{j∈J} be the family of distinct minimal elements (with respect to ⊆) in the family {S_{a}}_{a∈Γ}. Clearly, (6) implies (2).

Corollary 2.1. Let Γ be a star-shape domain in ℝ^{d} such that its boundary ∂Γ is a polyhedral complex. Let f be a function on ∂Γ such that its restriction to each (d − 1)-dimensional polyhedron in ∂Γ is a linear function on it. Then f admits representation (2).

Proof. Let a be a central point in Γ. For x ∈ ℝ^{d}, x ≠ a, let x̃ be the unique intersection point of the ray from a through x with ∂Γ. We define

f̃(x) = \begin{cases}\frac{∥x−a∥}{∥x̃−a∥}f(x̃) & for x ≠ a, \\ 0 & for x = a. \end{cases}

Clearly, f̃ is a piecewise linear function on ℝ^{d} and f̃|_{∂Γ} = f. Thus f admits representation (2).

Formula (2) is not very effective in the sense that the same component can appear in different ‘monomials’ in (2). For instance, g_{2} appears twice in (1). On the other hand, (1) can be written in the form

f(x) = g_{1}(x) ∧ [g_{2}(x) ∨ g_{3}(x)], ∀x ∈ ℝ,

where each component appears only once. Note that this representation is not in the disjunctive normal form. By modifying the technique presented in [2], one can show that in one-dimensional case any piecewise linear function admits a boolean representation in which each component appears in the formula exactly once. An example in [2] shows that it is not true in higher dimensions.

The reviewer of the paper suggested a more effective boolean representation in the disjunctive normal form than that given by (2). In what follows, we describe this construction. The proof uses only a minor modification of the techniques used in the proof of Theorem 2.1 and is omitted.

Let H be the set of all hyperplanes that are nonempty solution sets of the equations in the form g_{i}(x) = g_{j}(x) for i < j and have nonempty intersections with the interior int(Γ) of Γ. We consider H as a hyperplane arrangement [1] and denote T the family of nonempty intersections of the regions of H with int(Γ). We use the same name ‘region’ for elements of T . It is easy to see that the components g_{i} are linearly ordered over any region in T and that for any P ∈ T , a, b ∈ P implies S_{a} = S_{b} (see (5)). Consider now the pairs (g_{i}, g_{j}) for i < j that satisfy the following conditions:

(i) There are adjacent regions P, Q ∈ T such that g_{i}(x) = f(x) on P and g_{j}(x) = f(x) on Q.

(ii) f(x) = g_{i}(x) ∨ g_{j}(x) on P ∪ Q. Let H′ be the hyperplane arrangement defined by these pairs. We may assume that H′ is nonempty. (Otherwise, f is a concave function and we have a trivial representation.) We denote T′ the set of regions in Γ defined by H′ and define S_{P} = {i ∈ {1, …, n} : g_{i}(x) ≥ f(x), x ∈ P, P ∈ T′}. The sets S_{P} are incomparable and define the following representation

f(x) = ⋁_{P ∈T′} ⋀_{i∈S_{P}} g_{i}(x), ∀x ∈ Γ.

Since S_{P} ⊆ S_{a} for a ∈ P, the above formula, in general, is more effective than (2).

3. Concluding remarks

1. The statement of Theorem 2.1 also holds for piecewise linear functions from Γ to ℝ^{m}. Namely, let f : Γ → ℝ^{m} be a piecewise linear function and {g_{1}, …, g_{n}} be the set of its distinct components. We denote

f = (f_{1}, …, f_{m}) and g_{k} = (g_{1}^{(k)}, …, g_{m}^{(k)}), for 1 ≤ k ≤ n.

There exists a family {S_{j}^{k}}_{j∈J, 1≤k≤n} of subsets of {1, …, n} such that

f_{k}(x) = ⋁_{j∈J} ⋀_{i∈S_{j}^{k}} g_{i}^{(k)}(x), ∀x ∈ Γ, 1 ≤ k ≤ m.

The converse is also true.

2. The convexity of Γ is an essential assumption. Consider, for instance, the domain Γ = {(x_{1}, x_{2}) ∈ ℝ^{2} : x_{2} ≤ |x_{1}| } and define

f(x) = \begin{cases}x_{2} & for min\{x_{1}, x_{2}\} ≥ 0, \\ 0 & otherwise, \end{cases}

where x = (x_{1}, x_{2}). This piecewise linear function has two components, g_{1}(x) = x_{2} and g_{2}(x) = 0, but is not representable in the form (2).

3. Likewise, (2) is not true for piecewise polynomial functions as the following example (due to B. Sturmfels) illustrates. Let Γ = ℝ^{1}. We define

f(x) = \begin{cases}0 & for x ≤ 0, \\ x^{2} & for x > 0. \end{cases}

4. It follows from Theorem 2.1 that any piecewise linear function on a closed convex domain in ℝ^{d} can be extended to a piecewise linear function on the entire space ℝ^{d}.

5. By using the techniques presented in the paper, a representation theorem can be established for smooth functions on closed domains in ℝ^{d} [3]. In this case, the role of components is played by tangent hyperplanes.

Acknowledgments. The author thanks S. Gelfand, O. Musin, B. Sturmfels, and G. Ziegler for helpful discussions on the earlier versions of the paper. He is especially grateful to the anonymous referee for constructive suggestions. This work was partly supported by NSF grant SES–9986269 to J.-Cl. Falmagne at University of California, Irvine.

References

[1] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M.: Oriented Matroids.

Second Edition, Encyclopedia of Mathematics, Vol. 46, Cambridge University Press 1999. Zbl 0944.52006 [2] Dobkin, D.; Guibas, L.; Hershberger, J.; Snoeyink, J.: An efficient algorithm for finding

the CSG representation of a simple polygon. Algorithmica 10 (1993), 1–23.

Zbl 0777.68076

[3] Ovchinnikov, S.: Boolean representation of manifolds and functions. J. Math. Analysis and

   Appl. (submitted), e-print available at http://xxx.lanl.gov/abs/math.CA/0102007.

Received October 12, 2000