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

DOI10.1137/110859129zbMATH Open1270.90049arXiv1307.3522OpenAlexW2045376744MaRDI QIDQ5300536FDOQ5300536

Yaroslav D. Sergeyev, Daniela Lera

Publication date: 27 June 2013

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

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.

Full work available at URL: https://arxiv.org/abs/1307.3522

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

zbMATH Keywords

global optimizationaccelerationLipschitz functionsLipschitz derivativesbalancing local and global information

Mathematics Subject Classification ID

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

Cited In (33)

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