Journal of Convex Analysis Volume 2 (1995), No.1/2, 1–17

Consistency of Minimizers and the SLLN for Stochastic Programs^{1}

Zvi Artstein^{2}

Department of Theoretical Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel. e-mail: mtarts@weizmann.weizmann.ac.il

Roger J-B Wets

Department of Mathematics, University of California, Davis, CA 95616, U.S.A. e-mail: rjb@ucdavis.edu

Received 21 June 1994 Revised manuscript received 1 February 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

A general strong law of large numbers for stochastic programs is established. It is shown that solutions and approximate solutions may not be consistent with the strong law in general, but consistency holds locally, or when the decision space is compact. An additional integrability condition implies the uniform consistency of approximate solutions. The results are applied in the context of linear recourse models.

1. Introduction

The paper examines relations between solutions of a stochastic optimization problem, and the solutions of large sampled versions of the problem. We consider an abstract stochastic program of the form

minimize_{x∈X} E^{P (dξ)}(f(x, ξ))  (∗)

where E^{P (dξ)} is the expectation operator with respect to the probability measure P over the space Ξ of random elements. The decision space here is taken as a metric space. For a given sequence ξ_{1}, …, ξ_{n} of realizations of the random variable we form the deterministic problem

minimize_{x∈X} \frac{1}{n}(f(x, ξ_{1}) + ⋯ + f(x, ξ_{n})).  (∗∗)

When the ξ_{i} are drawn according to the distribution P, and independently, a reasoning in line of a strong law of large numbers indicates toward relations between solutions of (∗)

1 Research supported by a grant from the U.S.-Israel Binational Science Foundation. 2 Incumbent of the Hettie H. Heineman Professorial Chair in Mathematics.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

and those of (∗∗) for large n. Such relations, especially the robustness and the statistical consistency, are explored in the sequel. We note that the abstract form (∗) incorporates many concrete stochastic optimization problems, see e.g. Wets [15]; a linear recourse model is analyzed in the closing section. As a preliminary consideration we examine the functions on the space X which determine the minimization problems (∗) and (∗∗), namely

(Ef)(x) = E^{P (dξ)}(f(x, ξ))  (1.1)

(we suppress the superscript P on the operator E when no confusion may arise), and for ξ_{1}, …, ξ_{n} fixed

F (x; ξ_{1}, …, ξ_{n}) = \frac{1}{n} ∑_{j=1}^{n} f(x, ξ_{j}).  (1.2)

Under quite relaxed conditions (e.g. boundedness from below by an integrable function), if the ξ_{j} are independent and P -distributed, the values F (x; ξ_{1}, …, ξ_{n}) converge almost surely to (Ef)(x), for x fixed. This follows from the standard strong law of large numbers, see e.g. Ash [1, Section 7]. But a more general property holds. Under some conditions, the functions F (· ; ξ_{1}, …, ξ_{n}) converge almost surely to the function (Ef)(·), this when the convergence is with respect to the epi-convergence of functions, which can be interpreted as a one-sided version of uniform convergence. Such results are given in King and Wets [9], Attouch and Wets [3], Castaing and Ezzaki [5] and Hess [7]; we elaborate on that in Section 2 where such a strong law of large numbers for functions is verified under somewhat weaker conditions. In the rest of the paper we are interested in the robustness and consistency of optimal solutions and near optimal solutions of (∗). We ask, in particular, whether employing an optimal solution of (∗) for the problem (∗∗) with large n, yields with high probability a good approximate solution of (∗∗). The same question is examined with respect to uniformly small deviations from solutions of (∗). The consistency of optimal solutions is examined in Section 3. We give a counterexample for global consistency; but provide a local consistency result, and establish the global consistency when the decision space is compact. The uniform consistency of approximate solutions is examined in Section 4. Here even local robustness fails, unless the underlying conditions are strengthened. We display such sufficient conditions, and in the closing section demonstrate their applicability in the context of linear recourse models.

2. A Law of Large Numbers

We start by setting the conditions under which we work. We then recall the notion of epi-convergence, and state and prove the corresponding strong law of large numbers. We assume that X is a complete separable metric space. We assume that (Ξ, Σ, P) is a probability space, and that the σ-field Σ is complete with respect to P, namely, a subset of a null set in Σ also belongs to Σ (this assumption is for technical convenience only; standard techniques can be used to eliminate it). Two assumptions are placed on the cost functions f(x, ξ) as follows.

Assumption 2.1. The function

f(x, ξ): X × Ξ → (−∞, ∞]

is measurable on X × Ξ (where on X the Borel field is taken), and f(·, ξ) for ξ fixed is lower semicontinuous in x, namely x_{k} → x_{0} implies lim inf f(x_{k}, ξ) ≥ f(x_{0}, ξ).

Assumption 2.2. For each x_{0} ∈ X there exists an open set N_{0} in X and an integrable function α_{0}(ξ): Ξ → (−∞, ∞) such that x_{0} ∈ N_{0} and for almost all ξ ∈ Ξ the inequality

f(x, ξ) ≥ α_{0}(ξ)  (2.1)

holds for all x ∈ N_{0}. The assumptions are quite relaxed, and are satisfied by the typical stochastic programs. In fact, in quite a number of cases stochastic programs exhibit continuity in the x variable; the semicontinuity allows in turn to model constraints, as we can set f(x, ξ) = ∞ for the nonfeasible cases. We also note that the terminology random lower semicontinuous functions is often used in the literature to describe functions that satisfy Assumption 2.1.

Note that Fatou’s lemma (see e.g. Ash [1, 1.6.8(a)]), implies that (Ef)(x) is lower semicontinuous under Assumptions 2.1 and 2.2. Also, it is clear then that F (x; ξ_{1}, …, ξ_{n}) is lower semicontinuous in the x variable. We recall now the concept of epi-convergence for lower semicontinuous functions. Consult with Attouch [2] and Rockafellar and Wets [12] for a thorough analysis of the concept and its relation with minimization problems. Consider the sequence of lower semicontinuous functions

F_{k}(x): X → (−∞, ∞].

The sequence F_{k}(·) epi-converges to F_{0}(·) if the following two properties hold for every x_{0} ∈ X. (I) lim inf F_{k}(x_{k}) ≥ F_{0}(x_{0}) whenever x_{k} → x_{0}, and (II) lim F_{k}(y_{k}) = F_{0}(x_{0}) for at least one sequence y_{k} → x_{0}. Epi-convergence of lower semicontinuous functions is equivalent (as it is easy to see) to the set convergence of their epigraphs. To this end we introduce the notation

