Stochastic mathematical programs with equilibrium constraints

Michael Patriksson^{∗} and Laura Wynter^{†}

June 16, 1999

Abstract

We introduce Stochastic Mathematical Programs with Equilibrium Constraints (SMPEC), which generalize MPEC models by explicitly incorporating possible uncertainties in the problem data to obtain robust solutions to hierarchical problems. For this problem, we establish results on the existence of solutions, and on the convexity and directional differentiability of the implicit upper-level objective function, both for continuously and discretely distributed probability distributions. In so doing, we establish links between SMPEC models and two-stage stochastic programs with recourse. We also discuss basic parallel iterative algorithms for discretely distributed SMPEC problems.

Key words: Bilevel programming, variational inequality problems, stochastic programming, existence of solutions

1 Introduction

The present paper serves to introduce a framework for hierarchical decisionmaking under uncertainty. Hierarchical decision-making problems are encountered in a wide variety of domains in the engineering and experimental natural sciences, and in regional planning, management, and economics. These problems are all defined by the presence of two or more objectives with a prescribed order of priority or information. We consider in this paper a sub-class of these problems having two levels, or objectives. We refer to the upper level as the objective having the highest priority and/or information level; it is defined in terms of an optimization with respect to one set of variables. The lower-level problem, which in the most general case is described by a variational inequality, is then a supplementary problem parameterized by the upper-level variables. These models are known as generalized bilevel programming problems, or mathematical programs with equilibrium constraints (MPEC); see, for example, Luo et al. [13].

∗Department of Mathematics, Chalmers University of Technology, Gothenburg, Sweden, email: mipat@math.chalmers.se

†PRISM, Computer Science Department, Université de Versailles, Versailles, France, email:

Laura.Wynter@prism.uvsq.fr

In applications relating to Stackelberg game theory, economics, and decision analysis, a number of the problem inputs will often be subject to uncertainty. This is true in particular with respect to costs, demands, and system capacities, which are subject to fluctuations and/or are difficult to measure. In hierarchical models of engineering design and physical phenomena, external conditions and measurement or manufacturing errors introduce uncertainty into the problems. In both of these cases, the uncertainty can be included explicitly by generalizing some of the problem parameters to random variables. However, this generalization complexifies the model significantly; resolution strategies will in many cases require some approximation methods to solve the resulting stochastic programs.

In the simplest case, the expected values of the random variables could be substituted for their distributions and a deterministic model then solved. However, in a nonlinear problem subject to constraints, the effect of this simplification can be quite costly. Indeed, not only will the optimal cost of the expected value solution not necessarily represent the average of the possible optimal costs, but the solution may not even be feasible with respect to the realized values of the random variables. In the case of bilevel pricing and other applications of the Stackelberg game model (consider, for example, the network design problem of Marcotte [14]), user demands are often known only probabilistically. A robust model should then take into account explicitly the range of possible demand values in order to minimize the costs of insufficient capacity when the true demands are realized. Similarly, in topology optimization in structural mechanics (see, for example, Marti [16], and Christiansen et al. [3]), uncertainty enters naturally through random properties of the materials used and possible obstacles, and through conditions that will affect the structure once it has been built, such as varying weather conditions and external forces (or, loads).

To take into account explicitly the variability of the random inputs, as well as the possible infeasibility, we consider a stochastic programming extension of the mathematical programming problem with equilibrium constraints.

We thus define the following stochastic MPEC:

[SMPEC-Ω]

minimize E_{ω} [f(x, y(ω))] := ∫_{Ω} f(x, y(ω)) dF (ω),  (1a)
subject to x ∈ X ,  (1b)

where, for every ω ∈ Ω ⊂ ℜ^{l}, y(ω) ∈ S(x, ω) := { y ∈ ℜ^{m} | −T (x, ω, y) ∈ N_{Y(x,ω)}(y) } denotes the set of solutions to the lower-level variational inequality problem, parameterized by the upper-level variable, x. The random variable ω is defined on a probability space (Ω, A, P). Further, E_{ω} denotes the expected value with respect to ω ∈ Ω, f : ℜ^{n+m} ↦ ℜ ∪ {+∞} denotes the upper-level objective function, F denotes the cumulative distribution function, assumed to be continuously differentiable, with ∫_{Ω} dF (ω) = 1, by construction, and X ⊆ ℜ^{n} denotes the upper-level feasible set.

