Journal of Convex Analysis Volume 7 (2000), No. 1, 73–94

Piecewise Affine Selections for Piecewise Polyhedral Multifunctions and Metric Projections

M. Finzel

Mathematisches Institut, Universität Erlangen-Nürnberg, Bismarckstrasse 1 1/2, 91054 Erlangen, Germany. e-mail: finzel@mi.uni-erlangen.de

W. Li

Department of Mathematics and Statistics, Old Dominion University, Norfolk, VA 23529-0077, USA. e-mail: wuli@math.odu.edu

Received May 20, 1998 Revised manuscript received May 21, 1999

Piecewise polyhedral multifunctions are the set-valued version of piecewise affine functions. We investigate selections of piecewise polyhedral multifunctions, in particular, the least norm selection and continuous extremal point selections. A special class of piecewise polyhedral multifunctions is the collection of metric projections Π_{K,P} from ℝ^{n} (endowed with a polyhedral norm ∥ · ∥_{P}) to a polyhedral subset K of ℝ^{n}. As a consequence, the two types of selections are piecewise affine selections for Π_{K,P}. Moreover, if Π_{K,∞} and Π_{K,1} are the metric projection onto K in ℝ^{n} endowed with the ℓ_{∞}-norm and the ℓ_{1}-norm, respectively, we prove that Π_{K,1} has a piecewise affine and quasi-linear extremal point selection when K is a subspace, and that the strict best approximation sba_{K}(x) of x in K is a piecewise affine selection for Π_{K,∞}.

1. Introduction

Let ℝ^{n} be the n-dimensional vector space (of column vectors). Piecewise affine functions from ℝ^{n} to ℝ^{n} are useful in many applications. Early interest in this topic came from study of resistive networks [1, 27] and numerical solutions of nonlinear equations [6]. For recent work and references, see [5, 19, 30, 12, 13, 14]. Piecewise polyhedral multifunctions are the set-valued version of piecewise affine functions. One special class of such multifunctions is the one of metric projections Π_{K,P} from ℝ^{n} (endowed with a polyhedral norm ∥ · ∥_{P}) to a polyhedral subset K of ℝ^{n}. In many cases continuous selections of metric projections Π_{K,P} inherit the polyhedral structure of the projections, in particular, they are piecewise affine. That is why we first study piecewise affine selections for piecewise polyhedral multifunctions. Our research was motivated by Mangasarian’s least norm solution of a linear programming problem [23] as well as by special piecewise affine selections constructed for the metric projection Π_{K,1} in ℝ^{n} with the ℓ_{1}-norm, [8].

We will focus our attention to two types of piecewise affine selections of a piecewise polyhedral multifunction: the least norm solution introduced by Mangasarian [23] and continuous extremal point selections. The tools of Convex Analysis allow one to construct a continuous and piecewise affine selection of the extremal point mapping of a piecewise polyhedral mapping. Since the extremal point mapping of a piecewise polyhedral mapping has discrete image which is not convex at all, the construction of such a selection is not easy. Our construction leads to a linear programming problem. Moreover, the general

ISSN 0944-6532 / $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag

74 M. Finzel, W. Li / Piecewise affine selections for piecewise polyhedral multifunctions

theory on piecewise affine selections allows us to prove that the strict best approximation sba_{K}(x) of x in K is a piecewise affine selection for Π_{K,∞}, extending the main results in [8] and [7], respectively.

In order to describe our results more precisely, we first give the necessary notation. Recall that a subset K of ℝ^{n} is called a polyhedral subset of ℝ^{n} if K is the intersection of finitely many closed halfspaces of ℝ^{n}. In other words, K is a polyhedral subset of ℝ^{n} if and only if there exist a real l × n matrix A and a vector b ∈ ℝ^{l} such that K = {x ∈ ℝ^{n} : Ax ≥ b}, where y ≥ z means that each component of y is greater than or equal to the corresponding component of z. The interior, the boundary, the closure, and the extremal points of a subset K of ℝ^{n} will be denoted by int K, bd K, cl K, and ext K, respectively. A subset K of a closed set X in ℝ^{n} is said to be nowhere dense in X if cl(X \ cl K) = X (or K has no relative interior point of X) [18, p. 4]. The nowhere dense sets we will use here are the boundary of a closed set and hence nowhere dense in ℝ^{n} [18, p. 4]. These sets are also boundary sets in the sense of Kuratowski [20, p. 138]: A subset Y of a closed set X is said to be a boundary set with respect to X if its complement is a dense set in X, i.e., if cl(X \ Y) = X. However, in general, a boundary set in ℝ^{n} is not necessarily the boundary of another set!

For a polyhedral subset D of ℝ^{n} a collection of polyhedral subsets {D_{1}, …, D_{k}} is called a polyhedral subdivision of D if the subsets D_{i} satisfy the following three conditions:

D = ⋃_{i=1}^{k} D_{i},

dim(D_{i}) = dim D for each i, and dim(D_{i} ∩ D_{j}) < dim D for i ≠ j,

where the dimension dim D is the dimension of the affine hull of D.

A function f : D → ℝ^{m} is called piecewise affine on D if there exists a polyhedral subdivision {D_{1}, …, D_{k}} of D such that f is affine on each D_{i} (cf. [5]).

In applications, it is not practical to verify that a function is piecewise affine on D by constructing a polyhedral subdivision of D. Scholtes [30] proved that a continuous function f from ℝ^{n} to ℝ^{m} is piecewise affine if and only if there exist affine functions f_{1}, …, f_{r} from ℝ^{n} to ℝ^{m} such that

f(x) ∈ {f_{i}(x) : 1 ≤ i ≤ r} for x ∈ ℝ^{n}.  (1.1)

An analogue characterization holds if we replace ℝ^{n} by a polyhedral subset D of ℝ^{n}. That is, any continuous “patching” of affine functions on D gives a piecewise affine function on D. As a consequence, f is a continuous and piecewise affine function on D if and only if there exist a polyhedral decomposition D_{1}, …, D_{k} of D such that f is continuous on D and affine on each D_{i}. Moreover, a piecewise affine function is Lipschitz continuous.

Set-valued functions which correspond to point-valued affine functions are so-called polyhedral multifunctions. A mapping F : ℝ^{n} → 2^{ℝ^{m}} is a multifunction if it maps each point x in ℝ^{n} to a subset F (x) of ℝ^{m}. Here 2^{ℝ^{m}} denotes the power set of ℝ^{m}, the collection of all subsets of ℝ^{m}. In particular, F (x) might be empty.

A multifunction F : ℝ^{n} → 2^{ℝ^{m}} is said to be Hausdorff continuous on a subset D of ℝ^{n}, if

lim_{y→x,y∈D} H(F (x), F (y)) = 0 for x ∈ D,

where H(S, T) denotes the Hausdorff distance of two subsets S and T of ℝ^{m}:

H(S, T) = max {sup_{x∈S} inf_{y∈T}∥x − y∥, sup_{y∈T} inf_{x∈S} ∥x − y∥} ,

and ∥ · ∥ is the Euclidean 2-norm on ℝ^{m}. Here we assume H(S, ∅) = H(∅, T) = 0.

A multifunction F : ℝ^{n} → 2^{ℝ^{m}} is called a polyhedral multifunction if its graph {(x, y) : x ∈ ℝ^{n}, y ∈ F (x)} is a polyhedral subset of ℝ^{n} × ℝ^{m}. In particular, for each x ∈ ℝ^{n}, the image F (x) is either empty or polyhedral. A polyhedral multifunction F is Lipschitz continuous on its domain D := {x : F (x) ≠ ∅} [33] (cf. also [16]), i.e., there exists a positive constant λ (depending on F) such that

H(F (x), F (y)) ≤ λ · ||x − y|| for x, y ∈ D.

See [24] and [22] for explicit estimates of λ. Note, it is an immediate consequence of the definition of polyhedral multifunctions that its domain is a polyhedral subset of ℝ^{n}. Similar to piecewise affine functions, we define piecewise polyhedral multifunctions in terms of polyhedral multifunctions. A multifunction F : ℝ^{n} → 2^{ℝ^{m}} is called piecewise polyhedral if its domain D := {x : F (x) ≠ ∅} has a finite polyhedral subdivision {D_{1}, …, D_{k}} and F is a polyhedral multifunction on each D_{i}. If the domain D of a piecewise polyhedral multifunction F is a polyhedral set, then F is Lipschitz continuous on D (cf. the remark following Lemma 3.5).

One special class of piecewise polyhedral multifunctions is the collection of metric projections in (ℝ^{n}, ∥ · ∥_{P}), where ∥ · ∥_{P} denotes a polyhedral norm. Recall that a norm ∥ · ∥_{P} on ℝ^{n} is called polyhedral if the corresponding unit ball {x ∈ ℝ^{n} : ∥x∥_{P} ≤ 1} is polyhedral. A norm ∥ · ∥_{P} on ℝ^{n} is polyhedral if and only if there exist vectors E_{1}, …, E_{r} in ℝ^{n} such that

∥x∥_{P} = max_{1≤i≤r} ⟨E_{i}, x⟩ for x ∈ ℝ^{n}.  (1.2)