epi h = {(x, r): r ≥ h(x)}  (2.2)

for the epigraph of the function h(·). When h(·) is lower semicontinuous the set epi h is a closed set in X × (−∞, ∞]. Under some conditions on X, e.g. local compactness, epi-convergence is metrizable; we shall not need this property.

We state and prove now a strong law of large numbers with respect to epi-convergence. Such results were initiated in King and Wets [9], where the strong law was verified for convex integrands in a euclidean space. Attouch and Wets [3] have established the law for a separable Banach space, and general lower semicontinuous functions. Here we further relax the conditions, and work within a metric space; our approach though is in line with that of [3], the difference lies only in the way the equi-Lipschitz approximations are taken. Also worth mentioning in this respect are the contributions of Castaing and Ezzaki [5] and Hess [7] (we thank a referee for pointing them out to us). In [5] the authors use the Lipschitz approximations to provide limit laws for martingales and supperadditive sequences. In [7] the result is verified for a general, not necessarily complete, metric space. In turn the minorization condition is somewhat stronger. We note that a particular case of the epi-convergence would be the standard vector-valued slln into the space of continuous functions with the sup norm. But in our case the vector-valued methods seem not to apply. Also note the related observations by Plachky [10].

For convenience we state the results using a sequence ξ_{1}, ξ_{2}, … of independent and identically distributed samplings from Ξ; then almost sure properties refer to the denumerable power of (Ω, Σ, P). An easy reduction would cover the case of a sequence f_{j}(x, ξ) of i.i.d. cost functions.

Theorem 2.3. Let ξ_{1}, ξ_{2}, … be a sequence of independent and identically P -distributed drawings from Ξ. Under Assumptions 2.1 and 2.2, the sequence F (· ; ξ_{1}, …, ξ_{n}) almost surely epi-converges to (Ef)(·).

Proof. We first prove that almost surely property (I) of epi-convergence holds. Consider a fixed open set N_{0} in X, on which Assumption 2.2 holds. We verify first that almost surely property (I) holds for the restriction of F (· ; ξ_{1}, …, ξ_{n}) and of (Ef)(·) to N_{0}. One possibility is that on a set of ξ of positive measure the function f(x, ξ) = ∞ identically. Then the result is trivial, as (Ef)(x) = ∞ for x ∈ N_{0}, and clearly almost surely F (x; ξ_{1}, …, ξ_{n}) = ∞ for n large. Hence we proceed under the assumption that almost surely f(x, ξ) < ∞ for some x ∈ N_{0}. We claim that a sequence g_{k}(x, ξ) exists, of functions

g_{k}(x, ξ): N_{0} × Ξ → (−∞, ∞]

satisfying the following properties

(i) Each g_{k} is measurable on N_{0} × Ξ. (ii) Each g_{k} is a Lipschitz function of the variable x, with Lipschitz constant independent

of the variable ξ. (iii) g_{k}(x, ξ) ≥ α_{0}(ξ), and g_{k}(x, ξ) converges monotonically to f(x, ξ) as k → ∞. In order to provide the sequence g_{k} we employ the very useful construction of G. Beer [4]. Define first

g_{0}(x, ξ) = α_{0}(ξ).  (2.3)

Suppose that g_{k}(x, ξ) is given. Define

φ_{k}(x, ξ) = inf{d(x, y) + |g_{k}(x, ξ) − r|: y ∈ N_{0}, r ≥ f(y, ξ)}  (2.4)

where d(·, ·) is the metric on X; namely, φ_{k}(x, y) is the distance (of an L_{1} nature) of (x, g_{k}(x, ξ)) from the epigraph of f(·, ξ) restricted to N_{0}. Since f(·, ξ) is not identically +∞, the function φ_{k}(x, ξ) is finite. Define

g_{k+1}(x, ξ) = g_{k}(x, ξ) + φ_{k}(x, ξ).  (2.5)

We verify now the three desired properties. The measurability of g_{k+1}(x, ξ) follows, by induction, from that of φ_{k}(x, ξ). To establish the measurability of the latter, consider the set-valued map epi f(·, ξ), namely a map from Ξ to the closed subsets of N_{0} × (−∞, ∞]. By Lemma VII-1 of Castaing and Valadier [6, page 196], this set-valued function has a measurable graph. Further, by the Castaing Representation, see Rockafellar [11, Thm. 1B] or Castaing and Valadier [6, Section 2], a sequence s_{k}(ξ): Ξ → N_{0}×(−∞, ∞] of measurable point-valued functions exists, such that

epi f(·, ξ) = closure of {s_{1}(ξ), s_{2}(ξ), …}  (2.6)

(here epi f(·, ξ) is the epigraph of the function f(x, ξ) for ξ fixed). Each s_{j}(ξ) is of the form (x_{j}(ξ), r_{j}(ξ)). Since for an arbitrary fixed c

{(x, ξ): φ_{k}(x, ξ) < c} = ⋃_{j=1}^{∞}{(x, ξ): d(x, x_{j}(ξ)) + |g_{k}(x, ξ) − r_{j}(ξ)| < c}

and since x_{j}(·), g_{k}(·, ·), r_{j}(·) are measurable, it indeed follows that φ_{k}(·, ·) is measurable. This verifies property (i). Property (ii) follows directly from the construction. Indeed, g_{0}(x, ξ) is constant in x, namely has a Lipschitz constant 0. Suppose that L is a Lipschitz constant for g_{k}(·, ξ). From the definition of φ_{k}(x, ξ) in (2.4) it follows that it is Lipschitz with constant L + 1; hence by (2.4) the value 2L + 1 is a Lipschitz constant for g_{k+1}(·, ξ) for ξ fixed. Simple recursion shows then that 2^{k} − 1 is a Lipschitz constant for g_{k}(·, ξ), and property (ii) is proved. Property (iii) is clear, and as was mentioned, it was observed by Beer [4]. This completes the proof of the claim. With the aid of the sequence g_{k}(x, ξ) we can verify Property (I) on N_{0} as follows. For x and k fixed, define