The lower-level problem is defined by the parameterized mapping T (x, ω, ·) and feasible set Y(x, ω) [presumed convex], and N_{Y(x,ω)}(y) denotes the normal cone to the set Y(x, ω) at y ∈ Y(x, ω). Note that the lower-level problem may admit multiple solutions or no solution for certain values of x and ω; in the former case, we assume that the value of y chosen is that in the set S(x, ω) which yields the lowest value of the integral in (1a). In this way, we may define an objective function for [SMPEC-Ω] which depends on x only.

In practice, it is often impossible to evaluate exactly the expected value in (1a) for problems of realistic size due to the difficulty in calculating the multiple integrals. Therefore, in many applications, it is convenient to make the assumption/approximation that the random variables ω ∈ Ω are discrete or that the joint distribution function can be adequately discretized. In this case the expected value reduces to a sum over a discrete set L of random events, which we number by ℓ = 1, …, |L|. The probability of each such event is then given by ρ_{ℓ} > 0, with ∑_{ℓ∈L} ρ_{ℓ} = 1, by construction. We can then reformulate (1) as the following discretely distributed stochastic MPEC:

[SMPEC-L]

minimize E_{ℓ} [f(x, y_{ℓ})] := ∑_{ℓ∈L} ρ_{ℓ}f(x, y_{ℓ}),  (2a)
subject to x ∈ X ,  (2b)

where, for each ℓ ∈ L, y_{ℓ} ∈ S_{ℓ}(x) := { y ∈ ℜ^{m} | −T_{ℓ}(x, y) ∈ N_{Y_{ℓ}(x)}(y) }.

We note that the deterministic problem, which we will refer to as [MPEC], is obtained when |L| = 1. (This observation will also aid in determining the properties of [SMPEC-L].)

A special case of [MPEC] is bilevel programming, which is obtained when the lower-level variational inequality problem reduces to the optimality conditions for an optimization problem, that is, when, for all x ∈ X, T (x, ·) = ∇_{y}t(x, ·) for some function t : X × ℜ^{m} ↦ ℜ. Usually, bilevel programming is formulated in terms of the corresponding optimization problem, thus leading to the formulation

[BP]

minimize f(x, y),  (3a)
subject to x ∈ X ,  (3b)

where y ∈ arg min_{z∈Y(x)} t(x, z).

We will consider as well a special case of [BP], in which the upper-level objective function f depends on the lower-level solution only in the sense of its optimal value. This problem has been analyzed in Shimizu et al. [21], and is defined as follows:

[BPOV]

minimize f(x, p(x)),  (4a)
subject to x ∈ X ,  (4b)

where

p(x) := inf_{y∈Y(x)} t(x, y).  (4c)

The linear case of [BPOV] is denoted [BLPOV].

The formulations, as well as the notation, of the continuously and discretely distributed stochastic extensions of these special cases, [SBP], [SBPOV], and [SBLPOV], are the obvious.

We also introduce the classical canonical model of two-stage stochastic linear programming with recourse (e.g., Birge and Louveaux [2]):

[2S-SLP]

minimize c^{T} x + Q(x),  (5a)
subject to x ∈ X ,  (5b)

where Q(x) := E_{ω}[Q(x, ω)], and Q(x, ω) := inf_{y}{ q^{T} y | W y = ω − Ax; y ≥ 0 }, ω ∈ Ω, denotes the optimal value of the second-stage linear program.

Similarly, a non-linear form of the two-stage stochastic program with recourse is given as follows:

[2S-SNLP]

minimize E_{ω}[f(x, Q(x, ω))],  (6a)
subject to x ∈ X ,  (6b)

where Q(x, ω) := inf_{y∈Y(x,ω)} t(x, y, ω), ω ∈ Ω. We note that nonlinear forms of two-stage stochastic programs with recourse have been studied to a large extent only for the quadratic case (e.g., Rockafellar and Wets [20] and Birge et al. [1]).

In the rest of the paper, we shall investigate some relationships among the continuously and discretely distributed stochastic extensions of the models [MPEC], [BP], [BPOV], and [2S-SLP]. In particular, we analyze the links between these problem classes, previously not considered together, and present new results on the existence of solutions, and directional differentiability and convexity properties of the implicit upper-level objective function. A final section then briefly mentions some possibilities for constructing parallel iterative resolution methods for the case of discretely distributed probability distributions. We note that a number of related properties of expectation functionals can be found in Wets [22].

First, let us establish the complexity relations between the problem classes. These are illustrated in Figure 1. (The notation [A] ⊂ [B] denotes that the class of problems represented by [A] is included in that of [B].)

All the relations described in Figure 1 follow directly from the problem formulations. Most interesting here is the equality, which equates two-stage stochastic programming with recourse to the optimal value form of stochastic bilevel programming problems.

