No-free-lunch theorems in the continuum

DOI10.1016/J.TCS.2015.07.029zbMATH Open1329.68233OpenAlexW1582171764MaRDI QIDQ496010FDOQ496010

Authors Aureli Alabert, Alessandro Berti, R. Caballero, Marco Ferrante

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

stochastic processesblack-box optimisationno-free-lunch

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: No-Free-Lunch Theorems state, roughly speaking, that the performance of all search algorithms is the same when averaged over all possible objective functions. This fact was precisely formulated for the first time in a now famous paper by Wolpert and Macready, and then subsequently refined and extended by several authors, always in the context of a set of functions with discrete domain and codomain. Recently, Auger and Teytaud have shown that for continuum domains there is typically no No-Free-Lunch theorems. In this paper we provide another approach, which is simpler, requires less assumptions, relates the discrete and continuum cases, and that we believe that clarifies the role of the cardinality and structure of the domain.

Recommendations

• Continuous lunches are free plus the design of optimal optimization algorithms
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
• A ``no free lunch tutorial: sharpened and focused no free lunch
• A no-free-lunch theorem for non-uniform distributions of target functions
• Conditions that obviate the no-free-lunch theorems for optimization

Cites work

• scientific article; zbMATH DE number 6846220 (Why is no real title available?)
• A no-free-lunch theorem for non-uniform distributions of target functions
• Continuous lunches are free plus the design of optimal optimization algorithms
• On Positive-Definite Functions
• Optimizing without derivatives: what does the no free lunch theorem actually say?
• Stochastic global optimization.

Cited in

(5)

• No free lunch theorem: a review
• A ``no free lunch tutorial: sharpened and focused no free lunch
• Continuous lunches are free plus the design of optimal optimization algorithms
• A performance analysis of Basin Hopping compared to established metaheuristics for global optimization
• Free lunches on the discrete Lipschitz class

This page was built for publication: No-free-lunch theorems in the continuum

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