Parallel Computing for Large-Scale Optimization

大规模优化问题出现在各种重要的科学、工程和经济应用中，并且展示了允许通过具有高度并行性的算法解决的结构。研究将继续发展分解算法，以适合这些问题的分布式解决方案，并在各种并行架构上实施和测试这些方法，包括计算机科学系提供的多台计算机和多处理器，以及通过阿帕网在其他地方提供的多台计算机和多处理器。这种算法具有大粒度和低数据传输特性，非常适合并行架构。将特别强调网络优化问题，因为数学规划的大部分最困难的实际应用都属于这一类，并且因为这些问题也涵盖了广泛的数学类（从线性到非线性，从凸到非凸，从确定性到随机）。这些问题的并行算法的发展也需要调度和负载平衡技术的发展，这将有助于研究其他大规模科学计算领域的分布式技术。如果要有效地使用这些新的体系结构，分解问题以在多个并行处理器上同时运行是必不可少的。

Large-scale optimization problems arise in a great variety of important scientific, engineering, and economic applications, and exhibit structures that allow solution via algorithms that possess a high degree of parallelism. Research will be continued in the development of decomposition algorithms appropriate for the distributed solution of such problems and in the implementation and testing of these methods on a variety of parallel architectures including the multicomputers and multiprocessors available at the Computer Sciences Department and those available elsewhere via ARPANET. Such algorithms have the large granularity and low data transfer properties that are ideally suited to parallel architectures. Particular emphasis will be given to network optimization problems, since a large proportion of the most difficult real-world applications of mathematical programming fall into this category, and since such problems also cover a broad spectrum of mathematical classes (from linear to nonlinear, from convex to nonconvex, from deterministic to stochatic). The development of parallel algorithms for these problems will also require the development of scheduling and load-balancing techniques that will be useful in the study of distributed techniques for other areas of large- scale scientific computation. The decomposition of problems to run simultaneously on multiple parallel processors is essential if these new architectures are to be effectively used.