G_{k}(x; ξ_{1}, …, ξ_{n}) = \frac{1}{n} ∑_{j=1}^{n} g_{k}(x, ξ_{j})  (2.7)

since g_{k}(x, ξ) ≥ α_{0}(ξ). The standard strong law of large numbers implies that for x fixed, almost surely G_{k}(x; ξ_{1}, …, ξ_{n}) converge to

(Eg_{k})(x) = E^{P (dξ)}(g_{k}(x, ξ)).  (2.8)

Let x_{i}, i = 1, 2, … be a dense sequence in N_{0}. By the countability, almost surely G_{k}(x_{i}; ξ_{1}, …, ξ_{n}) converge as n → ∞ to (Eg_{k})(x_{i}) for all i = 1, 2, …, say that this holds for the collection Θ_{k} of sequences. The Lipschitz property in (ii) implies that for (ξ_{1}, ξ_{2}, …) in Θ_{k} the convergence of G_{k}(x; ξ_{1}, …, ξ_{n}) to (Eg_{k})(x) holds for all x ∈ N_{0}. Finally, on the intersection of Θ_{k} for k = 0, 1, …, we have that G_{k}(x; ξ_{1}, …, ξ_{n}) converge as n → ∞ to (Eg_{k})(x) for all x ∈ N_{0} and all k. And note that the intersection, which we denote by Θ, has a full measure. We are ready to prove that Property (I) holds for every F (· ; ξ_{1}, …, ξ_{n}) with (ξ_{1}, ξ_{2}, …) in Θ, namely almost surely. Let x_{0} ∈ N_{0} be arbitrary. Suppose first that (Ef)(x_{0}) < ∞. The monotonic convergence property (iii) implies that for k large the value (Eg_{k})(x_{0}) is close to (Ef)(x_{0}), say

(Ef)(x_{0}) − (Eg_{k})(x_{0}) < ϵ.

Since for a fixed k, the Lipschitz constant of g_{k}(·, ξ) is shared by all the ξ (it is 2^{k} − 1), it follows that (Eg_{k})(·) is also Lipschitz, and the same is true for each G_{k}(·, ξ_{1}, …, ξ_{n}). For sequences in Θ, the values G_{k}(· ; ξ_{1}, …, ξ_{n}) converge to (Eg_{k})(·), and since

F (x; ξ_{1}, …, ξ_{n}) ≥ G_{k}(x; ξ_{1}, …, ξ_{n})

always, it follows that whenever x_{n} → x_{0}

lim inf F (x_{n}; ξ_{1}, …, ξ_{n}) ≥ (Ef)(x_{0}) − ϵ  (2.9)

for all sequences in Θ. Since ϵ is arbitrarily small it follows that (2.9) holds also with ϵ = 0. This concludes the proof for (Ef)(x_{0}) < ∞. The case (Ef)(x_{0}) = ∞ is similar. The only modification is to replace the phrase ϵ arbitrarily small by (Eg_{k})(x_{0}) arbitrarily large. We leave out the details. So far we verified that almost surely Property (I) holds for x ∈ N_{0}. Since X is assumed separable, a countable number of such neighborhoods N_{0} cover X, this by Assumption 2.2. Therefore on a set of full measure, namely the intersection of the sequence of the corresponding Θ, the inequality (2.9) holds with ϵ = 0 for all x_{0} ∈ X and sequences x_{n} → x_{0}. This concludes the first part of the proof.

We now verify that almost surely Property (II) of epi-convergence holds. We consider the epigraph

epi(Ef)(·)  (2.10)

which is a set in X × (−∞, ∞] (by Assumption 2.2), and a dense sequence (x_{i}, r_{i}) in it. Note that r_{i} = ∞ is allowed. The lower semicontinuity of (Ef)(·) implies in particular that the sequence (x_{i}, (Ef)(x_{i})) is then dense in the lower boundary of the epigraph (2.10). Namely, for each x_{0} ∈ X, a subsequence of (x_{i}, (Ef)(x_{i})) converges to (x_{0}, (Ef)(x_{0})). We apply now the standard strong law of large numbers for each x_{i} separately. The countability implies that on a set Θ of sequences (ξ_{1}, ξ_{2}, …) of full measure, F (x_{i}; ξ_{1}, …, ξ_{n}) converge to (Ef)(x_{i}) as n → ∞, for each i = 1, 2, …. Clearly, for each element in Θ, if x_{0} is given, a subsequence, say y_{n}, of x_{i} can be deduced (related to the aforementioned subsequence of x_{i}), such that

lim F (y_{n}; ξ_{1}, …, ξ_{n}) = (Ef)(x_{0}).  (2.11)

This verifies Property (II) of epi-convergence on Θ, that is almost surely. This concludes the proof.

3. Robustness and Consistency of Minimizers

The epi-convergence almost surely of F (· ; ξ_{1}, …, ξ_{n}) to (Ef)(·) implies a number of properties for the convergence of the minimizers and of the infima. For instance, the set of approximate solutions of (∗∗) almost surely converges topologically to the corresponding set of approximate solutions of (∗). See Rockafellar and Wets [12] for an elaborate discussion. Here we go beyond such statements and examine robust properties of solutions and approximate solutions.

We define first the notion of asymptotic minimizers, and discuss its relation to the robustness and consistency. We show then that for a general decision space, a minimizer of (∗) may not be robust with respect to independent samples. We establish consistency for a compact X, and provide a local consistency result for a general space.

A point x_{0} is an ϵ-minimizer of H(·) if

H(x_{0}) − min_{x∈X} H(x) ≤ ϵ.  (3.1)

A point x_{0} is an asymptotic ϵ-minimizer of the sequence H_{k}(·) if

lim sup_{k→∞}(H_{k}(x_{0}) − min_{x∈X} H_{k}(x)) ≤ ϵ.  (3.2)

A 0-minimizer is called a minimizer, and likewise for an asymptotic 0-minimizer. If H_{k}(·) converges in some sense to H_{0}(·), it it natural to inquire whether a minimizer of H_{0}(·) is an asymptotic minimizer of the sequence H_{k}(·). This is the robustness of the minimizer with respect to the convergence. We note that minimizers are not, in general, robust with respect to the epi-convergence of lower semicontinuous functions. For instance, for x scalar let H_{0}(x) = 1 if x < 0 and H_{0}(x) = x if x ≥ 0. Let H_{k}(x) = H_{0}(x − k^{−1}). Then H_{k}(·) epi-converge to H_{0}(·), yet the minimizer x^{∗} = 0 of H_{0}(·) is not an asymptotic minimizer of H_{k}(·). The situation may be different in the framework of the almost sure convergence given in Theorem 2.3, as the strong law can be applied to f(x^{∗}, ·) with x^{∗} being the solution of (∗). Asymptotic minimization is then called consistency, in line with the terminology in statistical estimates. We find, however, that the consistency of the minimizer of (∗) may fail in general.

