Optimal algorithms for global optimization in case of unknown Lipschitz constant

DOI10.1016/J.JCO.2005.06.006MaRDI QIDQ2489149zbMATH OpenOpenAlexFDO

Authors Matthias Horn

Publication date 16 May 2006

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2005/143/

zbMATH Keywords

algorithmsComplexityGlobal optimizationLipschitz functionsnumerical exampleOptimal rate of convergence

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30)

Review text

The author presents two algorithms in order to find a point such that the value of a continuous multivariate Lipschitz function on the unit cube in that point be close to the infimum of the function. The first algorithm applies when the Lipschitz constant is known and the second when it is unknown and both are adaptive deterministic and use only function values. It is shown that both algorithms have the optimal rate of convergence and that adaptiveness is necessary and randomization yields no further advantages. A numerical test problem is presented to illustrate the behavior of the algorithm applying in the case when the Lipschitz constant is unknown.

Recommendations

• Lipschitzian optimization without the Lipschitz constant
• Global optimization of univariate Lipschitz functions. II: New algorithms and computational comparison
• scientific article; zbMATH DE number 757681
• Global optimization of univariate Lipschitz functions. I: Survey and properties
• On using estimates of Lipschitz constants in global optimization

Cites work

• Approximation and optimization on the Wiener space
• Deterministic and stochastic error bounds in numerical analysis
• Global optimization
• scientific article; zbMATH DE number 953034 (Why is no real title available?)
• Lipschitzian optimization without the Lipschitz constant
• Lower bound on complexity of optimization of continuous functions
• The complexity of the computation of the global extremum in a class of multi-extremum problems
• The real number model in numerical analysis
• Variational properties of averaged equations for periodic media

Cited in

(16)

• An algorithm for global optimization of Lipschitz continuous functions
• On using estimates of Lipschitz constants in global optimization
• Lipschitzian optimization without the Lipschitz constant
• Optimal estimation of univariate black-box Lipschitz functions with upper and lower error bounds.
• Lipschitz optimization methods for fitting a sum of damped sinusoids to a series of observations
• The alpha algorithm and the application of the cubic algorithm in case of unknown Lipschitz constant
• Local adaption for approximation and minimization of univariate functions
• On the experimental investigation of Pareto-Lipschitzian optimization
• On the worst-case optimal multi-objective global optimization
• scientific article; zbMATH DE number 617933 (Why is no real title available?)
• On the Pareto optimality in the context of Lipschitzian optimization
• Constrained, global optimization of unknown functions with Lipschitz continuous gradients
• Certified multifidelity zeroth-order optimization
• Deterministic computation of quantiles in a Lipschitz framework
• Measure-based diffusion grid construction and high-dimensional data discretization
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

This page was built for publication: Optimal algorithms for global optimization in case of unknown Lipschitz constant

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