The figure also illustrates that a particular linear form of [SBPOV] reduces to the classic two-stage stochastic linear program with recourse, [2S-SLP], namely a stochastic version of the right-hand side perturbation model, as discussed in [21, page 189], in which the upper-level variable is located only on the right-hand side Figure 1: Relationships among problem classes

[SBLPOV] ⊃ [2S-SLP]
⋂  ⋂
[SMPEC] ⊃ [SBP] ⊃ [SBPOV] = [2S-SNLP]
⋃  ⋃  ⋃
[MPEC] ⊃ [BP] ⊃ [BPOV]

of the lower-level constraints. (We will see later that this simplification enjoys, in many cases, certain convexity properties.)

Since [BP] is N P-hard, even in the linear case (e.g., Hansen et al. [8]), it is clear that the problem [SMPEC] introduced in this paper is N P-hard, as are the other problems in Figure 1, with the exception of the discrete version of the problem [2S-SLP], which is equivalent to a linear program, and is thus in P.

2 Existence of solutions

Consider the following general hierarchical programming model, which encompasses all those presented in Section 1.

[HP]

minimize f(x, v),  (7a)
subject to x ∈ X ,  (7b)

where v ∈ S(x), and S : ℜ^{n} ↦ 2^{ℜ^{s}} denotes a point–to–set mapping on ℜ^{n}. We let gr S := { (x, v) ∈ ℜ^{n+s} | v ∈ S(x) } denote the graph of the mapping S.

The main result of this section is a general existence result for [HP], which in the forthcoming will be specialized to allow existence to be established for all of the problem classes introduced in Section 1.

First, we show that [HP] encompasses the problems of Figure 1.

Proposition 2.1 The problems [SMPEC-L] and [SMPEC-Ω] reduce to [HP].

Proof: In the former case, let v = (v_{ℓ})_{ℓ∈L}, where v_{ℓ} := y_{ℓ}, S := ∏_{ℓ∈L} S_{ℓ}, and f(x, v) := ∑_{ℓ∈L} ρ_{ℓ}f(x, y_{ℓ}). In the latter case, let v := y(ω), and f(x, v) := E_{ω}[f(x, y(ω))].

Proposition 2.2 The problem [BPOV] reduces to [HP].

Proof: Let v := p(x) and S(x) := {p(x)}.

Consider the following assumptions, which will be necessary for demonstrating the existence of optimal solutions to the problem classes of interest:

(i) The upper-level constraint set, X ⊆ ℜ^{n}, is nonempty and closed.

(ii) The lower-level constraint set, Y(x), is nonempty for at least one x ∈ X , and bounded for all x ∈ X.

(iii) (Slater CQ) The lower-level constraint set, Y(x), is of the form Y(x) := { y ∈ ℜ^{m} | g_{i}(x, y) ≤ 0, i = 1, …, k }, where each function g_{i} : ℜ^{n+m} ↦ ℜ is continuous on ℜ^{n+m} and convex in y for each x ∈ X. Further, either g_{i}(x, ·) = g_{i}(·), i = 1, …, k, that is, Y(x) = Y, or for each x ∈ X there is a y ∈ ℜ^{m} such that g_{i}(x, y) < 0, i = 1, …, k.

(iv) There exists an (x, v) ∈ Z := { (x, v) ∈ gr S | x ∈ X } with f(x, v) < ∞.

(v) (Inf-compactness) f is lower semi-continuous (l.s.c.), proper, and has bounded lower level sets on Z.

Theorem 2.3 (Existence of optimal solutions to [HP]). Let the assumptions (i), (iv), and (v) be satisfied. Further, assume that gr S is closed. Then, [HP] has at least one optimal solution.

Proof: The assumptions imply the inf-compactness of the extended function f + δ_{Z}, where δ_{Z} is the indicator function for the closed set Z. The result then follows from Weierstrass’ Theorem.

A similar result is found in Zhang [23].

Next, we specialize this result to the problems defined in Section 1, and give sufficient conditions for the hypotheses to be satisfied.

Note that the conditions required in the preceding existence result are weaker than those of many previously considered requirements on bilevel model formulations, and as such, may be particularly interesting for a number of important applications.

For example, the following two corollaries allow one to establish the existence of an optimal solution to stochastic (and indeed also deterministic) structural optimization problems in the presence of zero lower bounds on the truss bar volumes. (See [3] for further details.)

In the following corollaries, the assumptions above are expressed using the notation of Propositions 2.1 and 2.2, for each problem class.

