In this paper, the global optimization problem miny∈SF(y) with S being a hyperinterval in RN and F(y) satisfying the Lipschitz condition with an unknown Lipschitz constant is considered. It is supposed that the function F(y) can be multiextremal, non-differentiable, and given as a 'black-box'. To attack the problem, a new global optimization algorithm based on the following two ideas is proposed and studied both theoretically and numerically. First, the new algorithm uses numerical approximations to space-filling curves to reduce the original Lipschitz multi-dimensional problem to a univariate one satisfying the Hölder condition. Second, the algorithm at each iteration applies a new geometric technique working with a number of possible Hölder constants chosen from a set of values varying from zero to infinity showing so that ideas introduced in a popular DIRECT method can be used in the Hölder global optimization. Convergence conditions of the resulting deterministic global optimization method are established. Numerical experiments carried out on several hundreds of test functions show quite a promising performance of the new algorithm in comparison with its direct competitors.

Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants

LERA, DANIELA;
2015-01-01

Abstract

In this paper, the global optimization problem miny∈SF(y) with S being a hyperinterval in RN and F(y) satisfying the Lipschitz condition with an unknown Lipschitz constant is considered. It is supposed that the function F(y) can be multiextremal, non-differentiable, and given as a 'black-box'. To attack the problem, a new global optimization algorithm based on the following two ideas is proposed and studied both theoretically and numerically. First, the new algorithm uses numerical approximations to space-filling curves to reduce the original Lipschitz multi-dimensional problem to a univariate one satisfying the Hölder condition. Second, the algorithm at each iteration applies a new geometric technique working with a number of possible Hölder constants chosen from a set of values varying from zero to infinity showing so that ideas introduced in a popular DIRECT method can be used in the Hölder global optimization. Convergence conditions of the resulting deterministic global optimization method are established. Numerical experiments carried out on several hundreds of test functions show quite a promising performance of the new algorithm in comparison with its direct competitors.
2015
global optimization; Lipschitz functions; space-filling curves; Hölder functions; deterministic numerical algorithms; DIRECT; classes of test functions
File in questo prodotto:
File Dimensione Formato  
CommNonlin2015.pdf

Solo gestori archivio

Descrizione: Articolo principale
Tipologia: versione editoriale
Dimensione 1.24 MB
Formato Adobe PDF
1.24 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
SetLipschitz_Lera.pdf

accesso aperto

Tipologia: versione post-print
Dimensione 693.36 kB
Formato Adobe PDF
693.36 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/11584/56910
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 41
  • ???jsp.display-item.citation.isi??? 31
social impact