Как эффективно найти максимальное значение в массиве, содержащем значения гладкой функции?

Question

У меня есть функция, которая принимает число с плавающей запятой и возвращает число с плавающей запятой.Можно предположить, что если бы вы построили график вывода этой функции, она была бы в форме 'n', т.е.была бы одна максимальная точка, и никаких других точек на функции с нулевым наклоном не было бы.Мы также знаем, что входное значение, которое дает этот максимальный выходной сигнал, будет лежать между двумя известными точками, возможно, 0,0 и 1,0.

Мне нужно эффективно найти входное значение, которое дает максимальное выходное значение в некоторой степени приближения, безвыполняю исчерпывающий поиск.

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

Answer 1

Я бы хотел пока подробно обсудить все остальные ответы по разным причинам, но не буду.

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

Я написал такой алгоритм на C ++. Есть предложения?

ОБНОВЛЕНИЕ : в GSL есть версия C минимизатора Brent. Архивы находятся здесь: ftp: //ftp.club.cc.cmu.edu/gnu/gsl/ Обратите внимание, что он будет покрыт некоторой разновидностью GNU «copyleft».

Когда я пишу это, последний и самый лучший из них - gsl-1.14.tar.gz. Минимизатор находится в файле gsl-1.14 / min / brent.c. Кажется, у него есть критерии прекращения, аналогичные тем, что я реализовал. Я не изучал, как он решает переключиться на золотое сечение, но для ОП это, вероятно, спорный вопрос.

ОБНОВЛЕНИЕ 2 : Я погуглил общедоступную версию Java, переведенную с FORTRAN. Я не могу ручаться за его качество. http://www1.fpl.fs.fed.us/Fmin.java Я заметил, что жестко закодированный КПД машины («точность машины» в комментариях) в два раза меньше значения для типичного ПК сегодня. Измените значение eps на 2.22045e-16.

Answer 2

Редактировать 2: Метод, описанный в Jive Dadson, - лучший способ сделать это. Я оставляю свой ответ, поскольку его легче реализовать, если скорость не слишком большая проблема.

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

Учитывая интервал [a, b], пусть x = (a + b) / 2 Пусть эпсилон будет чем-то очень маленьким.

Является ли (f (x + эпсилон) - f (x)) положительным? Если да, функция все еще растет в точке x, поэтому вы рекурсивно ищите интервал [x, b] В противном случае ищите интервал [a, x].

Может быть проблема, если максимальное значение лежит между x и x + epsilon, но вы можете попробовать это.

Редактировать: Преимущество этого подхода состоит в том, что он использует известные свойства рассматриваемой функции. То есть, я предположил, что «n» -образный, вы имели в виду, увеличивая-макс-уменьшая. Вот код Python, который я написал для проверки алгоритма:

def f(x):
    return -x * (x - 1.0)

def findMax(function, a, b, maxSlope):
    x = (a + b) / 2.0
    e = 0.0001
    slope = (function(x + e) - function(x)) / e
    if abs(slope) < maxSlope:
        return x
    if slope > 0:
        return findMax(function, x, b, maxSlope)
    else:
        return findMax(function, a, x, maxSlope)

Набрав findMax(f, 0, 3, 0.01), вы получите 0.504, если хотите.

Answer 3

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

.два начальных значения x[0]=0.0 и x[1]=1.0 Я бы продолжил вычислять следующие приближения как:

def next_x(x, xprev):
    return x - f(x) * (x - xprev) / (f(x) - f(xprev))

и, таким образом, вычислять x[2], x[3], ..., пока изменение в x не станет достаточно маленьким.

Редактировать : Как объясняет Джайв, это решение для поиска корней, которое не является поставленным вопросом.Для оптимизации правильным решением является минимизатор Brent, как объяснено в его ответе.

Answer 4

Учитывая, что это только функция от одной переменной и имеет один экстремум в интервале, вам не нужен метод Ньютона. Какой-то алгоритм поиска строк должен быть достаточным. Эта статья в Википедии на самом деле неплохая отправная точка, если не вдаваться в подробности. В частности, обратите внимание, что вы можете просто использовать метод, описанный в разделе «Прямой поиск», начиная с конечных точек вашего интервала в качестве двух точек.

Я не уверен, что вы считаете это «исчерпывающим поиском», но на самом деле он должен быть довольно быстрым, я думаю, для такого рода функции (то есть непрерывной гладкой функции с одним локальным экстремумом в заданный интервал).

Answer 5

Алгоритм Левенберга-Марквардта - это метод Ньютона, подобный оптимизатору. Он имеет реализацию C / C ++ levmar , которая не требует определения производной функции. Вместо этого он оценит целевую функцию в текущем районе, чтобы перейти к максимуму.

Кстати: этот веб-сайт, кажется, обновляется с тех пор, как я в последний раз посещал его, надеюсь, он даже тот же, который я запомнил По-видимому, теперь он также поддерживает другие языки.

Answer 6

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

Или просто возьмите 3 точки (влево / вверх / вправо) и зафиксируйте параболу.

Это зависит в основном от характера лежащего в основе отношения междуу, я думаю.

edit это в случае, если у вас есть массив значений, таких как состояния заголовка вопроса.Когда у вас есть функция , возьмите Ньютона-Рафсона.