Optimization Online


Local optima smoothing for global optimization

Bernardetta Addis (b.addis***at***ing.unifi.it)
Marco Locatelli (locatell***at***di.unito.it)
Fabio Schoen (schoen***at***ing.unifi.it)

Abstract: It is widely believed that in order to solve large scale global optimization problems an appropriate mixture of local approximation and global exploration is necessary. Local approximation, if first order information on the objective function is available, is efficiently performed by means of local optimization methods. Unfortunately, global exploration, in absence of some kind of global information on the problem, is a ``blind'' procedure, aimed at placing observations as evenly as possible in the search domain. Often this procedure reduces to uniform random sampling (like in Multistart algorithms, or in techniques based on clustering). In this paper we propose a new framework for global exploration which tries to guide random exploration towards the region of attraction of low-level local optima. The main idea originated by the use of smoothing techniques (based on gaussian convolutions): the possibility of applying a smoothing transformation not to the objective function but to the result of local searches seems to have never been explored yet. Although an exact smoothing of the results of local searches is impossible to implement, in this paper we propose a computational approximation scheme which has proven to be very efficient and (maybe more important) extremely robust in solving large scale global optimization problems with huge numbers of local optima.

Keywords: global optimization, local search, basin-hopping, Multistart, random sampling, smoothing transformation

Category 1: Global Optimization (Stochastic Approaches )

Citation: Technical Report DSI 5-2003 (revised), Dipartimento di Sistemi e Informatica, UniversitÓ degli Studi di Firenze, Firenze, 2003.

Download: [PDF]

Entry Submitted: 11/05/2003
Entry Accepted: 11/05/2003
Entry Last Modified: 11/05/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society