Many-stage Stochastic Programming

多阶段随机规划

• 批准号: 0204206
• 负责人: Lisa Korf
• 金额: $ 14.97万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-01 至 2004-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0204206&HistoricalAwards=false
• 关键词: Many; stage; Stochastic; Programming

0204206KorfThe proposed project addresses modeling, duality, approximation, implementation and application of stochastic programming problems with many time stages. The typical so-called multi-stage stochastic program tends to be modeled as an extension of a two-stage problem (often referred to as a stochastic program with recourse). This misses some important features of a problem with many time stages, including a description of the dynamics inherent to the problem, the structure of information, and the degree to which one may respond to that information at a given time stage. A typical problem from mathematical finance will be framed in a many-stage stochastic programming setting, allowing for a description of the dynamics. The classical pricing results of mathematical finance and extensions to more complicated problems will be obtained using the new model. This model will be generalized to be applicable to a much broader range of many-stage stochastic optimization problems, highlighting duality results and their significance. In conjunction with this will be an investigation into problems that could be modeled in a continuous time framework, and problems with infinitely many time stages. New stochastic programming models, and approximation techniques using the tools of variational analysis, will be developed for these respective problems. Finally, an investigation into the structure of many-stage problems that include a description of system dynamics will be undertaken, leading ultimately to the development and implementation of algorithms for solving them.Decision making under uncertainty and the theory and techniques of mathematical programming merged in the 1950's to create the field now known as stochastic programming. A stochastic program is a mathematical program (e.g. a linear program) that includes in its formulation a probability distribution to describe uncertain parameters. Research consists largely of understanding problem structure, deriving duality results and optimality conditions, developing approximation techniques, and exploiting the structure and theory in the development of solution schemes. The field's development began with a two-stage recourse model, where the cost of a decision made now (e.g. production) is affected by an uncertain outcome in the future (e.g. demand), and the possibility of taking recourse action once the future is revealed (e.g. overtime). A typical problem is to determine the present decision that minimizes expected cost. While much knowledge has been gained from the investigation of two-stage models, a limited view of many-stage stochastic programming has resulted in which multistage problems are considered as simple extensions of the two-stage case. This fails to address the inherently dynamic nature of problems with many time stages. Additionally, two-stage applications tend to come largely from areas such as production and manufacturing, whereas the bulk of problems with many time stages arise from financial, economic, and environmental planning applications and other problems where dynamics are driving a system. Thus, much of the new many-stage theory should be geared toward these sorts of applications. The proposed research will explore the additional dynamic structures, theory (duality, approximation), and questions regarding implementation, of stochastic optimization problems involving many (possibly even infinitely many, or a continuum of) stages. This will be motivated primarily by financial applications.

[0204206]本课题研究多时间阶段随机规划问题的建模、对偶性、近似、实现和应用。典型的所谓多阶段随机规划往往被建模为两阶段问题的扩展（通常称为带追索权的随机规划）。这忽略了具有多个时间阶段的问题的一些重要特征，包括对问题固有的动态描述、信息结构以及在给定时间阶段对该信息的响应程度。一个典型的数学金融问题将被框定在一个多阶段的随机规划设置中，允许对动力学进行描述。利用新模型将得到数学金融学的经典定价结果，并将其推广到更复杂的问题。该模型将被推广到更广泛的多阶段随机优化问题，突出了对偶结果及其意义。与此相结合的将是对可以在连续时间框架中建模的问题的研究，以及具有无限多个时间阶段的问题。新的随机规划模型，以及使用变分分析工具的近似技术，将针对这些各自的问题而发展。最后，对包括系统动力学描述在内的多阶段问题的结构进行调查，最终导致解决这些问题的算法的开发和实现。不确定性下的决策与数学规划的理论和技术在20世纪50年代合并，形成了现在被称为随机规划的领域。随机程序是一种数学程序（如线性程序），其公式中包含描述不确定参数的概率分布。研究主要包括理解问题结构，推导对偶结果和最优性条件，发展近似技术，以及在求解方案的开发中利用结构和理论。该油田的开发始于一个两阶段的追索权模型，即现在做出的决策（如生产）的成本受到未来不确定结果（如需求）的影响，以及未来发现后采取追索权行动的可能性（如加班）。一个典型的问题是确定使预期成本最小化的当前决策。虽然从两阶段模型的研究中获得了许多知识，但对多阶段随机规划的有限观点导致将多阶段问题视为两阶段情况的简单扩展。这无法解决具有多个时间阶段的问题的内在动态性质。此外，两阶段应用程序往往主要来自生产和制造等领域，而许多时间阶段的问题来自金融、经济和环境规划应用程序以及其他动态驱动系统的问题。因此，许多新的多阶段理论应该面向这类应用。提出的研究将探索额外的动态结构，理论（对偶性，近似），以及有关实施的问题，随机优化问题涉及许多（甚至可能无限多，或连续体）阶段。这将主要受到金融应用的推动。