RIA: Parallel Algorithms for Constrained Nonlinear Global Optimization

这是超级计算机时间奖。目的是设计和实现新的算法，通过充分利用并行计算能力，在共享内存的Cray 2、Cray X-MP和Cray Y-MP超级计算机上有效地解决大规模、受限、非线性的全局优化问题。约束全局优化问题出现在许多重要的科学和技术领域，包括具有非凸目标函数的调度和分配问题，以及各种计算机辅助设计和计算几何应用。这类优化问题可能具有许多约束局部最优解，但问题的可接受解要求获得全局最优解或其良好的近似值。由于计算全局最优解的内在困难，本研究的重点将是设计和实现高效的算法，在并行计算机上在合理的时间内获得这些问题的近似解。通常，这些算法将找到近似解和该解的保证界，近似解的精度和界的紧密性取决于所执行的计算量。考虑到这种方法，主要关注的是这些算法的平均行为，而不是最坏的情况，对这种行为的性能分析将需要理论研究和广泛的计算测试相结合。

This is an award of supercomputer time. The object is to design and implement new algorithms which, by taking full advantage of parallel computing capabilities, will effectively solve large- scale, constrained, nonlinear global optimization problems on the shared-memory CRAY 2, CRAY X-MP, and CRAY Y-MP supercomputers. Constrained global optimization problems arise in many important areas of science and technology and include scheduling and allocation problems with nonconvex objective functions and a variety of computer-aided design and computational geometry applications. These kinds of optimization problems may possess many constrained local optima, but an acceptable solution to the problem requires that a global optimum, or a good approximation to it, be obtained. Because of the inherent difficulty of computing the global optimum, the emphasis of this research will be on the design and implementation of efficient algorithms which obtain an approximate solution to these problems on parallel computers in a reasonable amount of time. Typically these algorithms will find both an approximate solution and guaranteed bounds on this solution, with the accuracy of the approximate solution and the tightness of the bounds depending on the amount of computation performed. In view of this approach, primary interest is placed on the average, rather than worst case, behavior of these algorithms, and the performance analysis of this behavior will require a combination of both theoretical investigation and extensive computational testing.