WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Алгоритм Левенберга — Марквардта — метод оптимизации, направленный на решение задач о наименьших квадратах. Является альтернативой методу Ньютона. Может рассматриваться как комбинация последнего с методом градиентного спуска или как метод доверительных областей[en][1]. Алгоритм был сформулирован независимо Левенбергом (1944) и Марквардтом (1963).

Постановка задачи

Пусть имеется задача о наименьших квадратах вида:

Эта задача отличается особым видом градиента и матрицы Гессе:

где  — матрица Якоби вектор-функции ,  — матрица Гессе для её компоненты .

Тогда согласно методу Гаусса — Ньютона в предположении доминирующей роли слагаемого над (то есть если норма значительно меньше максимального собственного значения матрицы ) очередное направление определяется из системы:

Алгоритм

Направление поиска Левенберга — Марквардта определяется из системы:

где  — некоторая неотрицательная константа, своя для каждого шага,  — единичная матрица.

Выбор можно осуществлять, делая его достаточным для монотонного спуска по функции невязки , то есть увеличивать параметр до тех пор, пока не будет достигнуто условие . Также параметр можно устанавливать исходя из отношения между фактическими изменениями функции достигнутыми в результате пробных шагов, и ожидаемыми величинами этих изменений при интерполяции. Подобную процедуру построил Флетчер.

Также можно показать, что удовлетворяет условию:

где  — параметр, связанный с .

Комбинация градиентного спуска и метода Гаусса — Ньютона

Нетрудно заметить, что при алгоритм вырождается в метод Гаусса — Ньютона, а при достаточно большом направление незначительно отличается от направления наискорейшего спуска. Таким образом, при правильном подборе параметра добиваются монотонного убывания минимизируемой функции. Неравенство всегда можно обеспечить, выбрав достаточно большим. Однако при этом теряется информация о кривизне, заключённая в первом слагаемом, и проявляются все недостатки метода градиентного спуска: в местах пологого наклона антиградиент мал, а в местах с крутым наклоном — велик, в то время как в первом случае желательно делать большие шаги, а во втором — маленькие. Так, с одной стороны, если есть длинная и узкая впадина на поверхности, определяемой функцией невязки , то компоненты градиента вдоль основания впадины — малы, а в направлении к стенкам — велики, в то время как идти желательно по основанию оврага. Способ учёта информации о кривизне предложил Марквардт. Он заметил, что если заменить единичную матрицу на диагональ матрицы Гессе, то можно достичь увеличения шага вдоль пологих участков и уменьшения вдоль крутых спусков:

Метод доверительных интервалов

При рассмотрении алгоритма Левенберга — Марквардта как метода доверительных интервалов с помощью эвристик выбирается интервал , на котором строится приближение функции :

При этом шаг определяется исходя из задачи минимизации:

Примечания

  1. Б. Т. Поляк. Метод Ньютона и его роль в оптимизации и вычислительной математике // Труды Института Системного Анализа Российской Академии Наук. — 2006. Т. 28. С. 44–62.

Литература

  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical optimization. М.: Мир, 1985. — 509 с.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии