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

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

Вступление

Решаемая задача - численно оптимизировать целевую функцию ${\displaystyle f\colon A\to \mathbb {R} }$ для некоторых набор ${\displaystyle A}$ (обычно ${\displaystyle A\subset \mathbb {R} ^{n}}$), т.е. найти ${\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
• Метод Нелдера-Мида
• Оптимизация роя частиц
• Поиск по шаблону
• Случайный поиск (включая Луус-Яакола )
• Имитация отжига
• Субградиентный метод

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

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

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

1. Conn, A.R .; Шейнберг, К.; Висенте, Л. Н. (2009). Введение в оптимизацию без производных. Серия книг MPS-SIAM по оптимизации. Филадельфия: СИАМ. Получено 2014-01-18.

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

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