The metric projection from (ℝ^{n}, ∥·∥_{P}) to a polyhedral subset K in ℝ^{n} is the multifunction defined by

Π_{K,P} (x) = {y ∈ K : ∥y − x∥_{P} = dist(x, K)} for x ∈ ℝ^{n},

where

dist(x, K) := min_{y∈K} ∥y − x∥_{P}  (1.3)

is the distance of a point x in (ℝ^{n}, ∥ · ∥_{P}) to K. The metric projection Π_{K,P} maps each x in ℝ^{n} to a bounded and nonempty polyhedral subset Π_{K,P} (x) of K. Moreover, it is Lipschitz continuous [21].

Special polyhedral norms on ℝ^{n} are the ℓ_{1}-norm, ∥z∥_{1} := |z_{1}|+⋯+|z_{n}|, and the ℓ_{∞}-norm ∥z∥_{∞} := max{|z_{1}|, …, |z_{n}|}, where z_{i} denotes the i-th component of a vector z in ℝ^{n}. The corresponding metric projections are denoted by Π_{K,1} and Π_{K,∞}, respectively.

Next let us introduce some selections of a multifunction F : D ⊂ ℝ^{n} → 2^{ℝ^{m}}. A selection of a multifunction F is a mapping s : D → ℝ^{m} such that s(x) ∈ F (x) for all x ∈ D. See [2, 4] for surveys on various selections of multifunctions and metric projections. If F is a multifunction such that F (x) is a nonempty closed convex subset of ℝ^{m} for every x in D, then the least norm selection for F, denoted by lns, is defined by

lns(x) := arg min_{y∈F (x)} ∥y∥ = arg min_{y∈F (x)} \frac{1}{2}∥y∥^{2} for x ∈ ℝ^{n}.  (1.4)

Since F (x) is a closed convex subset of ℝ^{n}, there exists a unique solution of the strictly convex quadratic programming problem (1.4). Thus, lns(x) is well-defined.

Another type of selections of F is given by the extremal point selections s of F, which satisfy s(x) ∈ ext F (x) for x ∈ D. In contrast to the least norm selection, there exists a Lipschitz continuous multifunction F such that F has no continuous extremal point selection (cf. Example 3.1). One central result in this paper is the existence of a continuous extremal point selection for a piecewise polyhedral multifunction. Moreover, each continuous extremal point selection of a piecewise polyhedral multifunction is piecewise affine. This leads to piecewise affine and continuous selections, and to linear selections [3]. The later exist only if the metric projection satisfies very strong additional conditions [2, 4].

The paper is organized as follows. Section 2 contains some characterizations of piecewise affine functions. The central result of Section 3 is that the least norm selection of a piecewise polyhedral multifunction F is a piecewise affine selection of F. Section 4 is devoted to the study of continuous extremal point selections of a piecewise polyhedral multifunction F. Any continuous extremal point selection of F is a piecewise affine selection of F. Moreover, for any ȳ ∈ ext F (x̄), there is a continuous extremal point selection s of F such that s(x̄) = ȳ. The main result of Section 5 is that the metric projection Π_{K,P} from (ℝ^{n}, ∥ · ∥_{P}) to a polyhedral subset K of ℝ^{n} is a piecewise polyhedral multifunction, and the corresponding distance function is piecewise affine. In the last section, we apply the results of piecewise affine selections of piecewise polyhedral multifunctions to the metric projection Π_{K,P} and obtain piecewise affine selections thereof. By the characterization of piecewise affine functions, the strict best approximation is a piecewise affine selection of Π_{K,∞}. Moreover, there exists a continuous, piecewise affine, and quasi-linear extremal point selection of Π_{G,1}, where G is a subspace of ℝ^{n}. However, for the general metric projection Π_{K,P}, one cannot expect a continuous, piecewise affine, and quasi-linear extremal point selection for Π_{K,P}. We give a simple counterexample in (ℝ^{3}, ∥ · ∥_{∞}).

To conclude the introduction, we give some matrix and vector notations used in this paper. For a matrix A (or a vector x) A^{T} (or x^{T}) denotes the transpose of A (or x). For an index set J, let A_{J} (or x_{J}) be the submatrix (or subvector) of A (or x) consisting of the i-th rows (or the i-th components) of A where i ∈ J. If J = {i}, we also write A_{i} (or x_{i}) instead of A_{J} (or x_{J}).

2. Piecewise Affine Functions

In this section, we provide and establish several characterizations of piecewise affine functions (cf. Corollary 2.4). As an application, we recover a result of Sun [32] on the structure of differentiable piecewise quadratic functions.

First we prove that for each continuous function f satisfying (2.1) a polyhedral subdivision of D exists such that f is affine on each of these polyhedral subsets of D. Moreover, for given affine functions f_{1}, …, f_{r} the polyhedral subdivision can be chosen independently of the particular function f.

Lemma 2.1. Let D be a polyhedral subset of ℝ^{n} and let f_{1}, …, f_{r} be affine functions from ℝ^{n} to ℝ^{m}. There exists a polyhedral subdivision {D_{1}, …, D_{k}} of D such that any continuous function f from D to ℝ^{m} satisfying

f(x) ∈ {f_{i}(x) : 1 ≤ i ≤ r} for x ∈ D,  (2.1)

is an affine function on each D_{j}, 1 ≤ j ≤ k.

Proof. First, we may assume dim D = n. Otherwise an affine isomorphism T : ℝ^{n} → ℝ^{n} exists such that T (D) ⊂ {x ∈ ℝ^{n} : x_{i} = 0, dim D + 1 ≤ i ≤ n}, and we can reduce the problem to ℝ^{dim D}.

Next we assume f_{i} ≢ f_{j} for 1 ≤ i < j ≤ r. Otherwise we may delete functions until this condition holds true.

Let f_{i,1}(x), …, f_{i,m}(x) be the m components of f_{i}(x). For 1 ≤ i < j ≤ r and 1 ≤ l ≤ m, we divide D into two closed polyhedral subsets:

D_{ijl}^{+} := {x ∈ D : f_{i,l}(x) − f_{j,l}(x) ≥ 0} and D_{ijl}^{−} := {x ∈ D : f_{i,l}(x) − f_{j,l}(x) ≤ 0}.

Note that

f_{i}(x) = f_{j}(x) if and only if x ∈ ⋂_{1≤l≤m}(D_{ijl}^{+} ∩ D_{ijl}^{−}).  (2.2)

Since f_{i} ≢ f_{j}, the set ⋂_{1≤l≤m}(D_{ijl}^{+} ∩ D_{ijl}^{−}) is polyhedral and of dimension less than n. For each sign-mapping σ : {(i, j, l) : 1 ≤ i < j ≤ r, 1 ≤ l ≤ m} → {−1, 1}, the set

D(σ) := ⋂_{1≤i<j≤k,1≤l≤m} D_{ijl}^{σ(i,j,l)}

is either empty or polyhedral. For each x ∈ D, we have x ∈ D(σ) with σ(i, j, l) = 1 if f_{i,l}(x) ≥ f_{j,l}(x) and σ(i, j, l) = −1 otherwise. Thus,

D = ⋃_{σ} D(σ).  (2.3)

Since D is a polyhedral set with nonempty interior, D(σ) is nowhere dense in D whenever dim D(σ) < n. By Baire’s Theorem [18, p. 28] the complement of a countable union of nowhere dense sets is dense. Hence,

cl [D \ ⋃_{dim D(σ)<n} D(σ)] = D.

Thus

D = cl [D \ ⋃_{dim D(σ)<n} D(σ)] ⊂ cl [ ⋃_{dim D(σ)=n} D(σ)] = ⋃_{dim D(σ)=n} D(σ) = D,

where the second equality holds true because all the polyhedral sets D(σ) are closed. So we obtain a decomposition of D:

D = ⋃_{dim D(σ)=n} D(σ).

Without loss of generality, we may assume that all sets D(σ) above are pairwise distinct, since we can delete some redundant subsets D(σ) until the remaining subsets are pairwise distinct. Now let D(σ) and D(σ′) be two distinct polyhedral sets such that dim D(σ) = dim D(σ′) = n. Since they are distinct, there exists a triple (i_{0}, j_{0}, l_{0}) of indices such that D_{i_{0}j_{0}l_{0}}^{σ(i_{0},j_{0},l_{0})} ≠ D_{i_{0}j_{0}l_{0}}^{σ′(i_{0},j_{0},l_{0})}. This implies that σ(i_{0}, j_{0}, l_{0}) = −σ′(i_{0}, j_{0}, l_{0}) and f_{i_{0},l_{0}} ≠ f_{j_{0},l_{0}}. Therefore,

D_{i_{0}j_{0}l_{0}}^{σ(i_{0},j_{0},l_{0})} ∩ D_{i_{0}j_{0}l_{0}}^{σ′(i_{0},j_{0},l_{0})} ⊂ {x ∈ ℝ^{n} : f_{i_{0},l_{0}}(x) = f_{j_{0},l_{0}}(x)},

which is a hyperplane. Therefore,