Corollary 2.4 (Existence of optimal solutions to [SMPEC-L]). Let the assumption (iii) hold for each ℓ ∈ L, and the mapping T_{ℓ} : ℜ^{n+m} ↦ ℜ^{m} be continuous on X × ℜ^{m}. Then, gr S_{ℓ} is closed for each ℓ ∈ L. Suppose further that the assumption (i) holds, that the assumption (iv) holds for some x over all the sets Z_{ℓ}, ℓ ∈ L, and that the assumption (v) holds with Z replaced by ∪_{ℓ∈L}Z_{ℓ}. Then, there exists at least one optimal solution to [SMPEC-L].

Proof: Each set S_{ℓ}(x) can be equivalently described by

S_{ℓ}(x) = { y ∈ Y_{ℓ}(x) | T_{ℓ}(x, y)^{T} (z − y) ≥ 0, ∀z ∈ Y_{ℓ}(x) }, x ∈ X .

By the assumption (iii), either Y_{ℓ}(x) = Y_{ℓ} holds, in which case the closedness of gr S_{ℓ} follows from the continuity of the mappings T_{ℓ} and g_{ℓ}, or the Slater condition holds, in which case the closedness of S_{ℓ} follows from Hogan [11, Lemma 1].

Corollary 2.5 (Existence of optimal solutions to [SMPEC-Ω]). Let the assumption (iii) hold for each ω ∈ Ω. Further, let T : ℜ^{n+l+m} ↦ ℜ^{m} and g : ℜ^{n+l+m} ↦ ℜ^{k} be continuous on X × Ω × ℜ^{m}. Then, gr S is closed. Suppose further that the assumption (i) holds, that the assumption (iv) holds for some x over all the sets Z(ω), ω ∈ Ω, almost surely, and that the assumption (v) holds with Z replaced by ∪_{ω∈Ω}Z(ω). Then, there exists at least one optimal solution to [SMPEC-Ω].

Proof: The continuity assumptions on T and g, together with the assumption (iii) for each ω ∈ Ω, imply that the mapping (x, ω) ↦ S(x, ω) is closed on X × Ω, and hence also the set gr S is closed, following the proof of Corollary 2.4. It follows from the lower semi-continuity of f that the integrand in (1a) is l.s.c. in ω (and hence integrable), and that, by the linearity of the integration operation and the fact that f is proper, the integral in (1a) also is l.s.c. Since there exists an x ∈ X such that this integral has a finite value, by the assumption (v), it is inf-compact. The desired result then follows as in Theorem 2.3.

Corollary 2.6 (Existence of optimal solutions to [SBP-L]). Let the assumption (iii) hold for each ℓ ∈ L, and the function t_{ℓ} : ℜ^{n+m} ↦ ℜ be continuous on X ×ℜ^{m}. Then, gr S_{ℓ} is closed for each ℓ ∈ L. Suppose further that the assumption (i) holds, that the assumption (iv) holds for some x over all the sets Z_{ℓ}, ℓ ∈ L, and that the assumption (v) holds with Z replaced by ∪_{ℓ∈L}Z_{ℓ}. Then, there exists at least one optimal solution to [SBP-L].

Proof: The proof is similar to that of Corollary 2.4, the closedness result following from [11, Lemma 1].

Corollary 2.7 (Existence of optimal solutions to [SBP-Ω]). Let the assumption (iii) hold for each ω ∈ Ω. Further, let t : ℜ^{n+l+m} ↦ ℜ and g : ℜ^{n+l+m} ↦ ℜ^{k} be continuous on X × Ω × ℜ^{m}. Then, gr S is closed. Suppose further that the assumption (i) holds, the assumption (iv) holds for some x over all the sets Z(ω), ω ∈ Ω, almost surely, and that the assumption (v) holds with Z replaced by ∪_{ω∈Ω}Z(ω). Then, there exists at least one optimal solution to [SBP-Ω].

Proof: The proof follows from that of Corollary 2.5.

Corollary 2.8 (Existence of optimal solutions to [SBPOV-L]). Under the assumptions of Corollary 2.6, there exists at least one optimal solution to [SBPOV-L].

Proof: The result is a special case of Corollary 2.6.

Corollary 2.9 (Existence of optimal solutions to [SBPOV-Ω]). Under the assumptions of Corollary 2.7, there exists at least one optimal solution to [SBPOV-Ω].

Proof: The result is a special case of Corollary 2.7.

