Stochastic Programming by Monte Carlo Simulation Methods

通过蒙特卡罗模拟方法进行随机规划

• 批准号: 0073770
• 负责人: Alexander Shapiro
• 金额: $ 9.49万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0073770&HistoricalAwards=false
• 关键词: Stochastic; Programming; Monte; Carlo; Simulation

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. [phone]; Fax: [phone],E-mail : [e-mail]://www.isye.gatech.edu/~ashapiroISyE, Georgia Tech, Atlanta, GA 30332-0205

许多随机规划问题可以表述为期望值函数的最优化问题。通常，相应的期望值函数不能精确地计算出来，而应该用蒙特卡罗方法来近似。事实上，在许多有趣的例子中，蒙特卡罗模拟是估计期望值函数的唯一合理方法。结果表明，如果底层概率分布是离散的，逼近问题是分段线性和凸的，那么随着概率以指数速度逼近1，随着样本量的增加，蒙特卡罗逼近问题的最优解提供了期望值问题的精确最优解。这就为下面的方法提供了理论依据，以求得这类问题的数值解。构造并解决一个基于相对小样本的蒙特卡罗近似问题。重复此过程几次并验证计算出的解，直到满足停止准则。这个项目的目标就是开发这种方法。该方法非常适合并行计算，初步实验结果良好。现实世界系统的优化几乎总是涉及随机性，随机性可以有各种概念形式，如不确定性、信息缺乏、数据的自然可变性等。例如，当对生产产品的需求不确定时，人们可能会考虑优化制造过程。事实证明，无论是在概念上还是在数值上，解决涉及随机性的随机优化问题都比解决确定性问题困难得多。然而，发展一种处理随机问题的方法显然是实际需要，近年来这是一个非常活跃的科学研究领域。这个建议的目的是发展数值技术来解决一类特殊的随机问题。如果成功，它将使更大问题的数值解成为可能，从而可能导致更广泛的应用。亚历山大·夏皮罗，电话。404 - 8946544;传真：404-8942301，电子邮件：[e-mail]://www.isye.gatech.edu/~ashapiroISyE，乔治亚理工学院，亚特兰大，佐治亚州30332-0205