Поиск линии

В оптимизации . поиск по строке — это базовый итеративный подход к поиску локального минимума $\mathbf {x} ^{*}$ целевой функции $f:\mathbb {R} ^{n}\to \mathbb {R}$ . Сначала он находит направление спуска, вдоль которого целевая функция $f$ будет уменьшено, а затем вычисляет размер шага, который определяет, насколько далеко $\mathbf {x}$ должен двигаться в этом направлении. Направление спуска можно рассчитать различными методами, например градиентным спуском или методом квазиньютона . Размер шага может быть определен как точно, так и неточно.

Одномерный поиск линий [ править ]

Предположим, f — одномерная функция, $f:\mathbb {R} \to \mathbb {R}$ и предположим, что он унимодальный , то есть содержит ровно один локальный минимум x * в заданном интервале [ a , z ]. Это означает, что f строго убывает в [a,x*] и строго возрастает в [x*, z ]. В этом случае есть несколько способов найти (приблизительную) точку минимума. ^[1]^{: сек.5}

Методы нулевого порядка [ править ]

Методы нулевого порядка используют только оценки функций (т. е. оракул значений ), а не производные: ^[1]^{: сек.5}

Тернарный поиск : выберите две точки b,c такие, что a < b < c < z . Если f( b )≤f( c ), то x* должно находиться в [ a , c ]; если f( b )≥( c ), то x* должно находиться в [ b , z ]. В обоих случаях мы можем заменить интервал поиска на меньший. Если мы выберем b , c очень близко к центру интервала, то интервал сократится примерно на 1/2 на каждой итерации, но нам понадобится два вычисления функции на итерацию. Следовательно, метод имеет линейную сходимость со скоростью ${\sqrt {0.5}}\approx 0.71$ . Если мы выберем b,c так, чтобы разбиение a,b,c,z имело три интервала одинаковой длины, то интервал сжимается на 2/3 на каждой итерации, поэтому метод имеет линейную сходимость со скоростью ${\sqrt {2/3}}\approx 0.82$ .
Поиск Фибоначчи: это вариант троичного поиска, в котором точки b , c выбираются на основе последовательности Фибоначчи . На каждой итерации требуется только одна оценка функции, поскольку другая точка уже была конечной точкой предыдущего интервала. Следовательно, метод имеет линейную сходимость со скоростью $1/\varphi \approx 0.618$ .
Поиск золотого сечения : это вариант, в котором точки b , c выбираются на основе золотого сечения . Опять же, на каждой итерации требуется только одна оценка функции, и метод имеет линейную сходимость со скоростью $1/\varphi \approx 0.618$ . Это соотношение является оптимальным среди методов нулевого порядка.

Методы нулевого порядка очень общие — они не предполагают дифференцируемости или даже непрерывности.

Методы первого порядка [ править ]

Методы первого порядка предполагают, что f непрерывно дифференцируема и что мы можем вычислить не только f, но и ее производную. ^[1]^{: сек.5}

Метод деления пополам вычисляет производную f в центре интервала c : если f'(c)=0, то это точка минимума; если f'( c )>0, то минимум должен находиться в [ a , c ]; если f'( c )<0, то минимум должен находиться в [ c , z ]. Этот метод имеет линейную сходимость со скоростью 0,5.

Методы подбора кривой [ править ]

Методы аппроксимации кривой пытаются достичь суперлинейной сходимости , предполагая, что f имеет некоторую аналитическую форму, например, многочлен конечной степени. На каждой итерации существует набор «рабочих точек», в которых мы знаем значение f (а возможно, и его производную). На основе этих точек мы можем вычислить полином, соответствующий известным значениям, и найти его минимум аналитически. Точка минимума становится новой рабочей точкой, и мы переходим к следующей итерации: ^[1]^{: сек.5}

Метод Ньютона — это частный случай метода подбора кривой, в котором кривая представляет собой полином второй степени, построенный с использованием первой и второй производных f . Если метод запускается достаточно близко к невырожденному локальному минимуму (= с положительной второй производной), то он имеет квадратичную сходимость .
Regula falsi — это еще один метод, который аппроксимирует функцию до полинома второй степени, но использует первую производную в двух точках, а не первую и вторую производные в одной и той же точке. Если метод запускается достаточно близко к невырожденному локальному минимуму, то он имеет суперлинейную сходимость порядка $\varphi \approx 1.618$ .
Кубическая аппроксимация соответствует полиному третьей степени, используя как значения функции, так и ее производную в двух последних точках. Если метод запускается достаточно близко к невырожденному локальному минимуму, то он имеет квадратичную сходимость .

Методы аппроксимации кривой имеют сверхлинейную сходимость, когда начинаются достаточно близко к локальному минимуму, но в противном случае могут расходиться. Методы безопасной аппроксимации кривой одновременно выполняют метод линейной сходимости параллельно с методом аппроксимации кривой. На каждой итерации они проверяют, достаточно ли близка точка, найденная методом аппроксимации кривой, к интервалу, поддерживаемому методом защиты; если это не так, то для вычисления следующей итерации используется метод защиты. ^[1]^: 5.2.3.4

Многомерный поиск строк [ править ]

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

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

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

локальных минимумов Преодоление

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

См. также [ править ]

Доверительная область — двойной подход к поиску локального минимума: сначала вычисляет размер шага, а затем определяет направление спуска.
Поиск по сетке
Скорость обучения
Поиск по шаблону (оптимизация)
Метод секущего

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

Дальнейшее чтение [ править ]

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

[:0-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[1]