Бенчмарк для быстрых алгоритмов, задачей которых является минимизация функций.

Question

Есть ли набор тестовых функций для измерения производительности (с точки зрения скорости, возможно, с высокой точностью торгуется) заданного алгоритма, задачей которого является найти/глобальный минимум вещественнозначная функция над заданным интервалом? В конце концов: эта проблема является открытой проблемой или существует теоретический лучший алгоритм для такой задачи?

EDIT: нет никаких ограничений на функцию, кроме того, что она должна быть ограничена.

Answer 1

Без ограничений по функции, кроме ограниченности, не представляется возможным всегда находить свой глобальный минимум, не говоря уже о разумном времени.

Рассмотрим семейство вещественных функций, определенных на [0..1]:

f (x0) = y0 
f (x) = 0 for all other x in [0..1] 

Для любого фиксированного x0 in [0..1] и y0 < 0, то минимум на x0. Тем не менее, любой алгоритм без предварительного знания x0 будет с трудом находить его.

Answer 2

Возьмите функцию, которая равна 0 в каждой точке, где вы оцениваете f (x), и c для неизвестного c> 0 для каждой точки, где вы не оцениваете f (x). Если вы хотите, чтобы он был непрерывным, то если x находится между a и b, где a и b - соседние точки, где вы оценили f (a) и f (b), то f переходит в линейный от f (a) = 0 до f ((a + b)/2) = c и обратно линейно до f (b) = 0.

Очевидно, что каждый раз, когда вы оцениваете f (x), вы получаете нуль. Поскольку вы никогда ничего не оцениваете, ваш алгоритм не может заключить, что глобальный максимум - это ничего, кроме нуля, что неверно.