Parallel Asynchronous Global Search and the Nested Optimization Scheme

Journal of Computational Analysis and Applications - Tập 3 - Trang 123-145 - 2001
Yaroslav D. Sergeyev1, Vladimir A. Grishagin2
1ISI-CNR, c/o DEIS, University of Calabria, Rende (CS), Italy
2Software Department, University of Nizhni Novgorod, Nizhni Novgorod, Russia

Tóm tắt

In this paper, a parallel asynchronous information algorithm for solving multidimensional Lipschitz global optimization problems, where times for evaluating the objective function can be different from point to point, is proposed. This method uses the nested optimization scheme and a new parallel asynchronous global optimization method for solving core univariate subproblems generated by the nested scheme. The properties of the scheme related to parallel computations are investigated. Global convergence conditions for the new method and theoretical conditions of speed up, which can be reached by using asynchronous parallelization in comparison with the pure sequential case, are established. Numerical experiments comparing sequential, synchronous, and asynchronous algorithms are also reported.

Tài liệu tham khảo

F. Aluffi-Pentini, V. Parisi, and F. Zirilli, Global optimization and stochastic differential equations, J. Optimization Theory Appl. 47, 1–16 (1985).

F. Archetti and F. Schoen, A survey on the global optimization problems: general theory and computational approaches, Ann. Operations Res. 1, 87–110 (1984).

W. Baritompa, Accelerations for a variety of global optimization methods, J. Global Optimization 4, 37–45 (1994).

M. Bertocchi, A parallel algorithm for global optimization, Optimization 62, 379–386 (1990).

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, 1989.

I. M. Bomze, T. Csendes, R. Horst, and P. M. Pardalos, eds., Developments in Global Optimization, Kluwer Academic Publ., Dordrecht, 1997.

C. R. Carr and C. W. Howe, Quantitative Decision Procedures in Management and Economics. Deterministic Theory and Applications, McGraw Hill, New York, 1964.

L. C. W. Dixon and G. P. Szego, eds., Towards Global Optimization, Vol. 2. North-Holland, Amsterdam, 1978.

C. A. Floudas and P. M. Pardalos, eds., State of the Art in Global Optimization, Kluwer Academic Publ., Dordrecht, 1996.

V. P. Gergel and Ya. D. Sergeyev, Sequential and parallel global optimization algorithms using derivatives, Computers Math. Appl., 37, 163–189 (1999).

V. A. Grishagin, On convergence conditions for a class of global search algorithms, Proc. 3rd All-Union Seminar Numerical Methods Nonlinear Programming, Kharkov, 82–84 (1979) (in Russ.).

V. A. Grishagin, Ya. D. Sergeyev, and R. G. Strongin, Parallel characteristic algorithms for solving problems of global optimization, J. Global Optimization 10, 185–206 (1997).

P. Hansen and B. Jaumard, Lipschitz optimization, in Handbook of Global Optimization, R. Horst and P. M. Pardalos, eds., Kluwer Academic Publ., Dordrecht, 1995.

E. M. T. Hendrix, Ph.D. thesis, Wageningen, 1998.

R. Horst and P. M. Pardalos, eds., Handbook of Global Optimization, Kluwer Academic Publ., Dordrecht, 1995.

R. Horst and H. Tuy, Global Optimization Deterministic Approaches, 3rd ed., Springer Verlag, Berlin, 1996.

R. B. Kearfott, Rigorous Global Search: Continuous Problems, Kluwer Academic Publ., Dordrecht, 1996.

S. Lucidi and M. Piccioni, Random tunneling by means of acceptance-rejection sampling for global optimization, J. Optimization Theory Appl. 62, 255–277 (1989).

A. Migdalas, P. M. Pardalos, and S. Støroy, eds., Parallel Computing in Optimization, Kluwer Academic Publ., Dordrecht, 1996.

R. H. Mladineo, An algorithm for finding the global maximum of a multimodal, multivariate function, Math. Programming 34, 188–200 (1986).

P. M. Pardalos, Parallel search algorithms in global optimization, Applied Math. Computation 29, 219–229 (1989).

P. M. Pardalos, A. T. Phillips, and J. B. Rosen, Topics in Parallel Computing in Mathematical Programming, Science Press, 1992.

P. M. Pardalos and J. B. Rosen, eds., Computational methods in global optimization, Ann. Operations Res. 25 (1990).

S. A. Pijavskii, An algorithm for finding the absolute extremum of a function, USSR Comput. Maths Math. Phys. 12, 57–67 (1972).

J. Pintér, Convergence qualification of adaptive partition algorithms in global optimization, Math. Programming 56, 343–360 (1992).

J. Pintér, Global Optimization in Action, Kluwer Academic Publ., Dordrecht, 1996.

H. Ratschek and J. Rokne, New Computer Methods for Global Optimization, Ellis Horwood, Chichester, 1988.

A. H. G. Rinnooy Kan and G. H. Timmer, Global optimization, Optimization (G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, eds.), North-Holland, Amsterdam, 1989.

Ya. D. Sergeyev, An information global optimization algorithm with local tuning, SIAM J. Optimization 5, 615–631 (1995).

Ya. D. Sergeyev, An information global optimization algorithm with local tuning, J. Global Optimization 15, 157–167 (1999).

Ya. D. Sergeyev and V. A. Grishagin, A parallel algorithm for finding the global minimum of univariate functions, J. Optimization Theory Appl. 80, 513–536 (1994a).

Ya. D. Sergeyev and V. A. Grishagin, Sequential and parallel algorithms for global optimization, Optimization Methods Software 3, 111–124 (1994b).

Ya. D. Sergeyev and R. G. Strongin, A global minimization algorithm with parallel iterations, USSR Comput. Maths. Math. Phys. 29, 7–15 (1990).

R. G. Strongin, Numerical Methods on Multiextremal Problems, Nauka, Moscow, 1978 (in Russ.).

R. G. Strongin, Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves, J. Global Optimization 2, 357–378 (1992).

R. G. Strongin and Ya. D. Sergeyev, Global multidimensional optimization on parallel computer, Parallel Comput. 18, 1259–1273 (1992).

A Törn and A. Žilinskas, Global Optimization, Lecture Notes in Computer Science, Springer Verlag, New York, 1989, p. 350.

G. R. Wood, The bisection method in higher dimensions, Math. Programming 55, 319–337 (1992).

Z. B. Zabinsky and R. L. Smith, Pure adaptive search in global optimization, Math. Programming 53, 323–338 (1992).

A. A. Zhigljavsky, Theory of Global Random Search, Kluwer Academic Publ., Dordrecht, 1991.

Thông tin
Thông tin xuất bản

Journal of Computational Analysis and Applications

Tập 3

123-145

Thông tin tác giả