Stochastic Programming by Monte Carlo Simulation Methods

点击翻译按钮获取中文摘要

Many stochastic programming problems can be formulated asproblems of optimization of an expected value function. Quiteoften the corresponding expected value function cannot be computedexactly and should be approximated, say by Monte Carlo methods.In fact, in many interesting examples, Monte Carlo simulation isthe only reasonable way of estimating the expectedvalue function. It turns out that if the underline probabilitydistribution is discrete and the approximating problems arepiecewise linear and convex, then with probabilityapproaching one exponentially fast, with increase of the samplesize, an optimal solution of the Monte Carlo approximation problemprovides an exact optimal solution of the expectedvalue problem. This gives a theoretical justification forthe following approach to a numerical solution of such problems.Construct and solve a Monte Carlo approximation problem based on arelatively small sample. Repeat this procedure several times and validatecalculated solutions until a stopping criterion is satisfied. The goal of thisproject is to develop this method. The method is ideally suited forparallel computations and some preliminary experiments showed goodresults.Optimization of real world systems almost always involves randomness whichcan come invarious conceptual forms such as uncertainty, lack of information, naturalvariability of the data, etc. One may think, for example, about optimizinga manufacturing process when the demand for produced goods is uncertain. Itturns out that solving stochastic optimization problems involvingrandomness is much more difficult than solving deterministic problems, bothconceptually and numerically. However, there is obvious practical need fordeveloping a methodology for dealing with stochastic problems and in recentyears this was a very active area of scientific research. This proposal isaimed at developing numerical techniques for solving a particular class ofstochastic problems. If successful, it will allow numerical solutions ofconsiderably larger problems, which in turn may result in bigger variety ofapplications.Alexander Shapiro ,Tel. 404-8946544; Fax: 404-8942301,E-mail : ashapiro@isye.gatech.eduhttp://www.isye.gatech.edu/~ashapiroISyE, Georgia Tech, Atlanta, GA 30332-0205