Оптимизировать неизвестную функцию, которую можно оценить только?

Учитывая неизвестную функцию , мы можем оценить ее значение в любой точке ее области, но у нас нет ее выражения. Другими словами, для нас как черный ящик. $f:\mathbb R^d \to \mathbb R$ $f$

Как называется проблема поиска минимизатора ? Какие существуют методы? $f$

Как называется задача поиска решения уравнения ? Какие существуют методы? $f(x)=0$

В вышеупомянутых двух проблемах, это хорошая идея, чтобы интерполировать или соответствовать некоторым оценкам f: используя функцию с известной формой и параметром быть определенным, а затем минимизировать или найти его корень? $(x_i, f(x_i)), i=1, \dots, n$ $g_\theta$ $\theta$ $g_\theta$

Спасибо и всего наилучшего!

optimization Тим
источник

Можете ли вы оценить его градиент в данной точке?

Chaohuang

@chaohuang: Есть два случая: вы можете или не можете оценить его градиент, в зависимости от предположений.

Тим

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

chaohuang

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

chaohuang

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

Брайан Борчерс

Ответы:

Методы, которые вы ищете - то есть, которые используют только оценки функций, но не производные - называются методами оптимизации без производных . О них много литературы, и в большинстве книг по оптимизации вы найдете главу о таких методах. Типичные подходы включают

Аппроксимация градиента конечными разностями, если можно разумно ожидать, что функция будет гладкой и, возможно, выпуклой;
Методы Монте-Карло, такие как имитация отжига;
Генетические алгоритмы.

Вольфганг Бангерт
источник

Могу ли я просто добавить «Суррогатное моделирование» в этот список? Они очень применимы для оптимизации «черного ящика», в частности, если оценка функции является дорогостоящей.

OscarB

Да, вы можете :-) Конечно, отличное дополнение.

Вольфганг Бангерт

Можно также использовать метод Нелдера-Мида, если известны хорошие оценки оптимума.

Да, вы можете использовать Nelder-Mead, но это ужасный алгоритм по сравнению с большинством других.

Вольфганг Бангерт

@WolfgangBangerth: Ваш комментарий к Nelder-Mead действителен только в измерении d> 2. В двух измерениях, это по многим задачам отличный и очень трудно победить метод.

Арнольд Ноймайер

Я думаю, что вам следует начать с: Семинара GECCO по бенчмаркингу оптимизации «черного ящика» с реальными параметрами (BBOB 2016) http://numbbo.github.io/workshops/index.html

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

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

Лисистрата
источник

-1

Я бы просто добавил, что одним из ключевых моментов здесь является возможность масштабирования метода оптимизации на многоядерных процессорах . Если вы можете выполнить несколько оценок функций одновременно, это даст вам ускорение, равное количеству задействованных ядер. Сравните это с использованием чуть более точной модели ответа, которая сделает вас на 10% более эффективным.

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

Павел
источник

Этот ответ слишком короткий, чтобы быть полезным (и оставаться полезным, поскольку ссылки могут исчезнуть в любой момент). Также, пожалуйста, отметьте, что вы являетесь автором этого программного обеспечения .

Кристиан Клэйсон