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

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

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

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

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

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

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

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

Алгоритмы

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

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

${\ 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}}) \ приблизительно 1,618}$

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

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

Ссылки

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

• Dennis, JE, 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.