Global Optimization (Slides)

Törn, Aimo A.

The task of global optimization is to find a solution in the solution set for which the objective function obtaines its smallest value, the global minimum. Global optimization thus aims at determining not just "a local minimum" but "the smallest local minimum" with respect to the solution set. Below is a description of the research on global optimization carried out at Äbo Akademi University.

1. Background


Extending the class of functions to include multimodal functions makes the global optimization problem unsolvable in general. In order to be solvable some smoothness condition on the function in addition to continuity must be known.

The existence of several local minima and unsolvability in general are important characteristics of global optimization. Unsolvability here means that a solution cannot be guaranteed in a finite number of steps.
There are two ways to deal with the unsolvability problem. First, "a priori" conditions on f and A are posed which turns the problem into a solvable one or at least makes it possible to tell for sure that a solution has been found. This restricts the function class that is considered.
The second approach which allows a larger class of objective functions to be considered is to give up the solvability requirement and only try to obtain an estimate of the global minimum. In this "probabilistic" approach it would be desirable also to obtain some results on the goodness of an obtained estimate. Some of the solvable problems may fall in this class because the number of steps required for a guaranteed solution might be prohibitively large.

When relaxing the requirement on solvability it seems rational to require that the probability that a solution is obtained approaches 1 if the procedure is allowed to continue forever.
An obvious probabilistic global search procedure is to use a local algorithm starting from several points distributed over the whole optimization region. This procedure is named "Multistart". Multistart is certainly one of the earliest global procedures used. It has even been used in local optimization for increasing the confidence in the obtained solution. One drawback of Multistart is that when many starting points are used the same minimum will eventually be determined several times. In order to improve the efficiency of Multistart this should be avoided.

Clustering methods are used to avoid this repeated determination of local minima. This is realized in three steps which may be iteratively used. The three steps are:

If the procedure employing these steps is successful then starting a single local optimization from each cluster would determine the local minima and thus also the global minimum. The advantage in using this approach is that the work spared by computing each minimum just once can be spent on computations in (a) and (b), which will increase the probability that the global minimum will be found.



2 Early papers


The paper [Becker and Lago 1970] is according to our knowledge the first where a clustering technique is used to aid in global optimization. It was presented at the "Eight Allerton Conference on Circuits and Systems Theory" and published in the Proceedings of this conference. It may not therefore be surprising that the paper remained unknown to the community of global optimization for almost ten years.

At the same time as Becker and Lago, Törn was working on global optimization during his stay at the Computer Science Department of Stanford University in 1968-1969. The first results were presented at a congress in 1972 [Törn 1973]. This was followed by several publications [Törn 1974 (diss.), 1976, 1977a, 1977b, 1978, 1979, 1980 and 1983]. The papers [Törn 1980, 1983] are applications of the global optimization algorithm to vector optimization (MCDM).



3. Early followers


Based on papers of Törn, especially [Törn 1978] a large number of researchers have contributed to the litterature on clustering methods for global optimization.
Spircu's starting point was the papers [Törn 1977a,b], see [Spircu 1978].
Gomulka [Gomulka 1978] installed Törn's package for global optimization at "The Numerical Optimization Centre" at Hatfield Polytechnic. Experiments were also made with a version using a different local optimizer than that of Törn.
In their paper [Boender et al 1982] describe their method as a stochastic method involving a combination of sampling, clustering and local search, terminating with a range of confidence intervals on the value of the global minimum.
The algorithm of Boender et al has been modified by Timmer [Timmer 1984]. Timmer considered several clustering methods. Based on experiments a method, "multi level single linkage", was deemed most accurate.
Csendes' algorithms [Csendes 1985] are implementations of the algorithm of [Boender et al 1982]. The local algorithms used are a random direction, linear search algorithm also used by Törn, and a quasi--Newton algorithm not using the derivative of the function. The results show the dependence of the result on the auxiliary local algorithm used.


4 Further research

1984-1990

The books published by Dixon and Szegö [Dixon and Szegö 1975, 1978] are contributed works. No book covering the whole field existed and as such a book would be of great help for researchers already in the field or entering the field. Dr. Antanas /v Zilinskas from Lithuanian Akademy of Science in Vilnius and I decided to try to write such a book. As a first result of this effort an overview of clustering methods was presented at the Second IFAC Syposium on Stochastic Control, Vilnius, May 1986 [Törn 1986]. The book [Törn and Zilinskas (1989)] was published by Springer Verlag.
At the Second workshop on Global Optimization in Sopron in 1990 a new "clustering" approach "Topographical Global Optimization (TGO)" was presented. In this approach the topography of the function made up by the sampled points is analyzed without any preceeding local steps in order to directly identify the best point in each basin around local minima. The first work on TGO was the Master Thesis of C. Juselius [Juselius 1989].

