Algorithms for Large Scale Stochastic Optimization

大规模随机优化算法

• 批准号: 9102660
• 负责人: John Mulvey
• 金额: $ 19.94万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-07-15 至 1996-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9102660&HistoricalAwards=false
• 关键词: Algorithms; Large; Scale; Stochastic; Optimization

This project continues previous work on nonlinear and stochastic networks. The basic research involves the design of efficient algorithms for large-scale network optimization problems. Attention will be paid to the inclusion of uncertainty within the model - stochastic networks - and to nonlinearities in the objective function. Many problems in engineering and management can be represented as a network in which some (or all) of the parameters are stochastic. Examples include: air-traffic control, hydroelectric power scheduling, financial investment strategies, transportation planning, productions/distribution, and personnel planning systems. Adding uncertainty to an optimization model greatly complicates the search for efficient algorithms. This research will focus on a new decomposition method, called diagonal quadratic approximation (DQA), that combines a penalty and an interior-point barrier approach. Initial results indicate that the DQA method is competitive with the leading stochastic programming algorithm - progressive hedging. Both methods are amenable to parallel implementation. The DQA method can be designed for a massively parallel computer. Thus, DQA applies to the multi-stage stochastic program, whereby large numbers of scenarios are required. The research will consider alternative versions of DQA and will study the theoretical aspects of convergence. Extensive computational tests will be made on a variety of serial and parallel computers, including a massively parallel SIMD machine. The research promises to make substantial progress in the handling of stochastic programming problems with a very large number of scenarios. The significance of the project is indicated by the wide range of applications that can be solved as network optimization problems under uncertainty.

本项目延续了以往在非线性和随机 网络. 基础研究涉及设计高效的 大规模网络优化问题的算法。 关注 将不确定性包含在模型中- 随机网络-以及目标函数中的非线性。 工程和管理中的许多问题都可以表示为 网络中的一些（或所有）参数是随机的。 例如：空中交通管制、水力发电 调度、财务投资策略、交通规划、 生产/分销和人员规划系统。 添加 优化模型的不确定性极大地使搜索复杂化 用于高效算法。 这项研究将集中在一个新的 分解方法，称为对角二次逼近（DQA）， 结合了点球和内点障碍法。 初步结果表明，DQA方法是有竞争力的， 领先的随机规划算法-渐进式套期保值。 两 方法适合于并行实现。 DQA方法可以 是为大规模并行计算机设计的。 因此，DQA适用于 多阶段随机规划，其中大量的情况下， are required. 该研究将考虑DQA的替代版本 并会研究衔接的理论问题。 广泛 计算测试将在各种串行和并行 计算机，包括大规模并行SIMD机器。 研究 承诺在处理随机性方面取得实质性进展 大量场景的编程问题。 的 项目的重要性体现在广泛的 可以作为网络优化问题解决的应用 在不确定性下。