dim(D(σ) ∩ D(σ′) ≤ dim (D_{i_{0}j_{0}l_{0}}^{σ(i_{0},j_{0},l_{0})} ∩ D_{i_{0}j_{0}l_{0}}^{σ′(i_{0},j_{0},l_{0})}) ≤ n − 1.

Thus, {D(σ) : dim(D(σ)) = n} is a polyhedral subdivision of D.

It remains to show that any continuous function f : D → ℝ^{m} satisfying (2.1) is affine on each D(σ) with dim D(σ) = n. Choose D^{∗} = D(σ) with dim D^{∗} = n, i.e., int D^{∗} ≠ ∅. Next we claim that f_{i}(x) ≠ f_{j}(x) for 1 ≤ i < j ≤ r and x ∈ int D^{∗}. Assume there exists an x^{∗} ∈ int D^{∗} such that f_{i}(x^{∗}) = f_{j}(x^{∗}) for two indices i ≠ j. But by (2.2) and by the construction of the sets D(σ), dim D(σ) = n, the point x^{∗} belongs to the boundary of D^{∗}, which stands in contradiction to x^{∗} ∈ int D^{∗}.

By (2.1) and by the continuity of f there exists exactly one index i^{∗} ∈ {1, …, r} such that f(x) = f_{i^{∗}}(x) for all x ∈ int D^{∗}. Using the continuity of f once more we have f(x) = f_{i^{∗}}(x) for x ∈ D^{∗}. Consequently, f is affine on each D(σ) with dim D(σ) = n.

Note that if f_{1}, …, f_{r} are linear functions (instead of affine functions) and D is a polyhedral cone (instead of a polyhedral set), then each D_{σ} in the above proof is a polyhedral cone. As a consequence, we have the following variation of Lemma 2.1.

Corollary 2.2. Let C be a polyhedral cone in ℝ^{n}, let f : C → ℝ^{m} be a continuous function, and let f_{1}, …, f_{r} be linear functions from ℝ^{n} to ℝ^{m} such that f(x) ∈ {f_{i}(x) : 1 ≤ i ≤ r} for x ∈ C. Then there exist polyhedral cones C_{1}, …, C_{k} such that

(i) C = ⋃_{i=1}^{k} C_{i}; (ii) dim(C_{i} ∩ C_{j}) < dim D for i ≠ j; (iii) dim C_{i} = dim C for each i; (iv) f is a linear function on each C_{i}.

Lemma 2.1 can also be rephrased in terms of continuous selections.

Theorem 2.3. Let F : ℝ^{n} → 2^{ℝ^{m}} be a multifunction such that D := {x : F (x) ≠ ∅} is a polyhedral set and F (x) ⊂ {f_{i}(x) : 1 ≤ i ≤ r} for x ∈ D, where f_{i} : ℝ^{n} → ℝ^{m} are affine functions. Then there exist at most finitely many continuous selections for F on D and each continuous selection of F is a piecewise affine function.

Proof. By Lemma 2.1, there exists a polyhedral subdivision {D_{1}, …, D_{k}} of D such that each continuous function f : D → ℝ^{m} satisfying (2.1) is affine on each D_{j}. As a consequence, each continuous selection of F is piecewise affine.

Let σ be a mapping from {1, …, k} to {1, …, r} and define

f_{σ}(x) := f_{σ(j)}(x) for x ∈ D_{j}, j = 1, …, k.

If f : D → ℝ^{m} is a continuous selection for F, then it is affine on each D_{j}. Since f(x) ∈ {f_{i}(x) : i = 1, …, r}, there is an index i(j) (depending on f) such that f(x) = f_{i(j)}(x) for x ∈ D_{j}. Defining σ(j) := i(j) for j = 1, …, k implies f = f_{σ}. Since there are at most r^{k} different mappings σ, F has at most r^{k} continuous selections.

Finally, we give a list of characterizations of piecewise affine functions.

Corollary 2.4. Let D be a polyhedral subset of ℝ^{n} and let f : D → ℝ^{m} be a continuous function. Then the following statements are equivalent.

(i) f is a piecewise affine function on D. (ii) There exist polyhedral subsets D_{1}, …, D_{k} of D such that D = ⋃_{i=1}^{k} D_{i} and f is an

affine function on each D_{i}. (iii) There exist affine functions f_{1}, …, f_{r} from ℝ^{n} to ℝ^{m} such that f(x) ∈ {f_{i}(x) : 1 ≤

i ≤ r} for x ∈ D. (iv) There exist piecewise affine functions g_{1}, …, g_{r} from ℝ^{n} to ℝ^{m} such that f(x) ∈

{g_{i}(x) : 1 ≤ i ≤ r} for x ∈ D.

(v) There exist polyhedral subsets D_{1}, …, D_{k} of D such that D = ⋃_{i=1}^{k} D_{i} and f is a piecewise affine function on each D_{i}.

Proof. It is obvious that (i) implies (ii). Assume that (ii) holds. Let f_{i} be an affine function such that f = f_{i} on D_{i}. Thus, (iii) holds (with r = k). This proves that (ii) implies (iii). It is trivial to see that (iii) implies (iv). Now we prove that (iv) implies (i). By the definition of piecewise affine functions, for each fixed i, there exist affine functions g_{i,1}, …, g_{i,r_{i}} such that

g_{i}(x) ∈ {g_{i,j}(x) : 1 ≤ j ≤ r_{i}} for x ∈ D.

Thus,

f(x) ∈ {g_{i}(x) : 1 ≤ i ≤ r} ⊂ {g_{i,j}(x) : 1 ≤ j ≤ r_{i}, 1 ≤ i ≤ r} for x ∈ D.

By Lemma 2.1, f is a piecewise affine function on D.

Finally, we prove the equivalence of (i) and (v). Obviously, (i) implies (v). Now assume that (v) holds. By the definition of piecewise affine functions, for each fixed i, f satisfies (iv) for D = D_{i}, and hence for D = ⋃_{i=1}^{k} D_{i}. Thus, (iv) holds. By the implication (iv)⇒(i), f is a piecewise affine function on D.

Related to piecewise affine functions are piecewise quadratic functions. By using (2.1), one can give the following definition of piecewise quadratic functions [31].

Definition 2.5. Let D be a polyhedral subset of ℝ^{n} and g : D → ℝ be a continuous function. We say that g is a piecewise quadratic function on D if there exist quadratic functions g_{1}, …, g_{r} from D to ℝ such that

g(x) ∈ {g_{i}(x) : 1 ≤ i ≤ r} for x ∈ D.  (2.4)

In general, one cannot get a polyhedral subdivision {D_{1}, …, D_{k}} of D such that g is a quadratic function on each D_{i}. However, for continuously differentiable piecewise quadratic functions, there is a polyhedral subdivision {D_{1}, …, D_{k}} of D such that g is a quadratic function on each D_{i} [32]. Here we recover the following theorem by Sun [32] on the structure of differentiable piecewise quadratic functions as an application of Lemma 2.1.

Corollary 2.6. Let D be a polyhedral subset of ℝ^{n} and let g : D → ℝ be a continuously differentiable function on D. Then g is a piecewise quadratic function on D if and only if there exists a polyhedral subdivision D_{1}, …, D_{k} of D such that g is a quadratic function on each D_{i}.

Proof. We assume dim D = n. Let {e_{1}, …, e_{n}} be the canonical basis of ℝ^{n}, i.e., e_{i} is the vector whose i-th component is 1 and other components are zero. Let g_{1}, …, g_{r} be quadratic functions such that (2.4) holds. Fixed x ∈ D. By continuity of g and g_{i}’s, g(x) ≠ g_{i}(x) implies g(x + te_{i}) ≠ g_{i}(x + te_{i}) for t near 0. By (2.4), for t near 0, we have

g(x + te_{i}) ∈ {g_{j}(x + te_{i}) : g_{j}(x) = g(x)} ,

which implies

\frac{g(x + te_{i}) − g(x)}{t} ∈ \{\frac{g_{j}(x + te_{i}) − g_{j}(x)}{t} : g_{j}(x) = g(x)\} .  (2.5)

By differentiability of g and g_{i}’s, letting t → 0 in (2.5), we obtain

\frac{∂g(x)}{∂x_{i}} ∈ \{\frac{∂g_{1}(x)}{∂x_{i}}, …, \frac{∂g_{r}(x)}{∂x_{i}}\} .  (2.6)

Let σ be a mapping from {1, …, n} to {1, …, r} and let f_{σ}(x) be a mapping from ℝ^{n} to ℝ^{n} whose i-th component is ∂g_{σ(i)}(x)/∂x_{i}. By (2.6), for each fixed x and i, there is an index j(i) such that

\frac{∂g(x)}{∂x_{i}} = \frac{∂g_{j(i)}(x)}{∂x_{i}}.

Let σ(i) = j(i) for i = 1, …, n. Then ∇g(x) = f_{σ}(x), where ∇g(x) denotes the gradient

of g at x and f_{σ} is an affine mapping from ℝ^{n} to ℝ^{n} whose i-th component is \frac{∂g_{j(i)}(x)}{∂x_{i}}. Thus,

∇g(x) ∈ ⋃_{σ}{f_{σ}(x)}.

Since ∇g is continuous and f_{σ} are affine, by Lemma 2.1, ∇g is a piecewise affine function. Hence a polyhedral subdivision {D_{1}, …, D_{k}} of D exists such that ∇g is an affine function on each D_{i}. As a consequence, g is a quadratic function on each D_{i}. The converse is trivially true.

3. Extremal Point Selections

3.1. Remarks on Continuous Extremal Point Selections

In this section we study extremal point selections of piecewise polyhedral multifunctions. One reason to do so is that any continuous extremal point selection of F is a piecewise affine function. In studying Lipschitz continuity of polyhedral multifunctions, Walkup and Wets proved Lipschitz continuity of the extremal points of polyhedral multifunctions (even though they did not explicitly state it) [33]. Since ext F (x) is a non-convex and finite point set, there is no general theory about the existence of a continuous selection for ext F. In fact, even a Lipschitz continuous multifunction F : ℝ^{2} → 2^{ℝ^{2}}, where F (x) is a line segment in ℝ^{2} for each x and ext F is Lipschitz continuous on ℝ^{2}, does not need to have a continuous extremal point selection.

However, for a piecewise polyhedral multifunction F with ext F (x) ≠ ∅ for all x, we shall construct a vector which determines for each x a supporting hyperplane for F (x) such that it intersects with F (x) in a unique point s(x) ∈ F (x), and s(x) continuously moves along the graph of F. Therefore, s(x) is an extremal point of F (x) and s is a continuous function of x. This allows us to construct a continuous extremal point selection for a piecewise polyhedral multifunction. That is, we obtain one type of piecewise affine selections of a piecewise polyhedral multifunction F by constructing continuous extremal point selections of F.

Let us start with the counterexample mentioned above.

Example 3.1. Let [x, y] := {θx + (1 − θ)y : 0 ≤ θ ≤ 1} for x, y ∈ ℝ^{2} and let 0 be the origin of ℝ^{2}. We denote the projections to the coordinate axis by

\begin{matrix}P_{1}(x) := (\begin{matrix}x_{1} \\ 0 \end{matrix}) , \\ P_{2}(x) := (\begin{matrix}0 \\ x_{2} \end{matrix}) . \end{matrix}

For x ∈ ℝ^{2}, define

F (x) := \begin{cases}[0, x] & if x ≥ 0 \\ [P_{1}(x), P_{2}(x)] & otherwise. \end{cases}

Then the image F (x) is a line segment in ℝ^{2} for each x in ℝ^{2}, and F and ext F are Lipschitz continuous on ℝ^{2}, but F does not have any continuous extremal point selection.

Proof. If x is on the boundary of the first quadrant, then either P_{1}(x) = 0 or P_{2}(x) = 0. If P_{1}(x) = 0, then P_{2}(x) = x; if P_{2}(x) = 0, then P_{1}(x) = x. Note that

ext F (x) := \begin{cases}\{0, x\} & if x ≥ 0 \\ \{P_{1}(x), P_{2}(x)\} & otherwise. \end{cases}

From this it is not difficult to prove that F and ext F are Lipschitz continuous. We leave the details to interested readers.

However, F does not have any continuous extremal point selection. Assume to the contrary, there is such a selection, say s. Then either s(x) = 0 or s(x) = x for x in the first quadrant. If s(x) = 0 for x in the first quadrant, it follows from the continuity of s that s(x) = P_{1}(x) in the second quadrant, which implies s(x) = P_{1}(x) in the remaining quadrants. By s(x) = 0 in the first quadrant and s(x) = P_{1}(x) in the fourth quadrant, we conclude that s is not continuous. Similarly, we will get a contradiction if s(x) = x in the first quadrant.

Remark 3.2. This example demonstrates that in general continuous extremal point selections do not exist.

One should compare this example with Michael’s selection theorem [25]: if Q is a lower semicontinuous multifunction and Q(x) is a closed convex set for each x, then Q has a continuous selection. The above example shows the importance of convexity of Q(x) in Michael’s selection theorem.

3.2. A Continuous Extremal Point Selection

In this section we study extremal point selections of piecewise polyhedral multifunctions. Let us first state the central result.

Theorem 3.3. Let F : ℝ^{n} → 2^{ℝ^{m}} be a piecewise polyhedral multifunction such that D := {x : F (x) ≠ ∅} is a polyhedral subset of ℝ^{n}. For any x̄ ∈ D and any ȳ ∈ ext F (x), there exists a continuous selection s of ext F on D with s(x̄) = ȳ.

In order to prove this theorem, we study polyhedral multifunctions more closely. Let F : D → 2^{ℝ^{m}} be a polyhedral multifunction, where D ⊂ ℝ^{n} with F (x) ≠ ∅ for x ∈ D. Clearly, the graph of F is a polyhedral subset of ℝ^{n+m}. In particular, there exist matrices A ∈ ℝ^{l×n}, Q ∈ ℝ^{l×m}, and a vector b ∈ ℝ^{l}, such that

graph(F) = {(x, y) : x ∈ D, y ∈ F (x)} = {(x, y) : Ax + Qy ≤ b}.

Consequently, the set D ⊂ ℝ^{n} is the orthogonal projection of graph(F) to ℝ^{n}, and hence D is a polyhedral subset of ℝ^{n}. The representation of graph(F) implies for x ∈ D:

F (x) = {y ∈ ℝ^{m} : Qy ≤ b − Ax};

i.e., the image F (x) is a polyhedral subset of ℝ^{m}.

Similarly, if F : D → 2^{ℝ^{m}}, is a piecewise polyhedral multifunction, where D is a polyhedral subset of ℝ^{n}, by its definition finitely many polyhedral subsets D_{1}, …, D_{r} of D exist such that D = ⋃_{i=1}^{r} D_{i}, and the restriction of F to D_{i} is a polyhedral function, 1 ≤ i ≤ r. In particular, there exist matrices A^{i} ∈ ℝ^{l_{i}×n}, Q^{i} ∈ ℝ^{l_{i}×m}, and vectors b^{i} ∈ ℝ^{l_{i}}, such that for 1 ≤ i ≤ r

graph(F |_{D_{i}}) = {(x, y) : x ∈ D_{i}, y ∈ F (x)} = {(x, y) : A^{i}x + Q^{i}y ≤ b^{i}, x ∈ D_{i}}.

Next we give some characterizations of the existence of extremal points of F (x):

Proposition 3.4. Let F : ℝ^{n} → 2^{ℝ^{m}} be a polyhedral multifunction with polyhedral domain D ⊂ ℝ^{n}. Under the notation given above we have

ext F (x) ≠ ∅ for x ∈ D ⟺ rank Q = m.

If F : ℝ^{n} → 2^{ℝ^{m}} is piecewise polyhedral with domain D, we have

ext F (x) ≠ ∅ for x ∈ D ⟺ rank Q^{i} = m for an index i ∈ {1, …, r}.

Proof. First let F be polyhedral. By Grünbaum [11, p. 162] the extremal points of F (x) are exactly the zero-dimensional faces of F (x) = {y ∈ ℝ^{m} : Qy ≤ b − Ax}, x ∈ D, which are the intersection sets of m of the hyperplanes {y ∈ ℝ^{m} : Q_{i}y = b_{i} − A_{i}x}, 1 ≤ i ≤ l, where the corresponding normal vectors Q_{i} are linearly independent. So we have ext F (x) ≠ ∅ for x ∈ D if and only if rank Q = m.

Now let F be piecewise polyhedral. Using the notation given above, it is sufficient to show that rank Q^{i} = m implies rank Q^{j} = m for all 1 ≤ i, j ≤ r. Assume rank Q^{1} = m. Since D is convex, there exists an index j ∈ {2, …, r} such that D_{1} ∩ D_{j} ≠ ∅, say j = 2 and x^{∗} ∈ D_{1} ∩ D_{2}. It suffices to prove rank Q^{2} = m, because for an arbitrary index j ∈ {2, …, r} by the connectedness of D always a finite sequence j_{1} = 1, j_{2}, …, j_{k} = j of indices in {1, …, r} exists such that D_{j_{s−1}} ∩ D_{j_{s}} ≠ ∅ for l = 2, …, k, and hence rank (Q^{j_{s−1}}) = m implies rank (Q^{j_{s}}) = m, 2 ≤ s ≤ k. Consider

F (x^{∗}) = {y ∈ ℝ^{m} : Q^{1}y ≤ b^{1} − A^{1}x^{∗}} = {y ∈ ℝ^{m} : Q^{2}y ≤ b^{2} − A^{2}x^{∗}}.

By rank Q^{1} = m and the first statement of Proposition 3.4 we have ext F (x^{∗}) ≠ ∅. Consequently, by the same argument, we have rank Q^{2} = m.

The following lemma is due to Walkup and Wets [33].

Lemma 3.5. Let F : ℝ^{n} → 2^{ℝ^{m}} be a polyhedral multifunction and ext F (x) be the set of extreme points of F (x) for x ∈ ℝ^{n}. Then there exists a positive constant λ such that

H(ext F (x), ext F (y)) ≤ λ∥x − y∥ for x, y ∈ ℝ^{n}.

Remark 3.6. Obviously, the statement of Lemma 3.5 holds also true for piecewise polyhedral multifunctions with polyhedral domain D. So the extremal point mapping of any piecewise polyhedral multifunction F : ℝ^{n} → 2^{ℝ^{m}} is Lipschitz continuous on each D_{i} of the polyhedral subdivision of D, and by the convexity of D, on D.

Dealing with extremal points of F (x), x ∈ D, makes sense only if ext F (x) ≠ ∅. So under the notation given above we assume rank Q = rank Q^{i} = m, 1 ≤ i ≤ r.

The representation of F given above shows that the extremal point mapping of F satisfies the conditions of Theorem 2.3. Consequently, each continuous extremal point selection of F behaves quite nicely as shown in the following theorem.

Theorem 3.7. Let F : ℝ^{n} → 2^{ℝ^{m}} be a piecewise polyhedral multifunction with polyhedral domain D ⊂ ℝ^{n}. Then each continuous extremal point selection of F is piecewise affine on D. There are only finitely many continuous extremal point selections of F on D.

Proof. Since the multifunction F is piecewise polyhedral, there exists a subdivision {D_{1}, …, D_{r}} of D such that the graph of F on D_{i} × ℝ^{m} is a polyhedron. The notation given above gives a representation of the multifunction F (x) = {y ∈ ℝ^{m} : Q^{i}y ≤ b^{i} − A^{i}x} for x ∈ D_{i}, 1 ≤ i ≤ r, and a representation of its extremal points:

ext F (x) = {y ∈ ℝ^{m} : there exists J ∈ J_{i} with

Q_{J}^{i}y = (b^{i} − A^{i}x)_{J}, Q^{i}y ≤ b^{i} − A^{i}x}, (3.1) where J_{i} is the collection of index sets J ⊂ {1, …, l_{i}} for which Q_{J}^{i} is an m × m square nonsingular matrix. For each J ∈ J_{i}, define

f_{J}^{i}(x) := [Q_{J}^{i}]^{−1}(b^{i} − A^{i}x)_{J}.

Then f_{J}^{i} is an affine mapping and from (3.1) we obtain

ext F (x) ⊂ {f_{J}^{i}(x) : J ∈ J_{i}, 1 ≤ i ≤ r} for x ∈ D.  (3.2)

By Theorem 2.3, any continuous selection of ext F is piecewise affine on D, and there exist only finitely many continuous selections of ext F on D.

Now we are going to prove Theorem 3.3 in two steps. First we prove the statement for a polyhedral multifunction F:

Theorem 3.8. Let F : ℝ^{n} → 2^{ℝ^{m}} be a polyhedral multifunction with domain D ⊂ ℝ^{n}. For any x̄ ∈ D and any ȳ ∈ ext F (x̄) a continuous selection s : D → ℝ^{m} of F exists such that s(x̄) = ȳ and s(x) ∈ ext F (x) for all x ∈ D.

Proof. Using the notation given above, by ȳ ∈ ext F (x̄), an index set J ⊂ {1, …, l} exists such that J contains m indices, rank Q_{J} = m, and

ȳ = Q_{J}^{−1}(b_{J} − A_{J} x̄).

In particular, rank Q = m. The cone

K(x) := {y ∈ ℝ^{m} : Q_{J}y ≤ b_{J} − A_{J}x}

contains F (x) and has the vertex

v(x) := Q_{J}^{−1}(b_{J} − A_{J}x).

The corresponding normal cone N of K(x) at the point v(x) is given by

N = cone{Q_{i}^{T} : i ∈ J} = {∑_{i∈J} a_{i}Q_{i}^{T} : α_{i} ≥ 0, i ∈ J} ,

i.e., we have

z^{T} (y − v(x)) ≤ 0 for z ∈ N, y ∈ K(x).  (3.3)

Because of rank Q_{J} = m we see that int N ≠ ∅. Now we are going to choose a vector u ∈ int N such that it is not a normal vector of any proper face of K(x) of dimension at least one. In other words, any supporting hyperplane of K(x) with normal vector u will support K(x) in a single point. So we consider the set of index sets M := {M ⊂ {1, …, l} : M contains m − 1 indices}. Since span{Q_{i}^{T} : i ∈ M} is a subspace of dimension at most (m − 1), it has no interior point (i.e., it is nowhere dense). So the finite union ⋃_{M∈M} span{Q_{i}^{T} : i ∈ M} has no interior points [18, Baire’s Theorem, p. 27]. Consequently, a vector u exists with

0 ≠ u ∈ int N \ ⋃_{M∈M} span{Q_{i}^{T} : i ∈ M}.

Let us assume u to be a unit vector, i.e., ||u|| = 1. Note that this vector u does not depend on the particular x ∈ D we fixed. So for each x ∈ D we have

v(x) ∈ H_{u}(x) := {y ∈ ℝ^{m} : u^{T} y = u^{T} v(x)}

and by (3.3)

F (x) ⊂ K(x) ⊂ {y ∈ ℝ^{m} : u^{T} y ≤ u^{T} v(x)}.  (3.4)

Now we define an extremal point selection s on D with s(x̄) = ȳ. By (3.4) we have u^{T} y ≤ u^{T} v(x) for all y ∈ F (x). Because of this and since F (x) is a polyhedral set, α(x) ≥ 0 exists such that

α(x) := max_{y∈F (x)} u^{T} y = max_{Qy≤b−Ax} u^{T} y.  (3.5)

Let S(x) denote the solution set of the above linear programming problem for any fixed x. Then S(x) is not empty. Note that S(x) is the intersection of F (x) and its supporting hyperplane H(x) := {y ∈ ℝ^{m} : u^{T} y = α(x)}. If S(x) is a face of F (x) of dimension at least one, then u is a normal vector of this face, which stands in contrast to the way u was chosen. Thus, S(x) contains only one point s(x). Then it is well-known that the solution set of (3.5) is Lipschitz continuous with respect to the right-hand side perturbations (for example, see [24, 22]). Thus, s(x) must be an extreme point of F (x) and is Lipschitz continuous. From the choice of u, we also have s(x̄) = ȳ.

Remark 3.9. Geometrically speaking, the normal vector u, introduced in the proof, determines the selection s as follows: It is the normal vector of the hyperplane H_{u}(x̄) in the y-space ℝ^{m} and it supports the cone K(x̄) as well as the polyhedron F (x̄) at their joint vertex v(x̄) such that the corresponding set of intersection contains the single point v(x̄). Embedded in ℝ^{n+m}, H_{u}(x) is an (m − 1)-dimensional affine subspace. If we move H_{u}(x̄) parallel to itself along the polyhedral graph of F it intersects F (x) in the single point s(x) for x ∈ D — the way u was chosen makes sure that this set of intersection contains exactly one point.

Remark 3.10. The idea of using a normal vector u for determining a continuous extremal point selection of a polyhedral multifunction F : D → 2^{ℝ^{m}} may also work in a more general situation. The assumption that finitely many normal vectors exist such that for all x ∈ D the set F (x) is given as intersection of certain corresponding halfspaces determined by these normal vectors is not necessary.

It is sufficient to make sure that F is Hausdorff continuous and that a normal vector u exists such that a corresponding hyperplane supports F (x) in a single point for all x ∈ D. For example, if F is Hausdorff continuous and if F (x) is strictly convex for all x ∈ D such a normal vector defines a continuous extremal point selection of F. However, we cannot expect the selection to be piecewise affine if F is not piecewise polyhedral.

Let us now complete the proof of Theorem 3.3. The idea of the second part of the proof is to start with the subpolyhedron D_{i} of D with x̄ ∈ D_{i}, where by Theorem 3.8 an extremal point selection s of F with s(x̄) = ȳ exists, and to extend s successively to neighboring subpolyhedra D_{j} of D via common points x ∈ D_{i} ∩ D_{j}. In order to ensure that s is well-defined on the entire set D, a minor modification of the choice of the determining normal vector u is necessary.

Proof of Theorem 3.3. Using the notation given above, an index i ∈ {1, …, r} exists such that x̄ ∈ D_{i}, say x̄ ∈ D_{1}. By Theorem 3.8 a continuous selection s : D_{1} → ℝ^{m} exists with s(x̄) = ȳ and s(x) ∈ ext F (x) for all x ∈ D_{1}. By the proof of Theorem 3.8 this selection is determined by a normal vector u of F (x̄) at ȳ. In detail, u belongs to the interior of the normal cone N of F (x̄) at ȳ, but not to the nowhere dense set ⋂_{M∈M} span {[Q_{i}^{1}]^{T} : i ∈ M} where M denotes the collection of all subsets of {1, …, l_{1}} which contain m − 1 elements.

The minor modification of the choice of u mentioned above is to substitute the exceptional set given above by a bigger exceptional set which is still a nowhere dense set in ℝ^{m}. In order to do this, define index sets M_{i} := {M ⊂ {1, …, l_{i}} : M contains exactly m − 1 indices}, i = 1, …, r. Again the finite union ⋃_{i=1}^{r} ⋃_{M∈M_{i}} span{[Q_{j}^{i}]^{T} : j ∈ M} is a nowhere dense set of ℝ^{m} (cf. [18, Baire’s Theorem, p. 27]. So a vector u exists with

0 ≠ u ∈ int N \ ⋃_{i=1}^{r} ⋃_{M∈M_{i}} span{[Q_{j}^{i}]^{T} : j ∈ M}.

By an analogue argument used in the proof of Theorem 3.8 u cannot be a normal vector of any face of the polyhedron F (x) = {y ∈ ℝ^{m} : Q^{i}y ≤ b^{i} − A^{i}x}, x ∈ D_{i}, 1 ≤ i ≤ r.

Next we extend s to D and determine so a continuous extremal point selection on D with s(x̄) = ȳ. Since D is convex, an index i ∈ {2, …, r} exists such that D_{1} ∩ D_{i} ≠ ∅, say x^{1} ∈ D_{1} ∩ D_{2}. By x^{1} ∈ D_{1}, s(x^{1}) is an extremal point of F (x^{1}), and by the construction of s on D_{1}, u is a normal vector of F (x^{1}) at s(x^{1}). By x^{1} ∈ D_{2} and by Theorem 3.8, u determines a continuous selection s̃: D_{2} → ℝ^{m} of F with s̃(x) ∈ ext F (x) for all x ∈ D_{2} and s̃(x^{1}) = s(x^{1}).

Since both selections are determined by the same normal vector u, we have s̃(x) = s(x) for all x ∈ D_{1} ∩ D_{2}. In other words, s continuously has been extended to D_{1} ∪ D_{2}, u is a normal vector of F (x) at s(x) and the corresponding supporting hyperplane intersects with F (x) in the single point s(x) for all x ∈ D_{1} ∪ D_{2}. Repeating this process iteratively extends s to the entire set D.

4. Least Norm Selections

It is well-known that for a Hausdorff continuous multifunction F the least norm selection is continuous, cf. [10, Theorem 1].

Lemma 4.1. Let F : ℝ^{n} → 2^{ℝ^{m}} be a Hausdorff continuous multifunction with closed domain D ⊂ ℝ^{n} such that F (x) is a closed convex subset of ℝ^{m} for every x ∈ D. Then the least norm selection for F is continuous on D.

When F is a piecewise polyhedral multifunction, the least norm selection is actually a piecewise affine and Lipschitz continuous function (cf. Theorem 4.4 below). In order to prove this we need the following well-known Karush-Kuhn-Tucker characterization of an optimal solution of a convex minimization problem with linear constraints.

Lemma 4.2 ([29, Corollary 28.3.1]). Let g : ℝ^{n} → ℝ be a convex differentiable function and consider the following convex minimization problem:

inf_{z} g(z) subject to Az ≥ b,  (4.1)

where A is an l × n matrix and b ∈ ℝ^{l}. Then z̄ is a solution of (4.1) if and only if there exist an index set J and w ∈ ℝ^{l} such that

Az̄ ≥ b, ∇g(z̄) = A_{J}^{T} w_{J}, w_{J} ≥ 0, A_{J} z̄ − b_{J} = 0.  (4.2)

Remark 4.3. The index set J is called the active set (of constraints) and w is the Lagrange multiplier corresponding to the inequality constraints Az ≥ b.

Theorem 4.4. Suppose that F : ℝ^{n} → 2^{ℝ^{m}} is a piecewise polyhedral multifunction and its domain D := {x ∈ ℝ^{n} : F (x) ≠ ∅} is polyhedral. Then the least norm selection of F is a piecewise affine (and Lipschitz continuous) function on D.

Proof. First assume that F is a polyhedral multifunction on D. So there exist an l × m matrix A, an l × n matrix Q, and a vector b in ℝ^{l} such that

F (x) = {y ∈ ℝ^{m} : Ay ≥ b − Qx} for x ∈ ℝ^{n}.  (4.3)

Note that F (x) = ∅ for x ∉ D. Fix x ∈ D. By the characterization of the least norm solution (cf. Lemma 4.2), we know that there exist an index set J and a vector w ∈ ℝ^{l} such that

lns(x) = A_{J}^{T} w_{J}, A_{J} lns(x) − Q_{J}x − b_{J} = 0,
w_{J} ≥ 0, and A lns(x) − Qx − b ≥ 0.

Equivalently, we have lns(x) = A_{J}^{T} w_{J}, where w_{J} satisfies the following conditions:

w_{J} ≥ 0, AA_{J}^{T} w_{J} − Qx − b ≥ 0, and A_{J}A_{J}^{T} w_{J} − Q_{J}x − b_{J} = 0.  (4.4)

For each index set J, let

D̄_{J} = {(x, z, w_{J}) : x ∈ D, z = A_{J}^{T} w_{J} and (4.4) holds},
D_{J} = {x ∈ D : there exists w_{J} such that (4.4) holds}.

By its definition and (4.4), D̄_{J} is a polyhedral set. Since D_{J} is the linear projection of D̄_{J} onto ℝ^{n}, D_{J} is also a polyhedral set. Moreover, (4.4) is a characterization of the least norm solution lns(x) and, for any x in D, there exist J and w_{J} such that (4.4) holds. Therefore,

D = ⋃_{J} D_{J}.

For J ∈ J and x ∈ D_{J}, define

F_{J}(x) := {z ∈ ℝ^{m} : there exists w_{J} such that (x, z, w_{J}) ∈ D̄_{J}}.

Note that the graph of F_{J} has the following form:

graph(F_{J}) = {(x, z) : x ∈ D_{J} and there exists w_{J} such that (x, z, w_{J}) ∈ D̄_{J}}.

So it is the linear projection of the polyhedral set D̄_{J} onto ℝ^{n} × ℝ^{m} and, in particular, it is a polyhedral set. Thus, F_{J} is a polyhedral multifunction on D_{J}. Moreover, by the characterization (4.4) for lns(x) = A_{J}^{T} w_{J}, we obtain

F_{J}(x) = {lns(x)} for x ∈ D_{J}.

Since F_{J}(x) is a singleton, we have F_{J}(x) = ext F_{J}(x). Since lns is continuous (cf. Lemma 4.1) and lns(x) ∈ F_{J}(x) = ext F_{J}(x), lns(x) is a continuous extremal point selection for the polyhedral multifunction F_{J} on D_{J}. By Theorem 3.7, lns is a piecewise affine function on D_{J}.

Now assume that F is a piecewise polyhedral multifunction. Let D_{1}, …, D_{k} be polyhedral subsets of D such that D = ⋃_{i=1}^{k} D_{i} and F is a polyhedral multifunction on each D_{i}. By the previous proof, lns is a piecewise affine function on each D_{i}. By Corollary 2.4, lns is a piecewise affine function on D.

5. Metric Projections in Polyhedral Spaces

For a linear programming problem with inequality constraints Ax ≥ b, the optimal function value is actually a piecewise affine and convex function of b as shown by Guddat, Hollatz, and Nozicka [15].

Lemma 5.1 ([15, Theorem 6.7]). Let A be an n × m matrix and c ∈ ℝ^{m}. Define

φ(b) := min_{Ay≥b} ⟨c, y⟩

and

C := {b ∈ ℝ^{n} : there exists a vector ȳ such that Aȳ ≥ b and φ(b) > −∞} ≠ ∅.

Then there exist finitely many polyhedral cones C_{1}, ⋯, C_{k} such that

(i) C = ⋃_{i=1}^{k} C_{i}; (ii) int(C_{i}) ∩ int(C_{j}) = ∅ for i ≠ j; (iii) int(C_{i}) ≠ ∅ for each i; (iv) φ is a linear function on each C_{i}.

The reader might also prove this lemma using Corollary 2.2.

Theorem 5.2. Let K be a polyhedral subset of ℝ^{n} and ∥·∥_{P} be a polyhedral norm on ℝ^{n}. Then the distance function dist(·, K) defined in (1.3) is a piecewise affine function.

Proof. Let K = {y ∈ ℝ^{n} : Ay ≥ b}, where A is an m × n matrix and b ∈ ℝ^{m}. By (1.2), we can rewrite (1.3) as

dist(x, K) = min_{β,y} β subject to Ay ≥ b, and
⟨E_{i}, x − y⟩ ≤ β for i = 1, …, r,

i.e.,

dist(x, K) = min_{β,y} β subject to Ay ≥ b, and
⟨E_{i}, y⟩ + β ≥ ⟨E_{i}, x⟩ for i = 1, …, r.

(5.1)

By Lemma 5.1, there is a piecewise affine function φ such that

dist(x, K) = φ(b, ⟨E_{1}, x⟩ , …, ⟨E_{r}, x⟩) for x ∈ ℝ^{n}.

Thus, dist(x, K) is a piecewise affine function of x in ℝ^{n}.

Using the piecewise affine behavior of the distance function dist(·, K), it is easy to prove that the corresponding metric projection Π_{K,P} is a piecewise polyhedral multifunction.

Theorem 5.3. Let K be a polyhedral subset of ℝ^{n} and ∥·∥_{P} be a polyhedral norm on ℝ^{n}. Then the metric projection Π_{K,P} is a piecewise polyhedral multifunction.

Proof. Let K = {y ∈ ℝ^{n} : Ay ≥ b}, where A is an m × n matrix and b ∈ ℝ^{m}. Then, by (1.2), we have

Π_{K,P} (x) = {z : Az ≥ b, ∥x − z∥_{P} ≤ dist(x, K)}
= {z : Az ≥ b, ⟨E_{i}, x − z⟩ ≤ dist(x, K) for 1 ≤ i ≤ r}.

By Theorem 5.2, the distance function dist(x, K) is piecewise affine. Hence there exist finitely many polyhedral subsets D_{1}, …, D_{k} such that ℝ^{n} = ⋃_{j=1}^{k} D_{j} and the restriction of the distance function to each D_{j} is affine, i.e., there exist u^{j} ∈ ℝ^{n} and β_{j} ∈ ℝ such that

dist(x, K) = ⟨u^{j}, x⟩ + β_{j} for x ∈ D_{j}, 1 ≤ j ≤ k.

Consequently, for x ∈ D_{j}, we have

Π_{K,P} (x) = {z : Az ≤ b, ⟨E_{i}, x − z⟩ ≤ ⟨u^{j}, x⟩ + β_{j}, 1 ≤ i ≤ r}
= {z : Az ≤ b, ⟨E_{i}, z⟩ ≥ ⟨E_{i} − u^{j}, x⟩ − β_{j}, 1 ≤ i ≤ r}.

That is, Π_{K,P} is a polyhedral multifunction on each D_{j}. Since Π_{K,P} is Lipschitz continuous [21], Π_{K,P} is a piecewise polyhedral multifunction.

6. Piecewise Affine Selections for Metric Projections

6.1. Least Norm Selections for Metric Projections

In this section we study least norm selections of the metric projection Π_{K,P} from (ℝ^{n}, ∥·∥_{P}) to a polyhedral subset K of ℝ^{n}. Recall

lns(x) = arg min_{y∈Π_{K,P} (x)} \frac{1}{2}∥y∥^{2} for x ∈ ℝ^{n}.

It is easy to see that 0 = lns(x) for all x ∈ ℝ^{n} with 0 ∈ Π_{K,P} (x). Nürnberger [26] calls a selection which selects the origin whenever possible, a selection with null-property (Nulleigenschaft). He introduced this notion when he characterized lower semi-continuity of upper semi-continuous metric projections to certain subspaces of a general normed space. In particular, he proved the existence of a continuous selection with Nulleigenschaft of the metric projection to a linear subspace of ℝ^{n} endowed with an arbitrary norm. Lemma 4.1 extends this statement to the metric projection Π_{G} : ℝ^{n} → 2^{G}, where G is a closed subset of ℝ^{n} such that Π_{G} is Hausdorff continuous and Π_{G}(x) is convex for all x ∈ ℝ^{n}.

In particular, if we restrict ourselves to the polyhedral case, by Lemma 4.1 and Theorem 4.4, we can obtain a piecewise affine selection of Π_{K,P} by using the least norm selection of Π_{K,P}.

Theorem 6.1. Let K be a polyhedral subset of ℝ^{n} and ∥ · ∥_{P} a polyhedral norm on ℝ^{n}. Then the least norm selection of Π_{K,P} is piecewise affine, hence it is Lipschitz continuous.

The least norm selection lns(x) is either 0 (when 0 ∈ Π_{K,P} (x)) or a point on the relative boundary of Π_{K,P} (x) (when 0 ∉ Π_{K,P} (x)). In general, lns(x) is not necessarily an extremal point of Π_{K,P} (x), and it is different from any extremal point selection of Π_{K,P}.

Remark 6.2. Let K be a polyhedral subset of ℝ^{n} and ∥ · ∥_{P} be a polyhedral norm on ℝ^{n}. Then there exists a positive constant ϵ such that the least norm selection of Π_{K,P} is the unique solution of the following quadratic programming problem:

min_{y∈K} (∥x − y∥_{P} + \frac{ϵ}{2}∥y∥^{2}) for x ∈ ℝ^{n}.  (6.1)

This follows from Mangasarian’s characterization of the least norm solution of a linear program [23]: the least norm solution of the linear programming problem

min_{y∈C} c^{T} y

is the solution of the following quadratic programming problem

min_{y∈C} (c^{T} y + \frac{ϵ}{2}∥y∥^{2}) ,

where C is a polyhedral set and ϵ > 0 is a small positive constant. By (1.2), for each fixed x, Π_{K,P} (x) is the set of vectors y^{∗} which solve the following linear programming problem:

min τ subject to y ∈ K, ⟨E_{i}, x − y⟩ ≤ τ for i = 1, …, r.

Therefore, by Mangasarian’s characterization, the least norm selection of Π_{K,P} is the vector y^{∗} that solves the following quadratic programming problem:

min (τ + \frac{ϵ}{2}∥y∥^{2}) subject to y ∈ K, ⟨E_{i}, x − y⟩ ≤ τ for i = 1, …, r,

which is an equivalent form of (6.1).

6.2. Extremal Point Selections for Metric Projections

In this section we investigate continuous extremal point selections for the metric projection Π_{K,P}. By Theorem 5.3, Π_{K,P} is a piecewise polyhedral multifunction. Since Π_{K,P} (x) is bounded, we have ext Π_{K,P} (x) ≠ ∅ for all x in ℝ^{n}. By Theorems 3.3 and 3.7, Π_{K,P} always has a continuous extremal point selection, which is a piecewise affine selection.

Theorem 6.3. Let K be a polyhedral subset of ℝ^{n} and let ∥ · ∥_{P} be a polyhedral norm on ℝ^{n}.

(i) For any x̄ ∈ ℝ^{n} and any ȳ ∈ ext Π_{K,P} (x̄), there is a continuous extremal point selection s of the metric projection Π_{K,P} on ℝ^{n} with s(x̄) = ȳ.

(ii) Any continuous extremal point selection for Π_{K,P} is a piecewise affine (and Lipschitz

continuous) selection. (iii) There are only finitely many continuous extremal point selections of Π_{K,P}.

Proof. By Theorem 5.3, Π_{K,P} is a piecewise polyhedral multifunction on ℝ^{n}. Since Π_{K,P} (x) is a bounded polyhedral set in ℝ^{n}, ext Π_{K,P} (x) ≠ ∅ for all x ∈ ℝ^{n}. Thus, the statements in Theorem 6.3 follow from Theorems 3.3 and 3.7.

6.3. Quasi-linear Selections for Metric Projections

A multifunction F : ℝ^{n} → 2^{ℝ^{m}} is homogeneous, if

F (αx) = αF (x) for all x ∈ ℝ^{n}, α ∈ ℝ.

For a linear subspace G of ℝ^{n}, the multifunction F is quasi-additive with respect to G, if

F (x + z) = F (x) + F (z) for all x ∈ ℝ^{n}, z ∈ G.

We call F quasi-linear with respect to G, if F is homogeneous and quasi-additive with respect to G. A mapping s : ℝ^{n} → ℝ^{m} is called a quasi-linear selection of F with respect to G if s(x) ∈ F (x) for x ∈ ℝ^{n} and if s is a quasi-linear mapping with respect to G.

Two decades ago Nürnberger [26] proved the existence of a quasi-linear selection of a quasi-linear multifunction F under some mild assumption on F.

Lemma 6.4. Suppose that F (x) is a closed convex subset of ℝ^{m} for every x ∈ ℝ^{n} and F is a quasi-linear multifunction with respect to a subspace G of ℝ^{n} such that G is a set of fix-points of F (i.e., F (z) = {z} for z ∈ G). Then F has a quasi-linear selection with respect to G.

For a linear subspace G of ℝ^{n}, the metric projection Π_{G} from ℝ^{n} (endowed with any norm) to G is quasi-linear with respect to G. Since Π_{K,P} (z) = z for all z ∈ G, Nürnberger obtained the following as a corollary to Lemma 6.4.

Corollary 6.5. The metric projection Π_{G} onto a linear subspace G of ℝ^{n} endowed with any norm has a quasi-linear selection.

For a metric projection Π_{G,P} from (ℝ^{n}, ∥·∥_{P}) to a linear subspace of G of ℝ^{n}, by Theorem 6.3, we know that Π_{G,P} has a continuous and piecewise affine extremal point selection; and by Corollary 6.5, we know that Π_{G,P} has a quasi-linear selection. Is it possible to construct a continuous, piecewise affine, and quasi-linear extremal point selection for Π_{G,P}? The next example shows that the answer is negative.

Example 6.6. Consider the linear subspace

G = \{θ ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) : θ ∈ ℝ\} ⊂ ℝ^{3}

and ∥ · ∥_{P} = ∥ · ∥_{∞}. Then Π_{G,∞} does not have a quasi-linear and continuous extremal point selection.

Proof. Note that dist(x, G) = max{|x_{2}|, |x_{3}|}. Consider the subset

D := \{x ∈ ℝ^{3} : x = ( \begin{matrix}0 \\ x_{2} \\ x_{3} \end{matrix} ) , ∥x∥_{∞} = 1\},

which is the boundary of the unit square in the hyperplane {x ∈ ℝ^{3} : x_{1} = 0}, and is orthogonal to G. All points x in D have the same set of best approximants in G:

Π_{G,∞}(x) = \{θu : −1 ≤ θ ≤ 1\}, where u := ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) .

