Оптимизация без производных

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

Введение

Задача, которую необходимо решить, - численная оптимизация целевой функции. $f\colon A\to \mathbb {R}$ для какого-то набора $A$ (обычно $A\subset \mathbb {R} ^{n}$), то есть найти $x_{0}\in A$ так, что без потери общности $f(x_{0})\leq f(x)$ для всех $x\in A$.

Когда это применимо, общий подход заключается в итеративном улучшении предположения параметра путем локального подъема на холм в ландшафте целевой функции. Алгоритмы на основе производных используют производную информацию о $f$ чтобы найти хорошее направление поиска, поскольку, например, градиент указывает направление наибольшего подъема. Оптимизация на основе производных эффективна при поиске локальных оптимумов для гладких одномодальных задач в непрерывной области. Однако у них могут возникнуть проблемы, когда, например, $A$ отключено, или (смешанное) целое число, или когда $f$ дорого оценивать, или он негладкий, или зашумленный, так что (числовые аппроксимации) производных не дают полезной информации. Немного другая проблема заключается в том, когда $f$ является мультимодальным, и в этом случае локальные методы, основанные на производных, дают только локальный оптимум, но могут пропустить глобальный.

При оптимизации без производных для решения этих задач используются различные методы, используя только значения функции $f$, но без производных. Можно доказать, что некоторые из этих методов обнаруживают оптимумы, но некоторые являются скорее метаэвристическими, поскольку проблемы, как правило, сложнее решить по сравнению с выпуклой оптимизацией . Для них целью является, скорее, эффективный поиск «хороших» значений параметров, которые могут быть почти оптимальными при наличии достаточных ресурсов, но гарантии оптимальности обычно не могут быть предоставлены. Следует иметь в виду, что задачи разнообразны, поэтому обычно невозможно использовать один алгоритм для всех типов задач.

Алгоритмы

Известные алгоритмы оптимизации без производных включают:

• Байесовская оптимизация
• Координатный спуск и адаптивный координатный спуск
• Дифференциальная эволюция , включая многокритериальные варианты
• СДЕЛАННЫЙ
• Стратегии эволюции , Стратегии естественной эволюции ( CMA-ES , xNES, SNES)
• Генетические алгоритмы
• Алгоритм MCS
• Метод Нелдера-Мида
• Оптимизация роя частиц
• Поиск по шаблону
• ( Методы Пауэлла, основанные на интерполяции, например, COBYLA PRIMA )
• Случайный поиск (включая Лууса – Яаколу )
• Имитация отжига
• Стохастическая оптимизация
• Субградиентный метод
• различные алгоритмы на основе моделей, такие как BOBYQA и ORBIT

Тесты

Существуют тесты для алгоритмов оптимизации черного ящика, см., например, тесты bbob-biobj.

См. также

• Математическая оптимизация

Внешние ссылки

• Одет, Чарльз; Кокколарас, Майкл (2016). «Черный ящик и оптимизация без производных: теория, алгоритмы и приложения» . Оптимизация и инжиниринг . 17 : 1–2. дои : 10.1007/s11081-016-9307-4 .