Линейный поиск - Line search
В оптимизации , то строка поиск стратегия является одним из двух основных итерационных подходов к поиску локального минимума в качестве целевой функции . Другой подход - это доверительный регион .
Подход линейного поиска сначала находит направление спуска, по которому будет уменьшена целевая функция , а затем вычисляет размер шага, который определяет, как далеко следует продвинуться в этом направлении. Направление спуска может быть вычислено различными методами, такими как градиентный спуск или квазиньютоновский метод . Размер шага можно определить точно или неточно.
Пример использования
Вот пример градиентного метода, который использует линейный поиск на шаге 4.
- Установите счетчик итераций и сделайте первоначальное предположение о минимальном
- Повторение:
- Вычислить направление спуска
- Выберите в «свободно» минимизировать над
- Обновление и
- До <терпимости
На этапе поиска строки (4) алгоритм может либо точно минимизировать h , решая , либо свободно , запрашивая достаточное уменьшение h . Одним из примеров первого является метод сопряженных градиентов . Последний называется поиском по неточной строке и может выполняться несколькими способами, такими как поиск строки с возвратом или с использованием условий Вульфа .
Как и другие методы оптимизации, линейный поиск можно комбинировать с моделированием отжига, чтобы позволить ему перепрыгнуть через некоторые локальные минимумы .
Алгоритмы
Методы прямого поиска
В этом методе минимум должен быть сначала заключен в скобки, поэтому алгоритм должен идентифицировать точки x 1 и x 2 так, чтобы искомый минимум находился между ними. Затем интервал делится путем вычисления в двух внутренних точках, x 3 и x 4 , и отбрасывания той из двух внешних точек, которая не является смежной с точкой x 3 и x 4, которая имеет наименьшее значение функции. На последующих этапах необходимо рассчитать только одну дополнительную внутреннюю точку. Из различных методов деления интервала поиск по золотому сечению особенно прост и эффективен, поскольку пропорции интервала сохраняются независимо от того, как выполняется поиск:
где
Смотрите также
- Поиск золотого сечения
- Поиск по сетке
- Скорость обучения
- Поиск по шаблону (оптимизация)
- Секущий метод
Ссылки
дальнейшее чтение
- 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.