DIRECT SEARCH METHODS ON PARALLEL MACHINES
DIRECT SEARCH METHODS ON PARALLEL MACHINES
复制标题
DOI：
10.1137/0801027
复制
发表时间：
1991-11-01
影响因子：
3.1
通讯作者：
Torczon, Virginia
中科院分区：
文献类型：
--
作者：
Dennis, J. E., Jr.;Torczon, Virginia
本文描述了一种构造易于在并行机上实现的无约束优化的无导数算法的方法。这种方法的一个特点是可以很容易地生成算法，以利用任意数量的处理器，并适应任何通信与函数评估的成本比。数值测试显示，在两个方面都有加速。同步的代价是最小的，随着处理器的增加，加速几乎是线性的，也就是说，在给定问题和搜索策略的情况下，执行时间的减少与处理器的增加成正比。然而，更令人鼓舞的是，为了利用额外的(或更强大的)处理器而设计的不同搜索策略，实际上可能会导致基本算法性能的显著改善。因此，针对许多处理器的搜索策略实际上可能会生成更好的算法，即使是在顺序实现时也是如此。关键的区别在于，额外的处理器并不是简单地用来增强固有的顺序算法的性能；它们被用来激励设计更雄心勃勃-和更有效的搜索策略。这里给出的算法得到了强大的收敛定理、对各种问题的有希望的计算结果以及直观地解释为多向线搜索方法的支持。
This paper describes an approach to constructing derivative-free algorithms for unconstrained optimization that are easy to implement on parallel machines. A special feature of this approach is the ease with which algorithms can be generated to take advantage of any number of processors and to adapt to any cost ratio of communication to function evaluation.Numerical tests show speed-ups on two fronts. The cost of synchronization being minimal, the speed-up is almost linear with the addition of more processors, i.e., given a problem and a search strategy, the decrease in execution time is proportional to the number of processors added. Even more encouraging, however, is that different search strategies, devised to take advantage of additional (or more powerful) processors, may actually lead to dramatic improvements in the performance of the basic algorithm. Thus search strategies intended for many processors actually may generate algorithms that are better even when implemented sequentially. The key difference is that the additional processors are not used simply to enhance the performance of an inherently sequential algorithm; they are used to spur the design of ever more ambitious-and effective-search strategies.The algorithms given here are supported by a strong convergence theorem, promising computational results on a variety of problems, and an intuitively appealing interpretation as multidirectional line search methods.