1991-1995

Sami Viitanen continued the work on TGO in his Master Thesis [Viitanen 1991]. The results on TGO were published at the first Princeton Conference on Global Optimization in 1991 [Törn and Viitanen (1992)]. TGO with presampled points for a very uniform covering of A was published in JOGO [Törn and Viitanen (1994)].

Viitanen obtained his licentiate degree (PhD) in 1994. His Thesis was mainly on Parallel TGO including a paper on TGO for constrained problems [Törn and Viitanen 1993] but included also Parallel Simulated Annealing (MTASS, not published) and parallelization of the Multidimensional Bisection algorithm of Wood [Wood (1991)]. In MTASS the main idea was to explore multiple search directions in parallel and choose the "best" based on successes. The strategy of accepting new trial points (i.e. the temperature) was allowed to vary in an adaptive way based on the heating cycles idea of Bonnemoy and Hamma [Bonnemoy and Hamma (1991)]. Prof. B, Baritompa from Uni. of Canterbury, New Zealand was a visitor here in June 1992 and Dr. B. Hamma from Uni. of Toulose, France in July, August 1992.

Montaz Ali joined the research group as a post doc in 1995. He received his Ph.D. degree in Global Optimization from Loughborough University of Technology in August 1994. The PhD thesis is concerned with research into the developments and modifications of stochastic algorithms (for continuous variables) and their successful applications to real life problems. Two new Controlled Random Search (CRS) algorithm a are proposed, the CRS4 and CRS5 algorithms, which give significant improvements over Price's [1987] CRS3 algorithm, both in terms of cpu time and the number of function evaluations. In addition, he has developed a hybridge Multistate (MS) algorithm, the Topographical Multilevel Single Linkage (TMSL) algorithm, which combines the Multilevel Single Linkage (MSL) algorithm of Timmer [1984] with the Topographical Global Optimization Algorithm (TGO) of Professor Aimo Torn. He also proposed a new aspiration based simulated annealing algorithm (ASA) which enhances the performance of the simulated annealing algorithm (SA) of Dekkers Aarts [1991] by incorporating an aspiration criterion. The theoretical convergence proof is also established and stated in the thesis. A substantial part of the thesis deals with the numerical investigation of eight different global optimization algorithms on some very difficult practical problems. These are the true global optimization problems arose in field of Control, Physical modelling and other areas, such as Statistics, Civil, Mechanical and Chemical Engineering. The global optimization codes are currently in use within the Molecular Dynamic (MD) simulation group in the Department of mathematical Sciences at Loughborough University of Technology, UK.
During his research he has programmed several semi-empirical, many-body potential functions of Tersoff [1988] to describe the interactions between atoms. These potential functions describe many-body bonded interaction between atoms. The global optimization algorithms have been successfully applied to these potentials and the minimum energy configuration of clusters of atoms predicted by these potentials are obtained (see, Ali and Smith [1993]). He has also successfully tackled the global optimization problem involving the control of vehicle suspension systems.

In 1995 a research project "Efficient Multistart Techniques for Global Optimization" was started with Prof. Juri Evtushenko, Computing Center of the Russian Academy of Sciences and Dr. S.K. Zavriev, Moscow State University (Funding by Academy of Finland). A research seminar with eight presentations was organized at the department 28-30.11.95 as part of this project. Participants were: J. Evtushenko, V. Zadan, S. Zavriev and Y. Perunova from the Russian side and A. Törn, M. Ali, S. Viitanen and Y. Difeng from our side.


1996-

Ali left after one year post doc position and joined the Dept. of Computational & Applied Mathematics at the University of Witwatersrand, Johannesburg, South Africa. Viitanen obtained his Ph.D. in 1997 [Viitanen 1997]. His Thesis includes the following published papers: [Törn and Viitanen 1992, 1994], an iterative version of TGO saving computing time in determining nearest neighbours presented at the second Princeton Conference on Global Optimization [Törn and Viitanen (1996)], the algorithm for Multidimensional Bisection [Baritompa and Viitanen (1996)] based on the simple idea of sharing the intervals produced during bisection among multiple processors, and a paper on some modified CRS algorithms [Ali, Törn and Viitanen 1997]. In 1999, Törn was invited to visit Witwatersrand during 8-22.11 for co-work with Ali. During the stay he gave two lectures, one on Global Optimization in general and one on Clustering Methods.