There are two choices of extremal point selections for Π_{G,∞} on D: u and −u. Let s be a continuous extremal point selection for Π_{G,∞}. By the continuity of s, there exists a constant ϵ = ±1 such that s(x) = ϵu for x ∈ D. Let v ∈ D. Then −v ∈ D. But

s(−v) = ϵu ≠ −ϵu = −s(v).

Hence s is not quasi-linear, since the homogeneity is not satisfied.

However, when G is a linear subspace of ℝ^{n} and ∥ · ∥_{P} = ∥ · ∥_{1}, Finzel [8] constructed a piecewise affine and quasi-linear extremal point selection of Π_{G,1} by using a perturbation analysis.

6.4. Strict Best Approximation

The strict best approximation was introduced by Rice [28] as a selection for the metric projection onto a linear subspace of (ℝ^{n}, ∥ · ∥_{∞}) which chooses the so-called best element among the best approximants. This idea can easily be extended to selections for the metric projection to closed convex subsets of (ℝ^{n}, ∥ · ∥_{∞}). Two years ago, Huotari and Li [17] gave another characterization of the strict best approximation in terms of monotone rearrangement and lexicographic order of vectors. They proved that the strict best approximation of x in K, denoted by sba_{K}(x), is a continuous function of x if Π_{K,∞} is Hausdorff continuous [17]. In this case, the strict best approximation sba_{K}(x) is actually the limit of best ℓ_{p}-approximations Π_{K,p}(x) as p → ∞:

