A VIEW OF THE LIMITATIONS, OPPORTUNITIES, AND CHALLENGES IN PARALLEL NONLINEAR OPTIMIZATION

The availability and power of parallel and distributed computers is ha ving a significant impact on how expensive problems are solved in all areas of numerical computation, and is likely to have an even larger i mpact in the future. This paper presents a view of how the considerati on of parallelism is affecting, and is likely to affect, one important field within numerical computation, the field of nonlinear optimizati on. It does not attempt to survey the research that has been done in p arallel nonlinear optimization. Rather it presents a set of examples, drawn mainly from our own research, that illustrate many of the limita tions, opportunities, and challenges inherent in incorporating paralle lism into the field of nonlinear optimization. These examples include parallel methods for unconstrained optimization problems with a small to moderate number of variables, parallel methods for large block bord ered systems of nonlinear equations, and parallel methods for small-sc ale and large-scale global optimization problems. Our overall conclusi ons are mixed. For most generic optimization problems with a small to moderate number of variables, the consideration of parallelism does no t appear to be leading to major algorithmic innovations. For many clas ses of large-scale problems, however, the consideration of parallelism appears to be creating opportunities for the development of interesti ng new methods that may be advantageous on parallel and sometimes even on sequential computers. In addition, a number of large-scale paralle l optimization algorithms exhibit irregular, coarse-grain structure, w hich leads to interesting computer science challenges in areas such as dynamic scheduling and load-balancing.