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.