Parallel search algorithms in global optimization

摘要

A number of parallel search algorithms are proposed and analyzed for constrained global optimization problems. Algorithms for such problems involve a large number of iterations and function evaluations and a large number of independent local searches. Concurrent function evaluations are well suited for multiprocessing. Similarly, concurrent iterations used for local minimizers can be implemented using multiprocessors. In this paper we consider the global minimization of nonconvex quadratic problems. The proposed algorithms are based on the used of linear programming and local search techniques. Specifically we solve multiple-cost-row linear programs and closely related nonlinear programs (local searches). In this approach, because the constraint set is unchanged and only the objective function changes, the subproblems can be solved independently of each other. Multitasking and vectorization techniques can be used effectively to exploit the parallelism inherent in these problems.