Лінійний пошук в оптимізації — Вікіпедія

В оптимізації алгоритм лінійного пошуку — це один з двох основних ітеративних підходів до пошуку локального мінімуму ${\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}.}$ На кожному наступному кроці потрібно обчислювати лише одну додаткову внутрішню точку. З різних способів поділу інтервалу^[1] пошук золотих перерізів особливо простий і ефективний, бо пропорції інтервалу зберігаються незалежно від того, як триває пошук:

${\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.