sba_{K}(x) = lim_{p→∞} Π_{K,p}(x) for x ∈ ℝ^{n},  (6.2)

where Π_{K,p}(x) is the unique element in K such that

∥x − Π_{K,p}(x)∥_{p} = min_{z∈K} ∥x − z∥_{p}  (6.3)

and ∥z∥_{p} = (|z_{1}|^{p} + … + |z_{n}|^{p})^{\frac{1}{p}}. Note that Π_{K,P} is Lipschitz continuous [21] when K is a polyhedral set. As a consequence, sba_{K}(x) can also be defined by (6.2) if K is a polyhedral set. Recently, Finzel and Li [9] proved that sba_{K} is Lipschitz continuous when K is a polyhedral set. In this subsection, we prove that sba_{K} is piecewise affine, which implies the Lipschitz continuity of sba_{K}, extending the following result proved by Finzel [7].

Lemma 6.7. Let G be a subspace of ℝ^{n}. Then the strict best approximation sba_{G} is a piecewise affine function.

Our approach is to represent sba_{K} in terms of sba_{G_{i}}, where G_{i} denote those finitely many affine subspaces in ℝ^{n} which are the affine hulls of the faces of K. For this purpose, we need the following lemma on the structure of Π_{K,p}(x) [9].

M. Finzel, W. Li / Piecewise affine selections for piecewise polyhedral multifunctions 93

