Concurrent nomadic and bundle search: A class of parallel algorithms for local optimization

Abstract. We present a family of algorithms for local optimization that exploit the parallel architectures of contemporary computing systems to accomplish significant performance enhancements. This capability is important for demanding real time applications, as well as, for prob-lems with time–consuming objective functions. The proposed concurrent schemes namely nomadic and bundle search are based upon well es-tablished techniques such as quasi-Newton updates and line searches. The parallelization strategy consists of (a) distributed computation of an approximation to the Hessian matrix and (b) parallel deployment of line searches on different directions (bundles) and from different start-ing points (nomads). Preliminary results showed that the new parallel algorithms can solve problems in less iterations than their serial rivals