Algorithms for Large Scale Stochastic Optimization

这个项目延续了之前关于非线性和随机网络的研究。基础研究涉及大规模网络优化问题的高效算法设计。我们将注意到模型中的不确定性——随机网络——以及目标函数中的非线性。工程和管理中的许多问题可以表示为一个网络，其中一些（或全部）参数是随机的。例子包括：空中交通管制、水力发电调度、金融投资策略、运输规划、生产/分销和人事规划系统。在优化模型中加入不确定性会使寻找高效算法变得非常复杂。本研究将集中于一种新的分解方法，称为对角二次逼近（DQA），它结合了惩罚和内点屏障方法。初步结果表明，DQA方法与目前领先的随机规划算法渐进式套期保值具有一定的竞争力。这两种方法都可以并行实现。DQA方法可以设计用于大规模并行计算机。因此，DQA适用于需要大量场景的多阶段随机规划。该研究将考虑DQA的替代版本，并将研究收敛的理论方面。将在各种串行和并行计算机上进行广泛的计算测试，包括大规模并行SIMD机器。该研究有望在处理具有大量场景的随机规划问题方面取得实质性进展。该方案具有广泛的应用前景，可作为不确定条件下的网络优化问题加以解决。

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.