Lemma 6.8. Let K be a polyhedral subset of ℝ^{n}. Then there exist vectors z^{1}, …, z^{r} in ℝ^{n} and subspaces G_{1}, …, G_{r} of ℝ^{n} such that

\begin{matrix}Π_{K,p}(x) ∈ \{z^{1} + Π_{G_{1},p}(x − z^{1}), …, z^{r} + Π_{G_{r},p}(x − z^{r})\} \\ for x ∈ ℝ^{n}, 1 < p < ∞. \end{matrix}  (6.4)

Theorem 6.9. If K is a polyhedral subset of ℝ^{n}, then the strict best approximation sba_{K} is a piecewise affine selection for Π_{K,∞}.

Proof. By Lemma 6.8, there exist vectors z^{1}, …, z^{r} in ℝ^{n} and subspaces G_{1}, …, G_{r} of ℝ^{n} such that (6.4) holds. Since (6.2) holds for any polyhedral set, letting p → ∞ in (6.4) we obtain

sba_{K}(x) ∈ {z^{1} + sba_{G_{1}}(x − z^{1}), …, z^{r} + sba_{G_{r}}(x − z^{r})} for x ∈ ℝ^{n}.  (6.5)

By Lemma 6.7, for each i, g_{i}(x) := z^{i} + sba_{G_{i}}(x − z^{i}) is a piecewise affine function. By Corollary 2.2, the strict best approximation sba_{K} is a piecewise affine function.

