J.A. Martinez, L.G. Casado and I. Garcia
Computer Architecture & Electronics Dpt.
University of Almeria, Spain
email: amartin@ace.ual.es
In [1, 2] two algorithms for solving the global optimization problem, for the one-dimensional and multidimensional cases, respectively, are described. Both algorithms are based on an efficient use of interval analysis and gradient information. These algorithms take advantage of all available information to estimate better bounding, selection and elimination rules. Experiments using a wide set of test functions showed that they work faster than traditional interval analysis global optimization methods. The work we intend to show at this conference deals with a parallel implementation of the sequential algorithm to solve the multidimensional case [2]. Our interest mainly consists of the minimization of the execution time needed to solve very difficult problems. In [3, 4, 5, 6] parallel algorithms for solving the global optimization problem have been presented. In this work, we proposed a new strategy for interval parallel global optimization which takes advantage of the Charm++ characteristics [7]. Charm++ apart from traditional programming models such as message passing and shared memory programming, offers the message-driven execution model. Therefore, computations in Charm++ are triggered based on the arrival of associated messages. The asynchronous message passing is the basic interprocess communication mechanism in Charm++. However, Charm++ also permits wide variations on this mechanism to make it easy for the programmer to write programs. These possible variations include prioritization, conditional message packing and unpacking, quiescence detection, and dynamic load balancing. Preliminary results have shown that this parallel approach obtains a super speed-up for hard to solve problems and, what is more valuable, the algorithm is able to find solutions for problems which were unsolvable by the sequential algorithm in a reasonable time.
References:
[1] Casado, L.G., Martinez, J.A., Garcia I. and Sergeyev, Ya. D.: 2002, New interval analysis support functions using gradient information in a global minimization algorithm. Journal of Global Optimization. v. 22, n. 2, pp 359-376. kluwer Academic Publishers.
[2] Martinez, J.A., Casado, L.G., Garcia I., and B. Toth: 2003, AMIGO: Advanced Multidimensional Interval analysis Global Optimization algorithm. To appear in Nonconvex Optimization and Its Applications. kluwer Academic Publishers.
[3] Berner, S.: 1996, Parallel Methods for Verified Global Optimization: Practice and Theory. Journal of Global Optimization. v. 9, n. 1, pp. 122. kluwer Academic Publishers.
[4] Dixon, L.C.W., Jha, M.: 1993, Parallel Algorithms for Global Optimization. Journal of Optimization Theory and Applications. v. 79, n. 2, pp.385-395. kluwer Academic Publishers.
[5] Wiethoff, A.: 1997, Verifizierte Globale Optimierung auf Parallelrechnern. PhD Dissertation, University of Karlsruhe, Karlsruhe.
[6] Suiunbek, I.: 2002, A New Parallel Method for Verified Global Optimization. PhD Dissertation, University of Wuppertal, Wuppertal.
[7] The Charm++ Programming Language Manual. Parallel Programming Laboratory, University of Illinois.