The following is an example of a result that can be established for [2S-SLP] by using the links to bilevel programming. (Existence results for two-stage stochastic linear programming based on general linear programming properties can be found in [2, Section 3.1].

Corollary 2.10 (Existence of an optimal solution to [2S-SLP]). Let assumption (ii) hold for some x ∈ X and for each ω ∈ Ω. Suppose further that assumption (i) holds, and that the upper-level feasible set, X, is bounded. Then, there exists at least one optimal solution to [2S-SLP].

Proof: By the linearity of all of the problem functions, (i) and (ii) along with the boundedness of X imply (iv) and (v). Then, the result follows from that of Corollary 2.7.

3 Convexity

We next establish the convexity of some interesting special cases of [SMPEC].

Theorem 3.1 (Convexity of [SBPOV-L]). In addition to the assumptions of Corollary 2.8, suppose, for each ℓ ∈ L, that t_{ℓ} and g_{i,ℓ}, i = 1, …, k, are convex on ℜ^{n+m}. Then, each function p_{ℓ} : X ↦ ℜ ∪ {+∞}, defined by (4c), is convex on X. Further, assume that X is convex, and that the function f : X × ℜ ↦ ℜ is convex on X × ℜ and increasing in its second argument. Then, the implicit upper-level objective function x ↦ ∑_{ℓ∈L} ρ_{ℓ}f(x, p_{ℓ}(x)) is convex on X, so that [SBPOV-L] is a convex problem.

Proof: We need only to establish the convexity of p_{ℓ}, ℓ ∈ L, on X, but this result follows from the assumptions and Geoffrion [7, Theorem 5].

Theorem 3.2 (Convexity of [SBPOV-Ω]). In addition to the assumptions of Corollary 2.9, suppose, for each ω ∈ Ω, that t(·, ω, ·) and g_{i}(·, ω, ·), i = 1, …, k, are convex on ℜ^{n+m}. Then, each function p(·, ω) : X ↦ ℜ ∪ {+∞}, defined by (4c), is convex on X. Further, assume that X is convex, and that the function f : X × ℜ ↦ ℜ is convex on X × ℜ and increasing in its second argument. Then, the implicit upper-level objective function x ↦ E_{ω}[f(x, p(x, ω))] is convex on X, so that [SBPOV-Ω] is a convex problem.

Proof: The convexity of p(·, ω), ω ∈ Ω, on X follows as in the proof of Theorem 3.1. The linearity of the integration then yields the desired result.

It is clear that the convexity of [2S-SLP] is a special case of that of [SBPOV-Ω]. (Compare, for example, with [2, Corollary 3.33]).

4 Differentiability

In this section, we will examine the directional differentiability of the implicit upper-level objective function of [HP], and, as before, specialize that result to the different problem classes. Let us first consider a number of assumptions.

(a) The function f is continuously differentiable on X × ℜ^{m}.

(b) The lower-level constraint set, Y(x), is of the form Y(x) := { y ∈ ℜ^{m} | g_{i}(x, y) ≤ 0, i = 1, …, k }, where each function g_{i} : ℜ^{n+m} ↦ ℜ is twice continuously differentiable on ℜ^{n+m} and convex in y for each x ∈ X. Further, for each x ∈ X, Y(x) ≠ ∅ and Y(x) ⊂ B, for some open and bounded set B ∈ ℜ^{m}.

(c) (Linear independence CQ) Let I(x, y) := { i = 1, …, k | g_{i}(x, y) = 0 }. Then, for each x ∈ X and y ∈ S(x), the partial gradients ∇_{y}g_{i}(x, y), i ∈ I(x, y), are linearly independent.

(d) The mapping T is continuously differentiable on X ×ℜ^{m} and strongly monotone in y for each x ∈ X.

(d′) The mapping T is continuously differentiable on X × ℜ^{m} and monotone in y for each x ∈ X.

The following Theorem, presented without proof, follows directly from Robinson [18, 19].

Theorem 4.1 (Directional differentiability for [HP]). Let the assumption (a) be satisfied and the implicit mapping x ↦ S(x) be locally Lipschitz continuous on X. Then, the implicit upper-level objective function x ↦ f(x, S(x)) of [HP] is locally Lipschitz continuous and directionally differentiable on X.

Next, we provide sufficient conditions for the directional differentiability of the implicit upper-level objective functions for the problem classes presented in Section 1.

Corollary 4.2 (Directional differentiability for [SMPEC-L]). Let the assumption (a) hold, and the assumptions (b)–(d) be satisfied for each ℓ ∈ L. Then, the implicit upper-level objective function x ↦ ∑_{ℓ∈L} ρ_{ℓ}f(x, y_{ℓ}(x)) of [SMPEC-L] is locally Lipschitz continuous and directionally differentiable on X.

Proof: By Robinson [18, Theorem 2.1], the assumptions (a)–(d) imply that for each ℓ ∈ L, the implicit mapping x ↦ S_{ℓ}(x) is locally Lipschitz continuous. Then, by Theorem 4.1, the result follows.

Corollary 4.3 (Directional differentiability for [SMPEC-Ω]). Let the assumptions of Corollary 2.5 hold. Further, let the assumption (a) hold, and the assumptions (b)–(d) be satisfied, almost surely. Then, the implicit upper-level objective function x ↦ E_{ω}[f(x, y(x, ω))] of [SMPEC-Ω] is locally Lipschitz continuous and directionally differentiable on X.

Proof: Note that under the assumptions of Corollary 2.5, the integral in (1a) exists. As in Corollary 4.2, the implicit function x ↦ S(x, ω) is locally Lipschitz continuous. The integration preserves the locally Lipschitz continuity, since the Lipschitz constant of f remains bounded on any bounded subset of X, and is therefore integrable. The result then follows by Theorem 4.1.

The following result, adapted from Fiacco [6], illustrates that the requirements needed to ensure the directional differentiability of the implicit upper-level objective function of [SBPOV] are weaker than those of [SMPEC].

Corollary 4.4 (Directional differentiability for [SBPOV-L]). Let the assumption (a) hold, and the assumptions (b), (c), and (d′) be satisfied for each ℓ ∈ L. Then, the implicit upper-level objective function x ↦ ∑_{ℓ∈L} ρ_{ℓ}f(x, p_{ℓ}(x)) of [SBPOV-L] is locally Lipschitz continuous and directionally differentiable on X.

Proof: By the result of [6], under the assumptions (b), (c) and (d′), the optimal value function x ↦ p_{ℓ}(x) is directionally differentiable on X, for all ℓ ∈ L. Then, by Corollary 4.2, with assumption (a), the result follows.

Corollary 4.5 (Directional differentiability for [SBPOV-Ω]). Let the assumptions of Corollary 4.3 hold, except that the assumption (d) is replaced by the weaker assumption (d′). Then, the implicit upper-level objective function x ↦ E_{ω}[f(x, p(x, ω))] of [SBPOV-Ω] is locally Lipschitz continuous and directionally differentiable on X.

Proof: Follows directly from using Corollary 4.3 and arguments similar to those in the proof of Corollary 4.4.

5 Algorithms for SMPEC

Deterministic MPEC models are notoriously difficult and time-consuming to solve because of their non-convexity coupled with the nondifferentiability of the implicit upper-level objective function. (Differentiability can only be asserted under the additional condition that strict complementarity holds.) The introduction of a random distribution on some or all of its parameters causes an even greater increase in the problem size and computational complexity. For this reason, the development of efficient methods is primordial, as are the use of parallel strategies, whenever possible.

In this paper, we have presented a taxonomy which highlights the principal features of each problem type, and which therefore facilitates the adaptation of algorithms.

For example, descent algorithms developed for deterministic MPEC can be adapted to SMPEC as long as the local Lipschitz continuity and directional differentiability of the stochastic objective function can be maintained. Corollaries 4.2 and 4.3 present the conditions needed. Similarly, algorithms for solving BPOV can be adapted to SBPOV as long as the conditions of Corollary 4.4 or 4.5 are satisfied.

Further, in the case of [SMPEC-L] or [SBPOV-L], subgradients can be calculated efficiently if one makes use of the decomposability of the problem.

For example, based on the notation of [SMPEC-L], and following the approach of Outrata and Zowe [17] for [MPEC], a subgradient of the implicit upper-level function f at x is given by the formula

ξ_{f}(x) := ∑_{ℓ∈L} ρ_{ℓ}[∇_{x}f(x, y_{ℓ}) + ∇_{x}L_{ℓ}(x, y_{ℓ}, λ_{ℓ})^{T} d_{y_{ℓ}} − ∇_{x}g_{J (x,ℓ)}(x, y_{ℓ})^{T} d_{λ_{J (x,ℓ)}}], (8)

where, for each ℓ ∈ L, L_{ℓ}(x, y_{ℓ}, λ_{ℓ}) := T_{ℓ}(x, y_{ℓ}) + ∇_{y}g(x, y_{ℓ})^{T} λ_{ℓ} is the Lagrangean of the lower-level problem, with y_{ℓ} := y_{ℓ}(x) for brevity, and λ_{ℓ} being the (unique, under the conditions of Corollary 4.2) vector of multipliers for the parameterized lower-level constraints. Furthermore, for each ℓ ∈ L, the set J (x, ℓ) is chosen such that I(x, ℓ) ⊇ J (x, ℓ) ⊇ I_{+}(x, ℓ) holds, where I(x, ℓ) denotes the set of active lower-level constraints at (x, y_{ℓ}), and I_{+}(x, ℓ) is the subset for which the multiplier values are positive, and (d_{y_{ℓ}}, d_{λ_{J (x,ℓ)}}) solves the linear system

[\begin{matrix}∇_{y}L_{ℓ}(x, y_{ℓ}, λ_{ℓ}) & −∇_{y}g_{J (x,ℓ)}(x, y_{ℓ})^{T} \\ ∇_{y}g_{J (x,ℓ)}(x, y_{ℓ}) & 0^{m×|J (x,ℓ)|} \end{matrix} ] (\begin{matrix}d_{y_{ℓ}} \\ d_{λ_{J (x,ℓ)}} \end{matrix}) = (\begin{matrix}−∇_{y}f(x, y_{ℓ}) \\ 0^{m} \end{matrix}) . (9)

Each component of the subgradient can be calculated independently and in parallel. The subgradient can then be used in an algorithm for the heuristic solution of the problem or be embedded within a more sophisticated algorithm. A simple scheme is to take, at some iteration t,

x^{t+1} := P_{X} [x^{t} − γ_{t}ξ_{f}(x^{t})],

for some γ_{t} > 0 determined through an inexact line search. Note that, at points of nondifferentiability, the method may break down because the negative of the subgradient may then not be a descent direction; in order to obtain a well-defined iteration at such points, one can envisage utilizing a step length which is the maximum of the one supplied by a backtracking line search and the result of a predetermined step length formula used in traditional subgradient optimization techniques. Outrata and Zowe [17] utilize the deterministic analog of the systems (8) and (9) in the development of a bundle method for the solution of [MPEC], which immediately extends to the solution of [SMPEC-L].

Consider the following parallel resolution strategy for this model. In some cases, one may identify a cluster of similar scenarios. Allocating these to the same processor, one may solve the corresponding lower-level problems by utilizing efficient reoptimization procedures given that any of them have been solved to optimality, since the optimal solution to any one of them is feasible as well as near-optimal to all the others. Further, for scenarios with slightly differing sets, J (x, ℓ), consider sorting subsets of the scenarios so that J (x, ℓ_{1}) ⊂ J (x, ℓ_{2}), and so on. Then, one may solve the preceding linear systems in sequence, expanding the matrix with the necessary rows and columns and utilizing the solution to the former system as a starting point in the search for the next. The fact that the choice of J (x, ℓ) is arbitrary in the range of active constraints may also assist in the construction of the afore-mentioned clusters (and the subsequent solutions of the linear systems) through a minimization of the number of scenarios with distinct values of J (x, ℓ).

Another algorithmic method that can be transfered to [SMPEC-L] is the class of penalty methods for [MPEC]. Assume that for each ℓ ∈ L there is a (continuous) function, ψ_{ℓ} : ℜ^{n+m} ↦ ℜ ∪ {+∞}, which satisfies ψ_{ℓ}(x, y) ≥ 0 for all (x, y) ∈ X × ℜ^{m}, and

ψ_{ℓ}(x, y) = 0  ⟺  y ∈ S_{ℓ}(x).

Then, the inclusion (2b) can be represented by a single equation in y. The penalized problem is then defined for η_{ℓ} > 0 by

minimize ∑_{ℓ∈L} ρ_{ℓ}[f(x, y_{ℓ}) + η_{ℓ}ψ_{ℓ}(x, y_{ℓ})],
subject to x ∈ X .

In the deterministic case, such approaches have been devised by Harker and Choi [9], and Marcotte and Zhu [15]. See also Larsson and Patriksson [12] for other examples of differentiable, and typically non-convex, merit functions for variational inequality problems and Facchinei and Soares [5] for NCP-functions for the VIP primal–dual optimality conditions.

Again, this penalty approach can be easily parallelized, since the evaluation of the penalty function and its derivatives can be done independently over the different scenarios.

Several other methods for solving BP and MPEC problems have appeared in the literature in recent years (see, e.g., [13, 21] for overviews, and the recent smoothing method of Facchinei et al. [4]). These methods can generally be adapted to solving the discretely-distributed stochastic models presented here.

In the case of large-scale models, and when the number of scenarios is very high, however, simple parallelization strategies over the scenarios may however not make the model tractable. In these cases it may be necessary to develop further approximation schemes, such as approximating the lower-level problem, or constructing aggregation/disaggregation strategies with respect to the scenarios.

In the case of continuously distributed SMPEC problems like [SMPEC-Ω] or [SBPOV-Ω], no such decomposition over scenarios is available, and the presence of the multiple integral in the objective function generally necessitates numerical integration at each upper-level iteration. Birge et al. [1] propose an approximate Newton method as well as a modification of the stochastic decomposition method of Higle and Sen [10] to solve quadratic stochastic programs with recourse. These problems are in fact quadratic instances of SBPOV with a separable objective function and polyhedral constraints. Other strategies for solving [SMPEC-Ω] and [SBPOV-Ω] may make use of random sampling of the continuous distribution, as is done within the class of stochastic quasi-gradient methods.

References

[1] J. R. Birge, X. Chen, L. Qi, and Z. Wei, “A stochastic Newton method for stochastic quadratic programs with recourse,” technical report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, 1995.

[2] J. R. Birge, and F. Louveaux, Stochastic Programming, Springer-Verlag, New York, NY, 1997.

[3] S. Christiansen, M. Patriksson, and L. Wynter, “Stochastic bilevel programming in structural optimization,” technical report, PRISM, Computer Science Department, Université de Versailles, Versailles, France, 1999. Submitted.

[4] F. Facchinei, H. Jiang, and L. Qi, “A smoothing method for mathematical programs with equilibrium constraints,” Mathematical Programming 85, 107–134 (1999).

[5] F. Facchinei and J. Soares, “A new merit function for nonlinear complementarity problems and a related algorithm,” SIAM Journal on Optimization 7, 225–247 (1997).

[6] A. V. Fiacco, “Optimal value continuity and differential stability bounds under the Mangasarian–Fromovitz constraint qualification,” in: Mathematical Programming with Data Perturbations II, A. V. Fiacco, ed., Marcel Dekker, New York, NY, 1983, pp. 65–90.

[7] A. M. Geoffrion, “Elements of large-scale mathematical programming,” Management Science 16, 652–691 (1970).

[8] P. Hansen, B. Jaumard, and G. Savard, “New branch-and-bound rules for linear bilevel programming,” SIAM Journal on Scientific and Statistical Computing 13, 1194–1217 (1992).

[9] P. T. Harker and S.-C. Choi, “A penalty function approach for mathematical programs with variational inequality constraints,” Information and Decision Technologies 17, 41–50 (1991).

[10] J. L. Higle and S. Sen, “Stochastic decomposition: An algorithm for two stage linear programs with recourse,” Mathematics of Operations Research 16, 650–669 (1991).

[11] W. W. Hogan, “Directional derivatives for extremal-value functions with applications to the completely convex case,” Operations Research 21, 188–209 (1973).

[12] T. Larsson and M. Patriksson, “A class of gap functions for variational inequalities,” Mathematical Programming 64, 53–79 (1994).

[13] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.

[14] P. Marcotte, “Network design problem with congestion effects: A case of bilevel programming,” Mathematical Programming 34, 142–162 (1986).

[15] P. Marcotte and D. Zhu, “Exact and inexact penalty methods for the generalized bilevel programming problem,” Mathematical Programming 74, 141–157 (1996).

[16] K. Marti, ed., “Structural Reliability and Stochastic Structural Optimization,” special issue of Mathematical Methods of Operations Research 46, no. 3 (1997).

[17] J. Outrata, and J. Zowe, “A numerical approach to optimization problems with variational inequality constraints,” Mathematical Programming 68, 105–130 (1995).

[18] S. M. Robinson, “Strongly regular generalized equations,” Mathematics of Operations Research 5, 43–62 (1980).

[19] S. M. Robinson, “An implicit-function theorem for a class of nonsmooth functions,” Mathematics of Operations Research 16, 282–309 (1991).

[20] R. T. Rockafellar, and R. J.-B. Wets, “A Lagrangian finite generation technique for solving linear–quadratic problems in stochastic programming,” Mathematical Programming Study 28, 63–93 (1986).

[21] K. Shimizu, Y. Ishizuka, and J. Bard, Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic Publishers, Boston, MA, 1997.

[22] R. J.-B. Wets, “Stochastic programming”, Chapter VIII in Optimization, volume 1 in Handbooks in Operations Research and Management Science, G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, eds., North-Holland, Amsterdam, 1989, pp. 573–629.

[23] R. Zhang, “Problems of hierarchical optimization in finite dimension,” SIAM Journal on Optimization 4, 521–536 (1994).