Метод прямого пошуку

Метод прямого пошуку — це метод математичної оптимізації, який не використовує інформацію про похідну в її класичному розумінні для пошуку оптимальних рішень: іноді інформація про похідну цільової функції f недоступна, ненадійна або непрактична для використання. Наприклад, функція f може бути негладкою, трудомісткою для оцінки, або якимось чином спотвореною шумами, тому методи, що спираються на похідні або їх наближення за допомогою скінченних різниць, є малопридатними. Проблема пошуку оптимальних точок у таких ситуаціях називається оптимізацією без похідних, алгоритми, які не використовують похідні або скінченні різниці, називаються алгоритмами прямого пошуку.

Вступ

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

Загальний підхід полягає в ітераційному покращенні параметра шляхом локального підйому на гору в ландшафті цільової функції. Алгоритми на основі похідних використовують інформацію про похідну $f$ для того, щоб знайти найкращий напрямок пошуку, оскільки, наприклад, градієнт дає напрямок найкрутішого підйому. Оптимізація на основі похідних ефективна при знаходженні локальних оптимумів для гладких, нерозривних функцій. Однак у них можуть виникнути проблеми, наприклад коли множина $A$ є незв'язною, або функція набуває лише цілих значень, або коли функція $f$ трудомістка для оцінки, або є негладкою, так що похідна (її числові наближення) не надає корисної інформації. Інша проблема — коли функція $f$ є мультимодальною, і в цьому випадку методи на основі локальних похідних дають лише локальний оптимум, та можуть упустити глобальний.

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

Алгоритми

До відомих алгоритмів прямого пошуку належать:

• Байєсівська оптимізація
• Координатний спуск і адаптивний координатний спуск
• Алгоритм зозулі
• DONE
• Стратегії еволюції, стратегії природної еволюції (CMA-ES, xNES, SNES)
• Генетичний алгоритм
• Алгоритм MCS
• Метод Нелдера – Міда
• Метод рою часток
• Метод Гука — Дживса
• Випадковий пошук (включно з Луусом — Яаколою)
• Алгоритм імітації відпалу
• Субградієнтний метод

Див. також

• Математична оптимізація

Посилання

• Audet, Charles; Kokkolaras, Michael (2016). Blackbox and derivative-free optimization: theory, algorithms and applications. Optimization and Engineering. 17: 1—2. doi:10.1007/s11081-016-9307-4.