Volume 2006
http://edoc.hu-berlin.de/18452/363
2021-11-27T09:42:22ZOn Rates of Convergence for Stochastic Optimization Problems Under Non-I.I.D. Sampling
http://edoc.hu-berlin.de/18452/9024
On Rates of Convergence for Stochastic Optimization Problems Under Non-I.I.D. Sampling
Homem-de-Mello, Tito
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we discuss the issue of solving stochastic optimization problems bymeans of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. Thisis a well studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo is used); here, we study the case where thatassumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling schemecarry over to the optimization case, in the sense that convergence of approximatingoptimal solutions and optimal values to their true counterparts has the same rates asin pointwise estimation. Our motivation for the study arises from two types of sampling methods that havebeen widely used in the Statistics literature. One is Latin Hypercube Sampling (LHS),a stratiﬁed sampling method originally proposed in the seventies by McKay, Beckman,and Conover (1979). The other is the class of quasi-Monte Carlo (QMC) methods,which have become popular especially after the work of Niederreiter (1992). Theadvantage of such methods is that they typically yield pointwise estimators which notonly have lower variance than standard Monte Carlo but also possess better rates ofconvergence. Thus, it is important to study the use of these techniques in sampling-based optimization. The novelty of our work arises from the fact that, while therehas been some work on the use of variance reduction techniques and QMC methods instochastic optimization, none of the existing work — to the best of our knowledge — hasprovided a theoretical study on the effect of these techniques on rates of convergence forthe optimization problem. We present numerical results for some two-stage stochasticprograms from the literature to illustrate the discussed ideas.
2006-12-18T00:00:00ZConvergent Bounds for Stochastic Programs with Expected Value Constraints
http://edoc.hu-berlin.de/18452/9023
Convergent Bounds for Stochastic Programs with Expected Value Constraints
Kuhn, Daniel
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This article elaborates a bounding approximation scheme for convexmultistage stochastic programs (MSP) that constrain the conditional expectation ofsome decision-dependent random variables. Expected value constraints of this typeare useful for modelling a decision maker’s risk preferences, but they may also ariseas artefacts of stage-aggregation. It is shown that the gap between certain upper andlower bounds on the optimal objective value can be made smaller than any prescribedtolerance. Moreover, the solutions of some tractable approximate MSP give rise to apolicy which is feasible in the (untractable) original MSP, and this policy’s cost differsfrom the optimal cost at most by the difference between the bounds. The consideredproblem class comprises models with integrated chance constraints and conditionalvalue-at-risk constraints. No relatively complete recourse is assumed.
2006-12-18T00:00:00ZAirline Network Revenue Management by Multistage Stochastic Programming
http://edoc.hu-berlin.de/18452/9022
Airline Network Revenue Management by Multistage Stochastic Programming
Möller, Andris; Römisch, Werner; Weber, Klaus
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seatprotection levels for all itineraries, fare classes, point of sales of the airlinenetwork and all data collection points of the booking horizon such that theexpected revenue is maximized. While the passenger demand and cance-lation rate processes are the stochastic inputs of the model, the stochasticprotection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processesare approximated by a ﬁnite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursivescenario reduction scheme. Numerical results for a small hub-and-spoke network are reported.
2006-12-14T00:00:00ZStability of multistage stochastic programs incorporating polyhedral risk measures
http://edoc.hu-berlin.de/18452/9021
Stability of multistage stochastic programs incorporating polyhedral risk measures
Eichhorn, Andreas; Römisch, Werner
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We analyse stability aspects of linear multistage stochastic programs with polyhedral risk measures inthe objective. In particular, we consider sensitivity of the optimal value with respect perturbations ofthe underlying stochastic input process. An existing stability result for multistage stochastic programswith expectation objective is carried forward to the case of polyhedral risk-averse objectives. Beside$L_r$-distances these results also involve ﬁltration distances of the perturbations of the stochasticprocess. We discuss additional requirements for the polyhedral risk measures such that the problemdependent ﬁltration distances can be bounded by problem independent ones. Stability and suchbounds are the basis for scenario tree approximation techniques used in practical problem solving.
2006-12-14T00:00:00Z