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

Оптимизация без производных это дисциплина в математическая оптимизация который не использует производная информация в классическом смысле для поиска оптимальных решений: иногда информация о производной целевой функции ж недоступен, ненадежен или нецелесообразен. Например, ж может быть негладким, или трудоемким для оценки, или каким-то образом зашумленным, поэтому методы, которые полагаются на производные или аппроксимируют их с помощью конечные разности малопригодны. Проблема нахождения оптимальных точек в таких ситуациях называется оптимизацией без производных, алгоритмы, не использующие производные или конечные разности, называются алгоритмы без производных.^[1]

Вступление

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

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

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

Алгоритмы

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

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

Смотрите также

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

Рекомендации

внешняя ссылка

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