|
Article Excerpt
We consider stochastic mathematical programs with complementarity constraints in which both the objective and constraints involve limit functions that need to be approximated. Such programs can be used for modeling "average" (expected) or steady-state behavior of complex stochastic systems. We first describe these stochastic mathematical programs with complementarity constraints and compare them with different stochastic mathematical programs with equilibrium constraints from the literature. This explicit discussion may facilitate selecting an appropriate stochastic model. We then describe a simulation-based method called sample-path optimization for solving these problems and provide sufficient conditions under which appropriate approximating problems will have solutions converging to a solution of the original problem almost surely. We illustrate an application on toll pricing in transportation networks. We explain how uncertainty can be incorporated and the approximating problems are solved using an off-the-shelf solver. These developments enable solving certain stochastic bilevel optimization problems and Stackelberg games using simulation.
Key words: stochastic mathematical programs with complementarity constraints; simulation; stability; mathematical programs with equilibrium constraints; stochastic network equilibrium; toll pricing problem
MSC2000 subject classification: Primary: 90C15, 90C31, 90C33; secondary: 90B15, 90B20, 91B70
OR/MS subject classification: Primary: Programming/complementarity and stochastic; secondary: games/stochastic, simulation/applications, transportation/traffic models
History: Received March 11, 2005; revised November 10, 2005, and February 16, 2006.
1. Introduction. In the last decade, many researchers have studied solution methods for mathematical programs with complementarity constraints (MPCC). Primarily, these programs arise in reformulations of important optimization problems such as mathematical programs with equilibrium constraints (MPEC) (Luo et al. [24]), generalized semi-infinite programs (Still [40]), or bilevel optimization problems (Bard [1] and Dempe [5]). Naturally, the crucial role of the MPCCs also attracted the attention of practitioners, since these mathematical programs are important modeling tools for numerous applications. In particular, they are useful for modeling bilevel or, in broader terms, hierarchical decisions expressed by upper and lower-level variables. Among such applications, we note Stackelberg games of mathematical economics, congestion problems in transportation networks, pricing in telecommunication networks, motion planning in robotics, and optimal design of mechanical systems; see Luo et al. [24], Ferris and Pang [10], Bard [1], Outrata et al. [26], and Dempe [5] for other applications.
When pursuing a realistic modeling approach, decision makers are usually faced with uncertainty. For instance, costs in a transportation network or measurements in a mechanical system are liable to intrinsic uncertainty by the nature of the problem. In certain cases, the uncertainty may be expressed explicitly by means of random model parameters, an approach which leads to stochastic mathematical programming formulations. In the present paper we explicitly describe three different stochastic formulations and give their comparative interpretations. Among these formulations, we then focus on a particular one that can be solved by a simulation-based method, so-called sample-path optimization.
Roughly speaking, sample-path methods are concerned with solving a problem of optimization and/or equilibrium, involving a limit function [f.sub.[infinity]] which is not observable. However, one can observe functions [f.sub.n] that almost surely converge pointwise to [f.sub.[infinity]] as n [right arrow] [infinity]. In the kind of applications we have in mind, [f.sub.[infinity]] could be a steady-state performance measure of a dynamic system or an expected value in a static system, and we use simulation to observe the [f.sub.n]'s. In systems that evolve over time, we simulate the operation of the system for, say, n time units and then compute an appropriate performance measure. In static systems we repeatedly observe instances of the system and compute an average. In both cases, to observe [f.sub.n] at different parameter settings we use the method of common random numbers. Furthermore, in many cases derivatives or directional derivatives of the [f.sub.n] can be obtained using well-established methods of gradient estimation such as infinitesimal perturbation analysis (IPA) (see Ho and Cao [17] and Glasserman [12]) or automatic differentiation capabilities (see Griewank [13]). For example, if the [f.sub.n] are differentiable and have closed-form expressions, then one can conveniently use an algebraic modeling language, such as GAMS, having automatic differentiation capabilities. The key point is the following: Once we fix n and a sample point (using common random numbers), [f.sub.n] becomes a deterministic function. Sample-path methods then solve the resulting deterministic problem (using [f.sub.n] with the fixed sample path selected) and take the solution as an estimate of the true solution. Clearly, the availability of very powerful deterministic solvers (both for optimization and for equilibrium problems) makes this approach very attractive.
In general, the results which provide theoretical support for sample-path methods are based on the sensitivity analysis of the corresponding deterministic problems. This aspect is illustrated by Robinson [32] for simulation optimization problems with deterministic constraints, as well as by Gurkan et al. [15] for stochastic variational inequalities. Following a similar argument, we build our sample-path analysis of stochastic MPCCs on the recent work of Scheel and Scholtes [36] who set forth important sensitivity results for deterministic MPCCs.
In our view, the present paper makes the following contributions:
* We propose a modeling structure for a class of stochastic MPCCs in which the expectations or limit functions must be approximated/estimated, for example, by using simulation.
* We present sufficient conditions under which the approximating problems will have solutions almost surely and these approximate solutions will be close to a solution of the original problem, provided the simulation run length is sufficiently large. This provides the theoretical support for the convergence of the sample-path method applied to the class of stochastic MPCCs addressed.
* We use an application related to toll pricing in transportation networks to illustrate how the method can be implemented.
Alongside, we provide sensitivity results for deterministic MPCCs complementary to those presented by Scheel and Scholtes [36] in terms of weaker sufficient conditions for stability (by interpreting the approximating functions as nonparametric perturbations of the true functions). In addition, we also provide a unifying discussion on an alternative set of sufficient conditions and derive a complementary result to Gurkan et al. [15] regarding the analysis of stochastic variational inequalities. As part of our analysis, we make use of the equivalence of two different regularity conditions, namely the nonvanishing determinantal sign condition of Scheel and Scholtes [36] and the strong regularity condition (to an appropriate generalized equation) of Robinson [31].
The remainder of this paper is organized as follows. In [section]2, we provide some related background material and specify the problem under consideration. In [section]3, we first restate some essential concepts, then use them in analyzing the sample-path solution of stochastic MPCCs and provide a discussion on stronger conditions to obtain stronger results. In [section]4, we include an illustrative example and provide numerical experiments. Finally, in [section]5 we give a summary and conclude the paper. Our analysis uses some regularity conditions for generalized equations and nonlinear programs. Since these conditions are rather technical and already discussed in the literature (see Facchinei and Pang [8] and references therein), we only give in Appendix A the appropriate forms required for our analysis. We often refer to the main theorem in Gurkan et al. [15] for convenience; this theorem is restated in Appendix B. Moreover, Appendix C contains an auxiliary result used in our analysis.
We hope that this paper caters for both theoretically and practically oriented readers. Both reader groups share [subsection]1 and 2 and readers with a theory interest can then concentrate on [section]3 and glance through [section]4, while the more application-oriented readers will get more out of [section]4 and can concentrate only on the approximating setup introduced in [section]3 and take the rest of the theoretical results for granted.
2. Literature review.
2.1. Background material for MPECs. In this section, we give some background material and terminology related to deterministic mathematical programs with equilibrium constraints (MPEC). The exposition below closely follows Luo et al. [24].
Suppose that some functions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are given, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a nonempty closed set, and for each [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], C(X) is a closed convex subset of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using these elements, the mathematical program with equilibrium constraints can be formulated as
MPEC min f(x, y) subject to (x, y) [member of] Z F(x, y)(v - y) [greater than or equal to] [for all] v [member of] C(x). (1)
Two sets of variables are distinguished--the upper-level variables [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the lower-level variables [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] while the overall objective function f to be minimized depends on both x and y. Z denotes the joint upper-level feasible set for the pair (x, y). The equilibrium constraints are defined by a parametric variational inequality with x as parameter vector and y as variables. In this inner problem, F is the equilibrium function while C(x) defines the restriction set of y for each given x.
The joint constraints set Z can be quite general; for example, we will define it by equality or inequality constraints as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are given functions. A particular situation arises when C(x) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all x; in this case, MPEC is equivalent to the following mathematical program with complementarity constraints:
min f(x, y) subject to g(x, y) [less than or equal to] 0, h(x, y) = y [greater than or equal to] 0, F(x, y) [greater than or equal to] 0, y F(x, y) = 0. (2)
Note that the set of constraints in (2) represents the usual parametric nonlinear complementarity problem. In particular, a bilevel optimization problem can be seen as a special case of MPEC in which the mapping F(x, x) is the partial gradient (with respect to y) of a real-valued, continuously differentiable function.
A well-known example of an MPEC is the leader-follower (Stackelberg) game from mathematical economics. Suppose there exists a set of rational players who try to select the best strategies from their sets of alternatives so they can maximize their utilities. Among these players there is a distinctive player called the leader, whose decision can impact the strategies chosen by the other players, i.e., the followers. Given the leader's preference, the other users play a Nash game and try to optimize their own utilities. Therefore, the leader's strategy plays the role of the upper-level variable. The resulting MPEC problem is to select the best strategy that maximizes the leader's utility and, at the same time, guarantee a Nash equilibrium among the other players. In [section]4, as an illustrative example, we will outline in detail another application related to toll pricing in transportation networks.
Using the nonsmooth min operator, the problem above can be rewritten as
min f(x, y) subject to g(x, y) [less than or equal to] 0, h(x, y) = min{[y.sub.k], [F.sub.k](x, y)} = [for all] k = 1, ..., [n.sub.2]. (3)
In the present paper, we consider the following generalization of problem (3). Let z = (x, y) and [n.sub.0] = [n.sub.1] + [n.sub.2] denote the dimension of z. Introduce an open set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let f: [THETA] [right arrow] R, g: [THETA] [right arrow] [R.sup.p], and h: [THETA] [right arrow] [R.sup.q] be twice differentiable functions, and for m [greater than or equal to] 1 and l [greater than or equal to] 2, define the matrix valued function F: [THETA] [right arrow] [R.sup.mxl] with twice differentiable components [F.sub.kj]: [THETA] [right arrow] R, k = 1, ..., m and j = 1, ..., l. Then, the mathematical program with complementarity constraints under consideration becomes:
MPCC min f(z) subject to g(z) [less than or equal to] 0, h(z) = min{[V.sub.k1](Z), ..., [F.sub.k1](Z)} = [for all] k = 1, ..., m. (4)
Here the variable z includes the decisions at all levels; the constraint min{[F.sub.k1](Z), ..., [F.sub.k1](Z)} = implies that [F.sub.kj](z) [greater than or equal to] for every j = 1, ..., l and [F.sub.k1](Z)[F.sub.k2](Z) ... [F.sub.k1](Z) = 0. Several theoretical issues related to problem (4) have been extensively studied; see Scheel and Scholtes N36].
2.2. Different formulations of stochastic MPECs. As mentioned earlier, MPECs are used for modeling bilevel or, in broader terms, hierarchical decisions expressed by upper and lower-level variables. When these decisions are subject to significant uncertainty, additional distinctions have to be made in order to relate the modeling process to the uncertain data. In our view, different interpretations of the uncertainty and the modeling concerns lead to three different formulations in an MPEC setting. In this section, we first indicate the class of stochastic MPCCs we address in this paper and then review the literature related to stochastic MPECs.
We are interested in the class of stochastic MPCCs in which, potentially, all of the defining functions f, F, g, or h (or some of their components) may represent a limit function or an expectation and, therefore, can not be directly observed. Formally, we address the following problem:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)
where any of [f.sub.[infinity]], [F.sup.[infinity]], [g.sup.[infinity]], or [h.sup.[infinity]] (or some of their components) may be unobservable. We use the expression "limit function" and the subscripts "[infinity]" to indicate that we do not have an explicit expression of these functions available to us.
A particular example in which expectations are involved in the objective function and in all the constraints is the following:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)
where [omega] represents the uncertain element as a random variable defined on a common probability space ([OMEGA], F, p) and
Z = {(x, y)| [E.sub.[omega]][g(x, y, [omega])] [less than or equal to] 0, [E.sub.[omega]],[h(x, y, [omega])] = 0}.
This formulation deals with problems...
|
