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

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

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

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

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

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

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

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

Алгоритми

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

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

${\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 \varphi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618}$

Дивись також

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