References

[1] M. Chen, E. Kuh: Solving piecewise linear equations for resistive networks, Circuit Theory Appl. 3 (1976) 3–24.

[2] F. Deutsch: A survey of metric selections, in: Fixed Points and Nonexpansive Mappings, ed. by R. C. Sine, Contemporary Mathematics 18 (1983) 49–71.

[3] F. Deutsch: Linear selections for the metric projection, J. Funct. Anal. 49 (1982) 269–292.

[4] F. Deutsch: A survey of metric selections, in: Approximation Theory, Spline Functions and Applications, ed. by S. P. Singh, Kluwer Academic Publishers (1992) 123–137.

[5] B. Eaves, U. Rothblum: Relationships of properties of piecewise affine maps over ordered fields, Linear Alg. Appl. 55 (1990) 1–63.

[6] B. Eaves, H. Scarf: The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976) 1–27.

[7] M. Finzel: Linear approximation in ℓ_{n}^{∞}, J. Approx. Theory 76 (1994) 326–350.

[8] M. Finzel: Best linear approximation in l_{1}(n), East J. Approx. 2 (1996) 1–30.

[9] M. Finzel, W. Li: Uniform Lipschitz continuity of best l_{p}-approximations by polyhedral sets, J. Math. Anal. Appl. 228 (1998) 112–118.