References and Bibliography (sorting: year, author)


1970-1980
  1. Becker, R.W. and G.V. Lago (1970), "A global optimization algorithm", In Proceedings of the 8th Allerton Conference on Circuits and Systems Theory, 3-12.
  2. Törn, A.A. (1973), "Global optimozation as a combination of global and local search", In Proceedings of Computer Simulation Versus Analytical Solutions for Business and Economic Models, Gothenburg 1972, 191-206.
  3. Törn, A.A. (1974), "Global optimization as a combination of global and local search", Ph.D. Thesis, Åbo Akademi.
  4. Dixon, L.C.W. and G.P. Szegö (1975), "Towards global optimization", North- Holland.
  5. Törn, A.A. (1976), "Probabilistic global optimization, a custer analysis approach", In Proceedings of the Second European Congress on Operations Research, Stockholm, 521-527.
  6. Törn, A.A. (1977a), "Cluster analysis as a tool in a global optimization model", In Proceedings of Third International Congress of Cybernetics and Systems, Bucharest 1975, Springer Verlag, 249-260.
  7. Törn, A.A. (1977b), "Cluster analysis using seed points and density-determined hyperspheres with an application to global optimization", IEEE trans. on Systems, Man and Cybernetics 7, 610-616.
  8. Dixon, L.C.W. and G.P. Szegö (1978), "Towards global optimization 2", North- Holland.
  9. Gomulka, J. (1978), "A users experience with Törn's clustering algorithm", In [Dixon and Szegö 1978], 63-70.
  10. Törn, A.A. (1978), "A search clustering approach to global optimization", In [Dixon and Szegö 1978], 49-62.
  11. Spircu, L. (1979), "Cluster analysis in global optimization", Economic Computation and Economic Cybernetic Studies and Research, Bucharest 13, 43-50.
  12. Törn, A.A. (1979), "A program for global optimization, multistart with clustering (MSC)", In Proceedings of Euro IFIP 79, North- Holland, 427-434.
  13. Törn, A.A. (1980), "A sampling- search- clustering approach for exploring feasible/efficient solutions of MCDM problems", Computers and Operations Research 7, 67-79.
  14. Törn, A.A. (1980b), "A general purpose optimizer based on clustering", Technische Hochschule Leipzig, Wissenschaftliche Zeitschrift 4/1980, 383-389.

1981-1990
  1. Boender, C.G.E., A.H.G. Rinnooy Kan, L. Strougie and G.T. Timmer (1982), "A stochastic method for global optimization", Math. Progr. 22, 125-140.
  2. Törn, A.A. (1983), "A sampling- search- clustering approach for solving scalar (local,global) and vector optimization problems", In Carlsson and Kochetkov (Eds.), Theory and Practice of Multiple Criteria Decision Making, North- Holland, 119-141.
  3. Timmer, G.T. (1984), "Global optimization - A stochastic approach", Ph.D. Thesis, Erasmus University Rotterdam.
  4. Csendes, T. (1985), "Two non-derivative implementations of Boender "et al"'s global optimization method: numerical performance", Report 1985/2, Jo'zsef Attila University, Szeged, Hungary.
  5. Törn, A.A. (1986), "Clustering methods in global optimization", Preeprints of the Second IFAC Symposium on Stochastic Control, Vilnius, 19-23 May, Part 2, 138-143.
  6. Price, W.L. (1987), "Global optimization algorithm for a CAD workstation", JOTA, vol.55, pp.133-146.
  7. Tersoff, J. (1988]), "Empirical Interatomic Potential for Silicon with improved Elastic Properties", Physics Review B, vol.38, no.14, pp 9902-9905.
  8. Törn, A.A. (1988), "Parallel Monte Carlo with application to global optimization", Proceedings of the 30th Annual Meeting of the Scandinavian Simulation Society (SIMS), Espoo, Finland 21-22 April, 156-165, Also in: Proceedings of the 3-rd Polish-Finnish Symposium, Gdansk-Sobieszewo, September 26-29, 329-340.
  9. Juselius, C. (1989), "A topographical method for global optimization", Master Thesis, Åbo Akademi (In Swedish).
  10. Törn, A.A. and A. Zilinskas (1989), "Global optimization", Lecture Notes in Computer Science 350, (Springer-Verlag, Berlin), 255 pp.
  11. Törn, A. and A. Zilinskas (1990), "Parallel global optimization algorithms in optimal design", In: H.-J. Sebastian, K. Tammer (Eds.), System Modelling and Optimization, Lecture Notes in Control and Information Sciences 143, 951-960.