Example 3.1. Let Ξ = [0, 1] with the Lebesgue measure. Let X = {0, 1, 2, …} with the line distance. We define

f(0, ξ) = 0.  (3.3)

We proceed successively. In the jth step (j ≥ 2) we define f(k, ξ) for ({j^{2} \atop j}) numbers, say for the numbers

m = k(j) + 1, …, k(j) + ({j^{2} \atop j}).  (3.4)

This is done as follows. We divide Ξ into j^{2} intervals of equal length. To each group of j

such intervals we associate a different number from (3.4), and hence the ({j^{2} \atop j}) numbers in the sequence. Denote the union of the j intervals associated with the number m by I_{j,m}. Define

f(m, ξ) = \{ \begin{matrix}−1 & if ξ ∈ I_{j,m} \\ 2 & otherwise. \end{matrix}  (3.5)

This for m = k(j) + 1, …, k(j) + ({j^{2} \atop j}).

The cost function f satisfies, of course, all the assumptions. The expectation is easily computed as

(Ef)(m) = (2j^{2} − 3j)j^{−2} if k(j) + 1 ≤ m ≤ k(j) + ({j^{2} \atop j}).  (3.6)

Therefore x^{∗} = 0 is the unique minimizer of (Ef)(·), with (Ef)(0) = 0, and (Ef)(m) ≥ 1 for m > 0. But, for every sample (ξ_{1}, …, ξ_{j}) there is at least one natural number m with

F (m; ξ_{1}, …, ξ_{j}) = −1.  (3.7)

Indeed, such an m can be found among the numbers in (3.4). This completes the example.

The situation is different when the decision space is compact. We show it following a standard, yet useful, lemma.

Lemma 3.2. If X is compact, then

min_{x∈X} H(x)

is continuous with respect to epi-convergence.

Proof. A stronger result is provided in Attouch [2, Theorem 2.11].

Theorem 3.3. Suppose that X is compact. Let x^{∗} be a minimizer (an ϵ-minimizer) of (Ef)(·). Then almost surely x^{∗} is an asymptotic minimizer (respectively an asymptotic ϵ-minimizer) of F (· ; ξ_{1}, …, ξ_{n}).

Proof. The standard strong law of large numbers when applied to f(x^{∗}, ·) with x^{∗} fixed, implies that on a set Θ_{1} of sequences (ξ_{1}, ξ_{2}, …), of full measure the following limit holds

lim_{n→∞} F (x^{∗}; ξ_{1}, …, ξ_{n}) = (Ef)(x^{∗}).  (3.10)

The slln of Theorem 2.3 together with Lemma 3.2 imply that on a set Θ_{2} of sequences, of full measure, the following limit occurs

lim_{n→∞}(min_{x∈X} F (x; ξ_{1}, …, ξ_{n})) = min_{x∈X}(Ef)(x).  (3.11)

The two limits imply directly the desired asymptotic minimization properties on the intersection of Θ_{1} and Θ_{2} which is also of full measure.

Here is an alternative formulation of the preceding result. The probability on the nproduct Ξ × Ξ × ⋯ × Ξ is the product probability.

Proposition 3.4. Suppose that X is compact. Let x^{∗} be an ϵ-minimizer of (Ef)(·). Then for every η > 0,

Prob{F (x^{∗}; ξ_{1}, …, ξ_{n}) − (min_{x∈X} F (x; ξ_{1}, …, ξ_{n}) + ϵ) ≥ η}  (3.12)

tends to 0 as n → ∞; for x^{∗} being a minimizer the same estimate holds with ϵ = 0.

Proof. Follows from Theorem 3.3 in a standard way.

A formulation similar to that of (3.12) holds locally near a minimizer of (Ef)(·), even in the noncompact case, as follows.

Proposition 3.5. Let x^{∗} be an ϵ-minimizer of (Ef)(·). For every η > 0 there are δ > 0 and n_{0} such that

Prob{min_{x∈X}(Ef)(x) − ( min_{x∈N_{δ}(x^{∗})} F (x; ξ_{1}, …, ξ_{n}) + ϵ) ≥ η} < η  (3.13)

for all n ≥ n_{0}, where N_{δ}(x^{∗}) denotes the δ-neighborhood of x^{∗} in X. For x^{∗} a minimizer the same estimate holds with ϵ = 0.

Proof. On a set Θ_{1} of full measure of sequences (ξ_{1}, ξ_{2}, …) we have

F (x^{∗}; ξ_{1}, …, ξ_{n}) → (Ef)(x^{∗}).  (3.14)

The slln in Theorem 2.3 implies that on a set Θ_{2} of full measure

lim inf F (x_{n}; ξ_{1}, …, ξ_{n}) ≥ (Ef)(x^{∗})  (3.15)

whenever x_{n} → x^{∗}. In particular, for each fixed sequence in Θ_{2}, a number δ > 0 exists and n_{0} such that

F (x; ξ_{1}, …, ξ_{n}) − F (x^{∗}; ξ_{1}, …, ξ_{n}) ≤ η  (3.16)

if n ≥ n_{0} and x ∈ N_{δ}(x^{∗}). A simple exhaustion argument would show that (3.16) holds with arbitrary large probability for δ small and n_{0} high enough. Together with (3.14) and noting that x^{∗} is an ϵ-minimizer the proof is complete.

4. Uniform Consistency of Approximations

The consistency in Theorem 3.3 applies for a fixed minimizer, or for a fixed approximate minimizer. In this section we inquire about the uniform consistency of approximations. For instance, we ask if with high probability an arbitrary approximate solution of (∗) yields an approximate solution of (∗∗) for large n. We find that this uniformity is false even locally for X compact, unless further conditions are imposed.

Example 4.1. Let X = \{0, 1, \frac{1}{2}, \frac{1}{3}, …\} with the metric of the line. Let Ξ = [0, 1] with the Lebesgue measure. We construct an integrand g(x, ξ) by modifying Example 3.1 as follows. At x = 0 we use the same value, namely

g(0, ξ) = 0.  (4.1)

For x = \frac{1}{m} we define

g(\frac{1}{m}, ξ) = \{ \begin{matrix}0 & if f(m, ξ) = 2 \\ 1 & if f(m, ξ) = −1 \end{matrix}  (4.2)

with f as defined in Example 3.1. The underlying assumptions hold, including the lower semicontinuity at x = 0. It is easy to see that

(Eg)(\frac{1}{m}) = \frac{1}{j} if k(j) + 1 ≤ m ≤ k(j) + ({j^{2} \atop j})  (4.3)

10 Z. Artstein, R. J-B. Wets / Consistency of Minimizers

with k(j) given in Example 3.1. Since (Eg)(0) = 0 it follows that (Eg)(·) is continuous at its minimizer x^{∗} = 0. For each sample (ξ_{1}, …, ξ_{n}), however, there are points \frac{1}{m} ∈ X arbitrarily close to 0, with F (\frac{1}{m}; ξ_{1}, …, ξ_{n}) = 1. This shows that with probability one an arbitrary approximate solution for (∗) may fail to provide an approximate solution of (∗∗).

Remark 4.2. Note that the approximation in the preceding example breaks down in one direction, namely for an ϵ-minimizer x of (∗) it may occur that F (x; ξ_{1}, …, ξ_{n})−(Ef)(x^{∗}) is large. The smallness of (Ef)(x^{∗}) − F (x; ξ_{1}, …, ξ_{n}) is guaranteed in the compact case by Theorem 3.3, and for local perturbations by Proposition 3.5.

An appropriate continuity condition would be sufficient for the desired uniform consistency. Indeed, notice that the integrand in Example 4.1 oscillates rapidly near the minimizer x^{∗} = 0. We set first some terminology.

We consider the problem (∗) and denote by X^{∗} the ensemble of minimizers of (Ef)(·), namely the solutions of (∗). Note that under Assumptions 2.1 and 2.2 the function (Ef)(·) is lower semicontinuous, hence X^{∗} is closed.

Let Y be a subset of X. We say that Y is a manifold of approximations with respect to X^{∗} if y_{k} ∈ Y and y_{k} → x^{∗} with x^{∗} ∈ X^{∗}, imply that (Ef)(y_{k}) converge to (Ef)(x^{∗}). Namely on Y ∪ X^{∗} the function (Ef)(·) is continuous at X^{∗}.

A manifold of approximations may not contain a full neighborhood of X^{∗}; in fact, in realistic problems it may occur that only perturbations from the minimizers in prescribed directions yield good approximations. The following result refers to a manifold of approximations (which may yet be part of a larger manifold) which enjoys additional properties. What we in fact show is that under the additional properties the approximations in this manifold are statistically consistent.

Theorem 4.3. Let Y be a manifold of approximations. Suppose that Y is compact and that the following conditions hold.

(a) y_{k} ∈ Y, y_{k} → x^{∗} and x^{∗} ∈ X^{∗} then f(y_{k}, ξ) → f(x^{∗}, ξ) for almost every ξ;

(b) for each x^{∗} ∈ Y ∩ X^{∗} a neighborhood N_{0} of x^{∗} exists, and an integrable function β(ξ) such that |f(y, ξ)| ≤ β(ξ) for all y ∈ N_{0} ∩ Y.

Then for every ϵ > 0 there exists a δ > 0 such that on a set Θ of sequences (ξ_{1}, ξ_{2}, …) of full measure,

lim sup_{n→∞}(max_{y∈Y_{δ}} F (y; ξ_{1}, …, ξ_{n}) − min_{x∈X} F (x; ξ_{1}, …, ξ_{n})) ≤ ϵ  (4.4)

when Y_{δ} is the set of δ-minimizers of (Ef)(·) in Y.

Proof. The statement allows for Y ∩ X^{∗} to be empty, but then the claim holds trivially. We therefore assume that there are elements in Y which are minimizers of (Ef)(·) on X. We denote Y^{∗} = Y ∩ X^{∗}. The lower semicontinuity of (Ef)(·) and the compactness imply that if y_{k} is a sequence with (Ef)(y_{k}) converging to min(Ef)(·), then y_{k} must converge to Y^{∗}. Therefore we can replace the statement “Y_{δ} is the set of δ-minimizers of (Ef)(·)” by the statement “Y_{δ} is in the closed δ-neighborhood of Y^{∗} in Y ”.

Consider now the upper closure of f(y, ξ) with respect to Y, namely the function

h(y, ξ) = lim sup_{z∈Y,z→y} f(z, ξ).

Then h(y, ξ) is upper semicontinuous in the y variable on Y. We claim that h(y, ξ) is measurable. To prove the claim let s_{k}(ξ) = (y_{k}(ξ), r_{k}(ξ)) be a sequence of measurable functions from Ξ into Y × (−∞, ∞], such that

epi f(·, ξ) = closure {s_{1}(ξ), s_{2}(ξ), …}

for all ξ. Such a sequence exists by the Castaing Representation, see Rockafellar [11] or the arguments leading to (2.6). The lower semicontinuity of f(y, ξ) in y implies that

(y_{k}(ξ), f(y_{k}(ξ), ξ))

is almost surely dense in the graph of f(·, ξ). Therefore h(y, ξ) can also be defined as

h(y, ξ) = lim sup_{y_{i}(ξ)→y} f(y_{k}(ξ), ξ)

with y_{i}(ξ) an arbitrary subsequence of y_{k}(ξ). The measurability of y_{k}(·), and hence of f(y_{k}(·), ·), yields then the measurability of h(y, ξ) in a routine way as follows. For every c ∈ (−∞, ∞) the inverse set h^{−1}(−∞, c) can be expressed as follows

\begin{matrix}\{(y, ξ): h(y, ξ) < c\} = \\ ⋃_{δ>0} ⋂_{ϵ>0} ⋃_{k=1}^{∞}\{(y, ξ): d(y, y_{k}(ξ)) < ϵ\} ∩ \{(y, ξ): f(y, ξ) < c − δ\} \end{matrix}  (4.5)

with d(·, ·) the metric on Y. The union over δ > 0 and the intersection over ϵ > 0 can be replaced by denumerable operations with δ_{i} → 0 and ϵ_{i} → 0. Then clearly the right hand side of (4.5) is a measurable set, and hence h^{−1}(−∞, c) is measurable, which implies the measurability of h. We note, however, that the continuity assumption (a) implies that h(y^{∗}, ξ) = f(y^{∗}, ξ) for y^{∗} ∈ Y^{∗}, and furthermore (a) holds when h(y, ξ) replaces f(y, ξ). The integrability assumptions (b) and Assumption 2.2 imply that (Eh)(y) is continuous at each y^{∗} ∈ Y^{∗}. Therefore, for every ϵ > 0 there exists a δ > 0 such that

|(Eh)(y) − (Ef)(y^{∗})| ≤ ϵ  (4.6)

when d(y, y^{∗}) ≤ δ for some y^{∗} ∈ Y^{∗}. We apply now Theorem 3.3 with a decision space being Y_{δ}, and with the upper semicontinuous integrand h(y, ξ); namely, we apply the result for the upper semicontinuous case, with maximizers replacing minimizers. The inequality (4.6) implies that y^{∗} in Y^{∗} is an ϵ-maximizer on Y_{δ}. By Theorem 3.3, on a set Θ of sequences (ξ_{1}, ξ_{2}, …), with full measure, the decision y^{∗} is an asymptotic ϵ-maximizer for

H(y; ξ_{1}, …, ξ_{n}) = \frac{1}{n} ∑_{j=1}^{n} h(y, ξ_{j})

on Y_{δ}. Since F (y; ξ_{1}, …, ξ_{n}) ≤ H(y; ξ_{1}, …, ξ_{n}) it follows that y^{∗} is then also an asymptotic ϵ-maximizer on Y_{δ}. Namely,

lim inf(F (y^{∗}; ξ_{1}, …, ξ_{n}) − max_{δ∈Y_{δ}} F (y; ξ_{1}, …, ξ_{n})) ≥ −ϵ

which in a form closer to (4.4) can be written as

lim sup(max_{y∈Y_{δ}} F (y; ξ_{1}, …, ξ_{n}) − F (y^{∗}; ξ_{1}, …, ξ_{n})) ≤ ϵ.  (4.7)

The previous inequality together with the convergence almost surely of F (y^{∗}; ξ_{1}, …, ξ_{n}) to (Ef)(y^{∗}), verifies (4.4) almost surely.

An alternative formulation of the uniform consistency of approximations is as follows.

Proposition 4.4. Under the conditions of Theorem 4.3, for every ϵ > 0 there exists a δ > 0, such that for every η > 0

Prob{max_{y∈Y_{δ}} F (y; ξ_{1}, …, ξ_{n}) − min_{x∈X} F (x; ξ_{1}, …, ξ_{n}) ≥ ϵ + η} < η  (4.8)

for n large enough, with Y_{δ} the set of δ-minimizers of (Ef)(·).

Proof. Follows from (4.4) using standard arguments.

We note that indeed in Example 4.1, the probability in equation (4.8) is equal to 1 whenever ϵ + η < 1. Note also that the integrability condition (b) in the statement of Theorem 4.3 cannot be dropped, even if the continuity in (a) prevails. Indeed, the values f(y, ξ) may be made large for y close to y^{∗} on subsets of Ξ with small measure, along the construction of Example 4.1, such that (4.8) is violated. Finally note that conditions (a) and (b) in Theorem 4.3 actually imply that Y is a manifold of approximations, so stating this fact explicitly as an assumption could be dropped.

5. Linear Recourse

The results of the preceding sections are illustrated here in the context of the two stage linear recourse model. For an overview of the theory and applications of such models consult with Wets [14], [15], and Kall [8].

Consider the problem

minimize ⟨c, x⟩ + E^{P (dξ)}(Q(x, ξ))
subject to Ax = b, x ≥ 0

(5.1)

where x ∈ IR^{k}, the k dimensional euclidean space, A, c and b are a fixed matrix and vectors (and ⟨·, ·⟩ denotes scalar multiplication), and P is a probability distribution over a space Ξ of random elements, as in previous sections. The cost Q(x, ξ) is determined via a recourse procedure, and given by

Q(x, ξ) = inf_{z}{⟨q(ξ), z⟩: W (ξ)z = d(ξ) + T (ξ)x, z ≥ 0}  (5.2)

with z ∈ IR^{ℓ} and q, W, d and T are random matrices and vectors with the appropriate dimensions; in particular q(·), W (·), d(·) and T (·) are measurable. In terms of the problem formulation in (∗) we have

f(x, ξ) = \begin{cases}⟨c, x⟩ + Q(x, ξ) & if Ax = b, x ≥ 0 \\ ∞ & otherwise. \end{cases}  (5.3)

Note that f(x, ξ) may equal +∞ even if the constraints on x are met; this happens when the recourse is not feasible, i.e., for no z ≥ 0 the equality W (ξ)z = d(ξ)+T (ξ)z is satisfied. Also note that the formulation (5.3) may not fit the general framework of this paper as Q(x, ξ) may be equal to −∞. This happens when the recourse decision is degenerate. We refer the reader to Wets [14] and references therein, and to Kall [8] for conditions that guarantee that Q(x, ξ) > ∞ for almost every ξ. Here, for concreteness, we impose a condition which implies this property, as follows. We use M^{T} to denote the transpose of the matrix M.

Assumption 5.1. (Integrable dual feasibility) There exists a vector u such that c ≥ A^{T} u. There exists a measurable function v(ξ) such that q(ξ) ≥ W^{T} (ξ)v(ξ) and such that ⟨d(ξ), v(ξ)⟩ and T^{T} (ξ)v(ξ) are both integrable.

Remark 5.2. The role of the integrable dual feasilibility conditions will be apparent in the proof of the following proposition. We note here that most practical examples satisfy this condition (see [14], [15], [8] and references therein). For instance, if c ≥ 0 and q(ξ) ≥ 0 for almost every ξ then the integrable dual feasibility holds with u = 0 and v(ξ) = 0.

Proposition 5.3. Under Assumption 5.1 the linear recourse problem (5.1)–(5.2) satisfies Assumptions 2.1 and 2.2.

Proof. The lower semicontinuity of f(x, ξ) in x follows from the more general result of Wets [14, Proposition 7.5]; note that for ξ fixed the lower semicontinuity of Q(x, ξ) can be verified by checking that min{⟨q, z⟩: W z = s, z ≥ 0} is lower semicontinuous in s, for q and W fixed. The lower semicontinuity of f(x, ξ) in x follows then from the closedness of the constraints Ax = b, x ≥ 0.

To prove the joint measurability of f(x, ξ) consider first a set-valued map, say Γ_{1}, which assigns to the data (x, W, d, T) the set {z: W z = d + T x} if Ax = b and x ≥ 0, and the empty set otherwise. The set-valued map Γ_{1} may have empty values, but it certainly has a closed graph, hence Γ_{1} is measurable but moreover, the inverse Γ_{1}^{−}(C) of a compact set C is a closed set (see e.g. Castaing and Valadier [6] for the definitions). Define now

Γ(x, ξ) = Γ_{1}(x, W (ξ), d(ξ), T (ξ)).

By the measurability of the data in (5.2) the set-valued map Γ is measurable jointly in (x, ξ), this since the inverse Γ^{−}(C) of a compact set is the inverse of the closed set Γ_{1}^{−}(C) by the function (x, W (ξ), d(ξ), T (ξ)) which is assumed to be measurable. Finally note that

f(x, ξ) = min{⟨q(ξ), z⟩: z ∈ Γ(x, ξ)}

which implies (say by using the Castaing Representation) the measurability of f(x, ξ) jointly in (x, ξ) in case the underlying σ-field is complete (see [6, Chapter III]), a property that we assume throughout. The remaining properties needed to complete the proof are that f(x, ξ) > −∞ and that the integral bound in Assumption 2.2 holds. For this we employ Assumption 5.1. Indeed, ⟨c, x⟩ ≥ ⟨A^{T} u, x⟩, hence by the equality Ax = b we get ⟨c, x⟩ ≥ ⟨u, b⟩, which gives a uniform lower bound on the cost of the primary decision. The recourse decision can be estimated as follows

⟨q(ξ), z⟩ ≥ ⟨W^{T} (ξ), z⟩
= ⟨v(ξ), W (ξ)z⟩
= ⟨v(ξ), d(ξ) − T^{T} (ξ)x⟩.

The integrability requirement in Assumption 5.1 implies that Q(x, ξ) > −∞, and furthermore, there is an integral bound as required in Assumption 2.2, locally in x.

With the preceding proposition, the strong law of large numbers verified in Theorem 2.3 applies. An immediate consequence is that if x^{n} = x^{n}(ξ_{1}, …, ξ_{n}) is a solution of

minimize  ⟨c, x⟩ + \frac{1}{n} ∑_{j=1}^{n}⟨q(ξ_{j}), z_{j}⟩
subject to  Ax = b
T (ξ_{j})x + W (ξ_{j})z_{j} = d(ξ_{j}) j = 1, …, n
x ≥ 0
z_{j} ≥ 0 j = 1, …, n

(5.4)

then almost surely any cluster point of x^{n} is a solution of the stochastic problem (5.1). Note that (5.4) is a large scale linear program, depending on a stochastic parameter.

We turn now to check the consistency of minimizers and ϵ-minimizers (that could as well be computed, with large probability, using (5.4) with a large enough sample). We note that the underlying conditions of Theorem 3.3 and Propositions 3.4 and 3.5 are satisfied. Hence consistency of minimizers and ϵ-minimizers is guaranteed with respect to decisions in any compact subset of IR^{k}. Next we wish to analyze the uniform consistency of approximations for the linear recourse, in line with the approach in Section 4. To this end define

D = {x: E^{P (dξ)}(f(x, ξ)) < ∞}  (5.5)

namely D is the effective domain of the cost function. Note that

D = {x: E^{P (dξ)}(Q(x, ξ)) < ∞} ∩ {x: Ax = b, x ≥ 0}.  (5.6)

The domain D may not be compact, and even its intersection with compact subsets of IR^{k} may not be compact; this was noted in Walkup and Wets [13] and will be also demonstrated in an example below. The following observation is of help.

Proposition 5.4. Let K be a compact polyhedral subset of D. Then there exists an integrable function β(ξ): Ξ → [0, ∞), such that for all x ∈ K, the bound f(x, ξ) ≤ β(ξ) holds almost everywhere.

Proof. The compact polyhedral set K is a convex combination of a finite number of points, say x_{1}, …, x_{r}. Let z_{j}(ξ) be an optimal recourse decision for the point x_{j}, namely W (ξ)z_{j}(ξ) = d(ξ) + T (ξ)x_{j}, and ⟨q(ξ), z_{j}(ξ)⟩ = Q(x_{j}, ξ). Such a recourse exists and is measurable by the completeness of the σ-field, see Kall [8]. The linearity of the constraints implies that the convex combination

α_{1}z_{1}(ξ) + ⋯ + α_{r}z_{r}(ξ)

is an admissible recourse decision for the primal decision

α_{1}x_{1} + ⋯ + α_{r}x_{r}.

Since the latter combinations exhaust K, it follows that β_{1}(ξ) = max{⟨q(ξ), z_{j}(ξ)⟩: j = 1, …, r} is an integrable bound of Q(x, ξ) for x ∈ K, and therefore β(ξ) = β_{1}(ξ) + max{⟨c, x⟩: x ∈ K} is the desired integrable bound.

We note that the preceding argument also proves that any polyhedral subset K of D is a manifold of approximations for the recourse problem, as defined in Section 4. This property also follows from the fact, proved in Wets [14], that E^{P (dξ)}(Q(x, ξ)) is continuous on polyhedral subsets of D. With the preceding arguments we can conclude that the uniform consistency of approximations to solutions of the stochastic linear recourse, holds whenever the approximations are restricted to a set contained in a polyhedral subset of D. Indeed, Proposition 5.4 implies that condition (b) of Theorem 4.3 holds, and as noted before, any polyhedral subset of D is a manifold of approximations. It is worthwile to note that under additional conditions the entire domain D is polyhedral. For instance, if P is supported on a finite set; or when W is fixed and the data (q(·), d(·), T (·)) have a finite variance and form a polyhedral set in the linaer space of (q, d, T), see [14, Theorem 4.7]; or if W and T are fixed and (q(·), d(·)) are square integrable, see [14, Theorem 4.10]. In general, D is a convex set which may not be closed, and E^{P (dξ)}(f(x, ξ)) may not be continuous on D, as noted in Walkup and Wets [13]. We provide here an example which demonstrates the phenomenon, and illustrates the preceding considerations.

Example 5.5. Let the primary decision x = (x_{1}, x_{2}) be two dimensional, and let the recourse decision z = (z_{1}, z_{2}, z_{3}) be three dimensional. The random element ξ takes values in [1, ∞), with an underlying probability that will be determined later. Let the recourse cost be given by

Q(x, ξ) = min{z_{1}: z_{1} + z_{2} = ξ^{2}x_{1}, z_{2} + z_{3} = (ξ^{2} − ξ)x_{2}, z ≥ 0}  (5.7)

and suppose that the goal is to minimize the expected value of the recourse, with x ≥ 0 (namely c = b = A = 0). It is easy to see that the optimal decision, regardless of the probability, is x = 0, and then Q(0, ξ) = 0 identically. For a general x, it is clear that

Q(x, ξ) = max(0, ξ^{2}x_{1} − (ξ^{2} − ξ)x_{2}).  (5.8)

Consider now the particular probability P on [1, ∞) that assigns the value 2^{−k} to the point ξ = 2^{k}, this for k = 1, 2, …, (note that then the data in (5.7) does not have finite variance). With this probability it is easy to see that

D = {(x_{1}, x_{2}): 0 ≤ x_{1} < x_{2}} ∪ {(0, 0)}.  (5.9)

Indeed, for x_{1} ≥ x_{2} > 0 we have Q(x, ξ) = ξ^{2}(x_{1} − x_{2}) + ξx_{2} and the expectation is +∞. If x_{1} < x_{2} then for ξ > x_{2}(x_{2} − x_{1})^{−1} we have Q(x, ξ) = 0, hence the expectation is finite.

The lower semicontinuity of the expected cost E^{P (dξ)}(Q(x, ξ)) implies then that as decisions x^{j} ∈ IR^{2} converge to x^{0} = (x_{1}, x_{1}) and x_{1} > 0, then E^{P (dξ)}(Q(x^{j}, ξ)) converge to +∞. This implies that not every compact subset of D that includes (0, 0) is a manifold of approximations. Indeed, on points x^{j} that converge to 0, but get closer and closer to the diagonal x_{1} = x_{2} in IR^{2}, the value may converge to +∞ as j → ∞. (In the concrete example (5.7) it is not difficult to compute the expectation, and come up with such a sequence. In fact, on the cone in IR_{+}^{2} determined by the relation (1 − 2^{−ℓ})x_{2} ≤ x_{1} ≤ (1 − 2^{−(ℓ+1)})x_{2} the value can be obtained by a finite summation of 2^{−k}Q(x, 2^{k}) over k = 1, …, 2^{ℓ}, resulting in

E^{P (dξ)}(Q(x, ξ)) = (x_{1} − x_{2})(2^{ℓ+1} − 2) + ℓx_{2}.

Hence if the sequence x^{j} = (x_{1,j}, x_{2,j}) is determined by x_{2,j} = j^{−1/2}, x_{1,j} = (1 − 2^{−j})x_{2,j}, the expectations tend to +∞ as x^{j} → 0.)

A conclusion of the theory, however, is that on any polyhedral subset of (5.9), in particular on a set {(x_{1}, x_{2}): 0 ≤ x_{1} ≤ (1 − δ)x_{2} ≤ Δ}, with δ > 0, the consistency of the minimizer x = 0, and the uniform consistency of approximations of x = 0, hold.

References

[1] R.B. Ash: Real Analysis and Probability. Academic Press, New York, 1972.

[2] H. Attouch: Variational Convergence of Functions and Operators. Pitman, London, 1984.

[3] H. Attouch, R.J-B Wets: Epigraphical processes: laws of large numbers for lsc functions. To appear.

[4] G. Beer: A geometric algorithm for approximating semicontinuous functions. J. Approximation Theory 49 (1987), 31–40.

[5] C. Castaing, F. Ezzaki: Variational inequalities for integrands martingales and additive random sequences. Seminaire d’Analyse Convexe Montpellier 22 (1992), n^{o} 1.

[6] C. Castaing, M. Valadier: Convex Analysis and Measurable Multifunctions. Lecture Notes in Mathematics 580, Springer-Verlag, Berlin, 1977.

[7] C. Hess: Epi-convergence of sequences of normal integrands and strong consistency of the maximum likelihood estimator. In: XXIV^{es} Journées de Statistique, Bruxelles (18–22 May, 1992), pp. 254–256; also Cahiers de Mathématiques de la Decision n^{o} 9121, Université Paris Dauphine (1991).

[8] P. Kall: Stochastic Linear Programming. Springer-Verlag, Berlin, 1976.

[9] A. King, R.J-B Wets: Epi-consistency of convex stochastic programs. Stochastics and Stochastics Reports 34 (1991), 83–92; erratum in 37 (1991) 259–260.

[10] D. Plachky: A version of the slln universal under mappings. Research Memorandum, Institute of Mathematical Statistics, University of Münster.

[11] R.T. Rockafellar: Integral functionals, normal integrands and measurable selections. In: Nonlinear Operators and the Calculus of Variations (J. Gossez and L. Waclbroek, eds.), Lecture Notes in Mathematics 543, Springer-Verlag, Berlin, 1976, pp. 157–207.

[12] R.T. Rockafellar, R.J-B Wets: Variational analysis: an introduction. In: Multifunctions and Integrands Stochastic Analysis and Optimization (G. Salinetti, ed.), Lecture Notes in Mathematics 1091, Springer-Verlag, Berlin, 1984, pp. 1–54.

[13] D.W. Walkup, R.J-B Wets: Stochastic programs with recourse. SIAM J. Appl. Math. 15 (1967), 1299–1314.

[14] R.J-B Wets: Stochastic programs with fixed recourse: The equivalent deterministic program. SIAM Review 16 (1974), 309–339.

[15] R.J-B Wets: Stochastic programming. In: Handbook for Operations Research and Management Science, Vol. 1 (G. Nemhanser and A. Rinooy Kan, eds.), Elsevier Science Publishers, Amsterdam, 1989, pp. 573–629.

18 Z. Artstein, R. J-B. Wets / Consistency of Minimizers HIER :

Leere Seite