This paper deals with two kinds of the one-dimensional global optimization problem over a closed finite interval: (i) the objective function f(x) satisfies the Lipschitz condition with a constant L; (ii) the first derivative of f(x) satisfies the Lipschitz condition with a constant M. In the paper, six algorithms are presented for the case (i) and six algorithms for the case (ii). In both cases, auxiliary functions are constructed and adaptively improved during the search. In the case (i), piecewise linear functions are constructed and in the case (ii) smooth piecewise quadratic functions are used. The constants L and M either are taken as values known a priori or are dynamically estimated during the search. A recent technique that adaptively estimates the local Lipschitz constants over different zones of the search region is used to accelerate the search. A new technique called the local improvement is introduced in order to accelerate the search in both cases (i) and (ii). The algorithms are described in a unique framework, their properties are studied from a general viewpoint, and convergence conditions of the proposed algorithms are given. Numerical experiments executed on 120 test problems taken from the literature show quite a promising performance of the new acceleration techniques.

Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives

LERA, DANIELA;
2013

Abstract

This paper deals with two kinds of the one-dimensional global optimization problem over a closed finite interval: (i) the objective function f(x) satisfies the Lipschitz condition with a constant L; (ii) the first derivative of f(x) satisfies the Lipschitz condition with a constant M. In the paper, six algorithms are presented for the case (i) and six algorithms for the case (ii). In both cases, auxiliary functions are constructed and adaptively improved during the search. In the case (i), piecewise linear functions are constructed and in the case (ii) smooth piecewise quadratic functions are used. The constants L and M either are taken as values known a priori or are dynamically estimated during the search. A recent technique that adaptively estimates the local Lipschitz constants over different zones of the search region is used to accelerate the search. A new technique called the local improvement is introduced in order to accelerate the search in both cases (i) and (ii). The algorithms are described in a unique framework, their properties are studied from a general viewpoint, and convergence conditions of the proposed algorithms are given. Numerical experiments executed on 120 test problems taken from the literature show quite a promising performance of the new acceleration techniques.
Global optimization; Lipschitz derivatives; Balancing local and global information
File in questo prodotto:
File Dimensione Formato  
articoloSIOPT.pdf

Solo gestori archivio

Descrizione: Articolo principale
Tipologia: versione editoriale
Dimensione 455.97 kB
Formato Adobe PDF
455.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11584/51009
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 55
  • ???jsp.display-item.citation.isi??? 52
social impact