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

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

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

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

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

Встановіть лічильник ітерацій ${\displaystyle \displaystyle k=0}$ і зробіть початкову здогадку ${\displaystyle \mathbf {x} _{0}}$ як мінімум.
Повторюйте:
1. Обчисліть напрямок спуску $p_{k}$
2. Оберіть $a_{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}.$ На кожному наступному кроці потрібно обчислювати лише одну додаткову внутрішню точку. З різних способів поділу інтервалу[1] пошук золотих перерізів особливо простий і ефективний, бо пропорції інтервалу зберігаються незалежно від того, як триває пошук:

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

Дивись також

Посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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