1991-1995
  1. Bonnemoy, C. and Hamma, S.B. (1991), "La methode du recuit simule: optimisation dans R^n", APII, Aut. Prod. Inf. Ind., Vol 25, No 5, 477-496.
  2. Dekkers, A. and Aarts, E. (1991), "Global Optimization and Simulated Annealing, Mathematical Programming", vol.50, pp.367-393.
  3. Viitanen, S. (1991), "SPATRA, a topographical method for parallel global optimization", Master Thesis, Åbo Akademi (In Swedish).
  4. Wood, G.R. (1991), "Multidimensional bisection and global optimization", Computers and Mathematics with Applications 21, 161-172.
  5. Törn, A. and Viitanen, S. (1992), "Topographical global optimization", In: C.A. Floudas and P.M. Pardalos (Eds.), Recent Advancses in Global Optimization, Princeton University Press, 384-398.
  6. Ali, M.M. and R. Smith (1993), "The Structure of Small Clusters Ejected by Ion Bombardment of Solid", Journal of Vacuum Science 44, Number 3/4, pp.377-379
  7. Törn, A. and Viitanen, S. (1993), "Topographical Global Optimization for Constrained problems", Åbo Akademi, Reports on Computer Science & Mathematics, A No. 143, 11 pp.
  8. Ali, M.M. and C. Storey, (1994), "Topographical Multilevel Single Linkage", Journal of Global Optimization, Vol 5, pp. 349-358.
  9. Ali, M.M. and C. Storey, (1994), "Modified Controlled Random Search Algorithms", International Journal of Computer Mathematics, Vol 53, pp.229-235.
  10. Törn, A.A. and Viitanen, S. (1994), "Topographical global optimization using pre-sampled points", Global Optimization 5, 267-276
  11. Törn, A.A. and Viitanen, S. (1994b), "Improving topographical global optimization", In Beulens, A.M., J. Dolezal, H.-J. Sebastian (Eds.), Proceedings of the second working conference of the IFIP TC 7.6 Working Group, Dagstuhl, Germany, 65-72.
  12. Ali, M.M. and C. Storey (1995), "A new topographical algorithm for global optimization", Journal of Faculty of science United Arab Emirates University 7, 132-138.

1996-
  1. Ali, M.M. and C. Storey (1996), "Aspiration Based Simulated Annealing Algorithm", Journal of Global Optimization 11, 181-191.
  2. Ali, M.M. and C. Storey, (1996), "The Optimal Control of Vehicle Suspension System", Proceedings of the 2nd International Conference on Adaptive computing in Engineering design and Control, 26-28 March 1996, Plymouth University.
  3. Törn, A. and S. Viitanen (1996), "Iterative topographical global optimization", In: C.A. Floudas and P.M. Pardalos (Eds.), State of the Art in Global Optimization, Princeton University Press, 353-363.
  4. Ali, M.M. (1997), "A short range many-body interatomic potential for modelling bcc metals (tungsten)".
  5. Ali, M., C. Storey and A. Törn (1997), "Application of stochastic global optimization algorithms to practical problems", Journal of Optimization Theory and Applications 95, No. 3, 545-563.
  6. Ali, M., A. Törn and S. Viitanen (1997), "A numerical comparison of some modified controlled random search algorithms", Journal of Global Optimization 11 (4), 377-385.
  7. Baritompa, W. and Viitanen, S. (1997), "Parallel Multidimensional Bisection", Concurrency: Practice and Experience 9(2), 113-121.
  8. Viitanen, S. (1997), "Some New Global Optimization Algorithms", TUCS Dissertations 5, 35 pp. + 5 papers.
  9. Törn, A., M. Ali and S. Viitanen (1999), "Stochastic global optimization: Problem classes and solution techniques", Journal of Global Optimization 14, 437-447.
  10. Hamma, B., S. Viitanen and A. Törn (2000), "Parallel continuous simulated annealing for global optimization, Optimization Methods and Software, Vol. 13, No. 2, 93-116.
  11. Ali, A. and A. Törn (2000), "Optimization of Carbon and Silicon Cluster Geometry for Tersoff Potential using Differential Evolution", In: C.A. Fluodas and P.M. Pardalos (Eds.), Optimization in Computational Chemistry and Molecular Biology, Kluver Academic Publishers, pp. 287-300.