Сверните функцию

Question

Предположим, вам дана функция от одной переменной и аргументов a и b, и вас попросят найти минимальное значение, которое функция принимает на интервале [a, b]. (Можно предположить, что аргумент является двойным, хотя в моем приложении мне может понадобиться библиотека произвольной точности.)

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

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

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

Answer 1

Версия, которую вы описываете, с одним минимумом, легко решить.

Идея такова.Предположим, что у меня есть 3 очка с a < b < c и f(b) < f(a) и f(b) < f(c).Тогда истинный минимум составляет от a до c.Более того, если я выберу другую точку d где-то в интервале, тогда я могу выбросить одну из a или d и все еще иметь интервал с истинным минимумом в середине.Мои приближения будут экспоненциально улучшаться по мере увеличения числа итераций.

Мы не совсем начинаем с этого.Мы начинаем с 2 пунктов, a и b, и знаем, что ответ находится где-то посередине.Возьмите середину.Если f ниже конечных точек, мы находимся в случае, который я обсуждал выше.В противном случае он должен быть ниже одной из конечных точек и выше другой.Мы можем выбросить более высокую конечную точку и повторить.

Answer 2

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

• набор x = (b-a)/2
• проверить, находится ли x справа от минимума или влево
• если x осталось от минимума: b = x
• , если x справа от минимума: a = x
• повторять с начала, пока не надоест
• минимум на x

Чтобы проверить, является ли x левым / правым от минимума, придумайте небольшое значение epsilon и проверьте, f(x - epsilon) < f(x + epsilon). Если это так, минимум находится слева, в противном случае это справа. Под «до тех пор, пока вам не надоест», я имею в виду: придумайте еще одно маленькое значение delta и остановитесь, если fabs(f(x - epsilon) - f(x + epsilon)) < delta.

Обратите внимание, что в общем случае, когда вы ничего не знаете о поведении функции f, невозможно определить нетривиальное свойство f. Ну, если вы не готовы попробовать все возможные входные данные. Подробности см. В теореме Райса на http://en.wikipedia.org/wiki/Rice%27s_theorem (SO не распознает это как URL).

Answer 3

То, что вы хотите, это оптимизировать Унимодальная функция . Правильный алгоритм похож на алгоритм btilly, но вам нужны дополнительные очки.

Take 4 points a < b < c < d.
We want to minimize f in [a,d].

If f(b) < f(c) we know the minimum is in [a, c]
If f(b) > f(c) "  "    "   "       is in [b, d]

Это может дать алгоритм сам по себе, но есть хороший трюк , включающий золотое сечение, которое позволяет повторно использовать промежуточные значения (таким образом, вам нужно вычислять f только один раз за итерацию вместо дважды)

Answer 4

Не прямой ответ, но указатель на дальнейшее чтение:

• scipy.optimize: http://docs.scipy.org/doc/scipy/reference/optimize.html
• секция е04 наглиба: http://www.nag.co.uk/numeric/cl/nagdoc_cl09/html/genint/libconts.html

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

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

Answer 5

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

Answer 6

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