[10] F. S. Garnir-Monjoie: Selections continues de multifonctions, Bull. Soc. Roy. Sci. Liege 46 (1977) 51–56.

[11] B. Grünbaum: Convex Polytopes, Interscience Publishers, London, 1967.

[12] M. Gowda: An analysis of zero set and global error bound properties of a piecewise affine function via its recession function, SIAM J. Matrix Anal. Appl. 17 (1996) 594–609.

[13] M. Gowda, M. Sznajder: Nondegeneracy concepts for zeros of piecewise smooth functions, Math. Oper. Res. 23 (1998) 221–238.

[14] M. Gowda, M. Sznajder: On the pseudo-Lipschitzian behavior of the inverse of a piecewise affine function, Math. Programming 74, Ser. A (1996) 267–278.

[15] J. Guddat, H. Hollatz, F. Nozicka: Theorie der linearen parametrischen Optimierung, Akademie-Verlag, Berlin, 1994.

94 M. Finzel, W. Li / Piecewise affine selections for piecewise polyhedral multifunctions

[16] A. J. Hoffman: Approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards 49 (1952) 263–265.

[17] R. Huotari, W. Li: The continuity of metric projection in ℓ_{∞}(n), the Pólya algorithm, the strict best approximation, and tubularity of convex sets, J. Math. Anal. Appl. 182 (1994) 836–856.

[18] G. Köthe: Topological Vector Spaces I, Springer-Verlag, Berlin, 1983.

[19] L. Kuntz, S. Scholtes: Structural analysis of nonsmooth mappings, inverse functions, and metric projections, J. Math. Anal. Appl. 188 (1994) 346–384.

[20] K. Kuratowski: Introduction to Set Theory and Topology, Pergamon Press, New York, 1972.

[21] W. Li: A. J. Hoffman’s theorem and metric projections in polyhedral spaces, J. Approx. Theory 75 (1993) 107–111.

[22] W. Li: The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program, Linear Alg. Appl. 187 (1993) 15–40.

[23] O. L. Mangasarian: Normal solutions of linear programs, Math. Programming Study 22 (1984) 206–216.

[24] O. L. Mangasarian, T. H. Shiau: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM J. Control Optim. 25 (1987) 583–595.

[25] E. Michael: Continuous selections I, Annals of Math. 63 (1956) 361–382.

[26] G. Nürnberger: Schnitte für die metrische Projektion, J. Approx. Theory 20 (1977) 196–219.

[27] T. Ohtsuki, T. Fujisawa, S. Kumagai: Existence theorems and a solution algorithm for piecewise linear resistive networks, SIAM J. Math. Anal. 8 (1977) 69–99.

[28] J. R. Rice: Tchebycheff approximation in a compact metric space, Bull. Amer. Math. Soc. 68 (1962) 405–410.

[29] C. T. Rockafellar: Convex Analysis, Princeton University Press, 1970.

[30] S. Scholtes: Introduction to piecewise differentiable equations, Preprint 53/1994, Institute für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, Germany, May, 1994.

[31] J. Sun: On the structure of piecewise quadratic functions, J. Optim. Theory Appl. 72 (1992) 499–510.

[32] J. Sun: On piecewise quadratic Newton and trust region problems, Math. Programming 76, Ser. B (1997) 451–467.

[33] D. Walkup, R. J-B Wets: A Lipschitzian characterization of convex polyhedra, Proc. Amer. Math. Soc. 23 (1969) 167–173.