Лінійний пошук в оптимізації

В оптимізації алгоритм лінійного пошуку — це один з двох основних ітеративних підходів до пошуку локального мінімуму ${\displaystyle x^{*}}$ цільової функції ${\displaystyle {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }}$. Інший підхід  — це ^[en].

Підхід лінійного пошуку спочатку знаходить напрямок спуску, уздовж якого буде зменшена цільова функція ${\displaystyle f}$, а потім обчислюється розмір кроку, який визначає, наскільки повинен рухатися ${\displaystyle {\displaystyle \mathbf {x} }}$ у тому напрямку. Напрямок спуску можна обчислити різними методами, такими як градієнтний спуск, метод Ньютона та квазіньютонівські методи. Розмір кроку може бути визначений точно або приблизно.

Приклади використання

Ось приклад градієнтного методу, який використовує лінійний пошук на кроці 2:2.

1. Встановіть лічильник ітерацій ${\displaystyle {\displaystyle \displaystyle k=0}}$ і зробіть початкову здогадку ${\displaystyle {\displaystyle \mathbf {x} _{0}}}$ як мінімум.
2. Повторюйте:
   1. Обчисліть напрямок спуску ${\displaystyle p_{k}}$
   2. Оберіть ${\displaystyle \alpha _{k}}$ щоб приблизно мінімізувати ${\displaystyle {\displaystyle h(\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}}$ для ${\displaystyle {\displaystyle \alpha \in \mathbb {R} _{+}}}$
   3. Оновіть ${\displaystyle {\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}}$ і ${\displaystyle {\textstyle k=k+1}}$
   4. Поки не досягнете ${\displaystyle {\displaystyle \|\nabla f(\mathbf {x} _{k+1})\|}<}$ прийнятної межі

На кроці 2:2 алгоритм може або точно мінімізувати ${\displaystyle h}$, розв'язавши ${\displaystyle h'(\alpha _{k})=0}$, або менш точно, запитуючи про достатнє зменшення ${\displaystyle h}$. Одним із прикладів першого є метод спряженого градієнта. Останній називається неточним лінійним пошуком і може здійснюватися різними способами, наприклад, лінійний пошук з вертанням або використанням умов Вольфе.

Як і інші методи оптимізації, лінійний пошук може поєднуватися з імітованим відпалом, щоб він міг переходити через деякі локальні мінімуми.

Алгоритми

Прямі методи пошуку

У цьому методі мінімум слід спершу оточити, тому алгоритм повинен ідентифікувати точки ${\displaystyle x_{1}}$ та ${\displaystyle x_{2}}$, щоб шуканий мінімум лежав між ними. Потім інтервал ділиться обчисленням функції ${\displaystyle f(x)}$ у двох внутрішніх точках, ${\displaystyle x_{3}}$ та ${\displaystyle x_{4}}$, і відкиданням тої із зовнішніх точок, яка несусідня з меншою серед ${\displaystyle x_{3}}$ та ${\displaystyle x_{4}.}$ На кожному наступному кроці потрібно обчислювати лише одну додаткову внутрішню точку. З різних способів поділу інтервалупошук золотих перерізів особливо простий і ефективний, бо пропорції інтервалу зберігаються незалежно від того, як триває пошук:

${\displaystyle {\displaystyle {\frac {1}{\varphi }}(x_{2}-x_{1})=x_{4}-x_{1}=x_{2}-x_{3}=\varphi (x_{2}-x_{4})=\varphi (x_{3}-x_{1})=\varphi ^{2}(x_{4}-x_{3})}}$

де

${\displaystyle {\displaystyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618}}$

Дивись також

• Метод хорд
• Метод Ньютона в оптимізації
• Метод Гука — Дживса
• Метод Нелдера – Міда
• Метод золотого перетину

Посилання

1. Swann, W.H. (1 березня 1969). A survey of non-linear optimization techniques. FEBS Letters. Т. 2, № S1. с. S39—S55. doi:10.1016/0014-5793(69)80075-x. ISSN 0014-5793. Процитовано 23 грудня 2019.