Линейный поиск - Line search

Не путать с линейный поиск.

В оптимизация, то линейный поиск стратегия - одна из двух основных итеративный подходы к поиску местный минимум ${\displaystyle \mathbf {x} ^{*}}$ из целевая функция ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$. Другой подход регион доверия.

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

Пример использования

Смотрите также: Поиск строки с возвратом

Вот пример градиентного метода, который использует поиск линии на шаге 4.

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

На этапе поиска строки (4) алгоритм может либо точно свести к минимуму час, решая ${\displaystyle h'(\alpha _{k})=0}$, или же свободно, запросив достаточное уменьшение час. Одним из примеров первого является метод сопряженных градиентов. Последний называется поиском неточной строки и может выполняться разными способами, например поиск строки с возвратом или используя Условия Вульфа.

Как и другие методы оптимизации, линейный поиск можно комбинировать с имитация отжига позволить ему перепрыгнуть через некоторые локальные минимумы.

Алгоритмы

Методы прямого поиска

В этом методе минимум необходимо сначала заключить в квадратные скобки, поэтому алгоритм должен определять точки. Икс₁ и Икс₂ такие, что искомый минимум лежит между ними. Затем интервал делится путем вычисления ${\displaystyle f(x)}$ в двух внутренних точках, Икс₃ и Икс₄, и отклонение любой из двух внешних точек, не смежной с точкой Икс₃ и Икс₄ который имеет наименьшее значение функции. На последующих этапах необходимо рассчитать только одну дополнительную внутреннюю точку. Из различных методов деления интервала,^[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}$

Смотрите также

• Поиск золотого сечения
• Поиск по сетке
• Скорость обучения
• Поиск по шаблону (оптимизация)
• Секущий метод

Рекомендации

1. Box, M. J .; Дэвис, Д .; Суонн, В. Х. (1969). Методы нелинейной оптимизации. Оливер и Бойд.

дальнейшее чтение

• Dennis, J. E., Jr .; Шнабель, Роберт Б. (1983). «Глобально сходящиеся модификации метода Ньютона». Численные методы безусловной оптимизации и нелинейных уравнений. Энглвудские скалы: Прентис-Холл. С. 111–154. ISBN  0-13-627216-9.
• Нокедаль, Хорхе; Райт, Стивен Дж. (1999). «Методы линейного поиска». Численная оптимизация. Нью-Йорк: Спрингер. С. 34–63. ISBN  0-387-98793-2.
• Сунь, Вэньюй; Юань, Я-Сян (2006). «Линейный поиск». Теория и методы оптимизации: нелинейное программирование. Нью-Йорк: Спрингер. С. 71–117. ISBN  0-387-24975-3.