Stochastic Two-Stage Programming

In this part we state definitions (and notations) and conventions having been used throughout this work.

i) DEFINITIONS and NOTATIONS

We start with recalling known definitions and characterizations within linear topological vector spaces, (stochastic) (convex) analysis, measure and probability theory. For that which is outlined below, we mainly used Feller 1966 [44], Billingsley 1968 [9], Rockafellar 1970 [118] and 1976 [121], Halmos 1974 [55], Kelley and Namioka 1976 [80], Ekeland and Temam 1976 [39], Castaing and Valadier 1976 [20], Brøndsted 1983 [18], Prékopa 1980 [107], Rudin 1980 [131], Robinson 1987 [111], Wets 1989 [144] and Bauer 1990 [3].

Optimization problems, in particular mathematical programs, are characterized by a set of (in particular finite dimensional) alternatives (decisions) and an objective. Decision makers have to select out of this set that alternative (decision), best satisfying the underlying objective. If all data are known prior to the decision process we speak of deterministic optimization (programming); if part of the data remain unknown and available only in a certain probabilistic sense we speak of stochastic optimization (programming). We retain on modeling uncertain data by means of assigning probability distributions to these data. Hence, we take as a premise that a probability distribution is given.

Due to the first chapter we realize that convex programs of the type (5.4) with random parameters (η,ξ) in the objective and in the right-hand side play an essential role in stochastic two-stage programs. We are aware of the fact that we have to integrate (at least approximately) the optimal value function (recourse function) of (5.4), given — for a fixed first-stage decision x — only implicitly by the infimum of (5.4). Although the optimal value function changes with x, we take into account that it remains a saddle function. This fact motivates to derive suitable approximates for the optimal value function, that are computable and allow conclusions about the goodness of the first-stage decision x. Such approximates will be derived in chapter III. At this point it is only of importance to stress that the existence of these approximates essentially depend on the existence of subgradients of the optimal value function at distinguished points. Hence, at first, we are confronted with investigating under which assumptions subgradients for the optimal value function at a certain distinguished point, say (η⁰,ξ⁰),exist. In other words we have to ensure dual solvability of the convex optimization problem — of the type (5.4) — with respect to (η,ξ) at (η⁰,ξ⁰).

As mentioned in chapter I the formulation of stochastic programming problems goes back to the mid 50s (Dantzig, Beale, Tintner). Since then a lot of research activities have resulted in developments of approaches for solving these problems. We intend next to focus on some of existing approaches and outline their main characteristica. The motivation to do this lies in the variety of stochastic two-stage programming problems entailing different and challenging features that have been exploited within the last decades. Some of the approaches discussed below have already been treated in Ermoliev and Wets 1988 [42], and even much more detailed therein than we will do here; however, the achieved progress within stochastic programming in the last five years have raised new ideas.

In this chapter we present BRAIN, an implementation (written in Fortran77) of the BaRycentric Approximation for INtegrands. In chapter III we mainly focused on understanding and properties of the approximation. Below, we concentrate to ease its usage and to illustrate the effort of the computational activities within one iteration of the algorithm stated in section 20. Moreover, that which follows gives also some insight in how to exploit the structural properties of a x-simplex.