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

DOI10.1137/110859129MaRDI QIDQ5300536zbMATH OpenOpenAlexFDO

Authors Daniela Lera, Yaroslav D. Sergeyev

Publication date 27 June 2013

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3522, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.746.2261

zbMATH Keywords

global optimizationaccelerationLipschitz functionsLipschitz derivativesbalancing local and global information

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26)

Abstract: This paper deals with two kinds of the one-dimensional global optimization problems 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), piece-wise linear functions are constructed and in the case (ii) smooth piece-wise 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 emph{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 accelerating techniques.

Recommendations

• Global one-dimensional optimization using smooth auxiliary functions
• A univariate global search working with a set of Lipschitz constants for the first derivative
• Novel local tuning techniques for speeding up one-dimensional algorithms in expensive global optimization using Lipschitz derivatives
• scientific article; zbMATH DE number 1058962
• Univariate geometric Lipschitz global optimization algorithms

Cited in

(33)

• Steklov regularization and trajectory methods for univariate global optimization
• GOSH: derivative-free global optimization using multi-dimensional space-filling curves
• Globally-biased disimpl algorithm for expensive global optimization
• Visualization of a statistical approximation of the Pareto front
• Global optimization of expensive black box functions using potential Lipschitz constants and response surfaces
• Lipschitz-inspired \texttt{HALRECT} algorithm for derivative-free global optimization
• Granular sieving algorithm for selecting best n$$ n $$ parameters
• On the least-squares fitting of data by sinusoids
• Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints
• On Acceleration of Derivative-Free Univariate Lipschitz Global Optimization Methods
• Global optimization on an interval
• On the search of the shape parameter in radial basis functions using univariate global optimization methods
• Optimal switching between cash-flow streams
• Space-filling curves for numerical approximation and visualization of solutions to systems of nonlinear inequalities with applications in robotics
• Multidimensional global optimization using numerical estimates of objective function derivatives
• Performance of convex underestimators in a branch-and-bound framework
• Combining global and local strategies to optimize parameters in magnetic spacecraft control via attitude feedback
• Operational zones for comparing metaheuristic and deterministic one-dimensional global optimization algorithms
• Accelerations for global optimization covering methods using second derivatives
• Metaheuristic vs. deterministic global optimization algorithms: the univariate case
• Accelerations for a variety of global optimization methods
• Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization
• A deterministic global optimization using smooth diagonal auxiliary functions
• Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties
• On deterministic diagonal methods for solving global optimization problems with Lipschitz gradients
• Global optimization method with numerically calculated function derivatives
• A Branch--and--Bound-Based Algorithm for Nonconvex Multiobjective Optimization
• Safe global optimization of expensive noisy black-box functions in the \(\delta \)-Lipschitz framework
• Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants
• A one-step worst-case optimal algorithm for bi-objective univariate optimization
• A univariate global search working with a set of Lipschitz constants for the first derivative
• A deterministic method for continuous global optimization using a dense curve
• Novel local tuning techniques for speeding up one-dimensional algorithms in expensive global optimization using Lipschitz derivatives

This page was built for publication: Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300536)