Patty Hough, Tammy Kolda, and Virginia Torczon
We introduce a new asynchronous parallel pattern search (APPS). The target platforms for APPS are the loosely-coupled parallel systems now widely available. We exploit the algorithmic characteristics of pattern search to design variants that dynamically initiate actions solely in response to messages, rather than routinely cycling through a fixed set of steps. This gives a versatile concurrent strategy that allows us to effectively balance the computational load across all available processors. Further, it allows us to incorporate a high degree of fault tolerance with almost no additional overhead. We present the new features of the associated convergence analysis and demonstrate the effectiveness of an implementation of APPS applied to both standard test problems as well as some engineering optimization problems.