Skip to main content
main-content

Über dieses Buch

Stochastic Programming offers models and methods for decision problems wheresome of the data are uncertain. These models have features and structural properties which are preferably exploited by SP methods within the solution process. This work contributes to the methodology for two-stagemodels. In these models the objective function is given as an integral, whose integrand depends on a random vector, on its probability measure and on a decision. The main results of this work have been derived with the intention to ease these difficulties: After investigating duality relations for convex optimization problems with supply/demand and prices being treated as parameters, a stability criterion is stated and proves subdifferentiability of the value function. This criterion is employed for proving the existence of bilinear functions, which minorize/majorize the integrand. Additionally, these minorants/majorants support the integrand on generalized barycenters of simplicial faces of specially shaped polytopes and amount to an approach which is denoted barycentric approximation scheme.

Inhaltsverzeichnis

Frontmatter

0. Preliminaries

Abstract
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].
Karl Frauendorfer

Part I. Stochastic Two-Stage Problems

Abstract
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.
Karl Frauendorfer

Part II. Duality and Stability in Convex Optimization (Extended Results for the Saddle Case)

Abstract
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 (η00),exist. In other words we have to ensure dual solvability of the convex optimization problem — of the type (5.4) — with respect to (η,ξ) at (η00).
Karl Frauendorfer

Part III. Barycentric Approximation

Abstract
In chapter I we applied the concept of normal integrands that helped to ensure stochastic two-stage problems to be well-defined. With respect to these problems, we further outlined how to raise the saddle property for the integrand and how to model stochastic independence of random data. In this chapter we shall present a barycentric approximation technique that exploits these features (saddle property, stochastic independence) and assists in solving stochastic two-stage problems approximately.
Karl Frauendorfer

Part IV. An Illustrative Survey of Existing Approaches in Stochastic Two-Stage Programming

Abstract
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.
Karl Frauendorfer

Part V. BRAIN — BaRycentric Approximation for INtegrands (Implementation Issues)

Abstract
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.
Karl Frauendorfer

Part VI. Solving Stochastic Linear Two-Stage Problems (Numerical Results & Computational Experiences)

Abstract
In this chapter we discuss computational results achieved with applying the barycentric approximation scheme (sections 14,16,19,20) for solving stochastic linear two-stage problems with (C1)-(C5) of section 17 supposed to hold.
Karl Frauendorfer

Backmatter

Weitere Informationen