В математике и вычислительной технике алгоритм Левенберга – Марквардта ( LMA или просто LM ), также известный как метод наименьших квадратов с затуханием ( DLS ), используется для решения нелинейных задач наименьших квадратов . Эти проблемы минимизации возникают, в частности, при подборе кривой наименьших квадратов .
LMA используется во многих программных приложениях для решения общих задач аппроксимации кривой. Однако, как и во многих алгоритмах подгонки, LMA находит только локальный минимум , который не обязательно является глобальным минимумом . LMA интерполирует между алгоритмом Гаусса – Ньютона (GNA) и методом градиентного спуска . LMA более надежен, чем GNA, а это означает, что во многих случаях он находит решение, даже если оно начинается очень далеко от конечного минимума. Для корректных функций и разумных начальных параметров LMA обычно медленнее, чем GNA. LMA также можно рассматривать как Гаусс-Ньютон, используя подход доверительной области .
Алгоритм был впервые опубликован в 1944 году Кеннет Левенберг , [1] , работая в Frankford армии Арсенал . Он был заново открыт в 1963 году Дональда Marquardt , [2] , который работал в качестве статистик в DuPont , и независимо друг от друга Girard, [3] Винна [4] и Morrison. [5]
Проблема
Основное применение алгоритма Левенберга – Марквардта - это задача аппроксимации кривой наименьших квадратов: при заданном наборе эмпирические пары независимых и зависимых переменных, найти параметры модельной кривой так что сумма квадратов отклонений сводится к минимуму:
- который предполагается непустым.
Решение
Как и другие числовые алгоритмы минимизации, алгоритм Левенберга – Марквардта является итерационной процедурой. Чтобы начать минимизацию, пользователь должен предоставить начальное предположение для вектора параметров.. В случаях с одним минимумом необоснованное стандартное предположение, напримербудет работать нормально; в случаях с несколькими минимумами алгоритм сходится к глобальному минимуму только в том случае, если первоначальное предположение уже несколько близко к окончательному решению.
На каждой итерации вектор параметров заменяется новой оценкой . Чтобы определить, функция аппроксимируется его линеаризацией :
где
это градиент (вектор-строка в данном случае) относительно .
Сумма квадратичных отклонений имеет минимум при нулевом градиенте по отношению к. Приведенная выше аппроксимация первого порядка дает
или в векторной записи,
Взяв производную от относительно и установка результата на ноль дает
где - матрица Якоби , у которой-я строка равна , и где а также векторы с -й компонент а также соответственно. Приведенное выше выражение, полученное дляподпадает под метод Гаусса-Ньютона. Матрица Якоби, как определено выше, является (в общем случае) не квадратной матрицей, а прямоугольной матрицей размера, где - количество параметров (размер вектора ). Умножение матриц дает необходимые квадратная матрица и произведение матрица-вектор в правой части дают вектор размера . В результате получается набор линейные уравнения, которые можно решить для .
Вклад Левенберга заключается в замене этого уравнения «версией с затуханием»:
где - единичная матрица, дающая в качестве приращения к оцениваемому вектору параметров .
(Неотрицательный) коэффициент демпфирования корректируется на каждой итерации. Если сокращениеявляется быстрым, можно использовать меньшее значение, приближая алгоритм к алгоритму Гаусса – Ньютона , тогда как если итерация дает недостаточное уменьшение невязки,может быть увеличен, делая шаг ближе к направлению градиентного спуска. Обратите внимание , что градиент от относительно равно . Следовательно, при больших значениях, шаг будет сделан примерно в направлении, противоположном градиенту. Если либо длина расчетного шага или уменьшение суммы квадратов из последнего вектора параметров упадут ниже предопределенных пределов, итерация остановится, а вектор последнего параметра считается решением.
Недостаток алгоритма Левенберга заключается в том, что если значение коэффициента демпфирования большой, инвертирующий вообще не используется. Флетчер представил, что мы можем масштабировать каждый компонент градиента в соответствии с кривизной, чтобы было большее движение вдоль направлений, где градиент меньше. Это позволяет избежать медленного схождения в направлении небольшого градиента. Поэтому Флетчер в своей статье 1971 года Модифицированная подпрограмма Марквардта для нелинейных наименьших квадратов заменила единичную матрицу с диагональной матрицей, состоящей из диагональных элементов , что делает масштаб решения инвариантным:
Подобный коэффициент затухания появляется в регуляризации Тихонова , которая используется для решения линейных некорректных задач , а также в гребенчатой регрессии , методе оценки в статистике .
Выбор параметра демпфирования
Были выдвинуты различные более или менее эвристические аргументы в пользу лучшего выбора параметра демпфирования. . Существуют теоретические аргументы, показывающие, почему некоторые из этих вариантов гарантируют локальную сходимость алгоритма; однако этот выбор может привести к тому, что глобальная сходимость алгоритма страдает из-за нежелательных свойств наискорейшего спуска , в частности, очень медленной сходимости, близкой к оптимальной.
Абсолютные значения любого выбора зависят от того, насколько хорошо масштабируется исходная задача. Марквардт рекомендовал начинать со значения и фактор . Первоначальная установка и вычисляя остаточную сумму квадратов после одного шага от начальной точки с коэффициентом демпфирования а во-вторых с . Если оба они хуже, чем начальная точка, то демпфирование увеличивается путем последовательного умножения на пока не будет найдена лучшая точка с новым коэффициентом демпфирования для некоторых .
Если использовать коэффициент демпфирования приводит к уменьшению квадрата остатка, тогда это принимается как новое значение (и новое оптимальное местоположение принимается таким, как полученное с этим коэффициентом демпфирования), и процесс продолжается; при использовании привел к худшему остатку, но с использованием привело к лучшему остатку, тогда остается неизменным, а новый оптимум принимается как значение, полученное с помощью как коэффициент демпфирования.
Эффективная стратегия управления параметром демпфирования, называемая отложенным удовлетворением , состоит в увеличении параметра на небольшую величину для каждого шага в гору и в значительном уменьшении для каждого шага вниз. Идея этой стратегии состоит в том, чтобы избежать слишком быстрого спуска в начале оптимизации, тем самым ограничивая шаги, доступные в будущих итерациях, и, следовательно, замедляя сходимость. [6] Увеличение в 2 раза и уменьшение в 3 раза оказалось эффективным в большинстве случаев, в то время как для больших задач более экстремальные значения могут работать лучше, с увеличением в 1,5 раза и уменьшением. в 5 раз. [7]
Геодезическое ускорение
При интерпретации шага Левенберга – Марквардта как скорости вдоль геодезического пути в пространстве параметров, можно улучшить метод, добавив член второго порядка, который учитывает ускорение по геодезической
где это решение
Поскольку этот член геодезического ускорения зависит только от производной по направлению по направлению скорости , он не требует вычисления полной производной матрицы второго порядка, требуя лишь небольших накладных расходов с точки зрения затрат на вычисления. [8] Поскольку производная второго порядка может быть довольно сложным выражением, может быть удобно заменить ее конечно-разностным приближением
где а также уже были вычислены алгоритмом, поэтому требуется только одна дополнительная оценка функции для вычисления . Выбор конечно-разностного шагаможет повлиять на стабильность алгоритма, и значение около 0,1 обычно является разумным. [7]
Поскольку ускорение может указывать в направлении, противоположном скорости, чтобы предотвратить остановку метода в случае, если демпфирование слишком мало, добавляется дополнительный критерий ускорения, чтобы принять шаг, требующий, чтобы
где обычно устанавливается на значение меньше 1, с меньшими значениями для более сложных задач. [7]
Добавление члена геодезического ускорения может позволить значительно увеличить скорость сходимости, и это особенно полезно, когда алгоритм движется через узкие каньоны в ландшафте целевой функции, где разрешенные шаги меньше и выше точность из-за второго порядка термин дает значительные улучшения. [7]
Пример
В этом примере мы пытаемся подогнать функцию с использованием алгоритма Левенберга – Марквардта, реализованного в GNU Octave в качестве функции leasqr . Графики показывают все более точное соответствие параметрам., используется в исходной кривой. Только тогда, когда параметры на последнем графике выбраны наиболее близкими к исходному, кривые будут точно соответствовать. Это уравнение является примером очень чувствительных начальных условий для алгоритма Левенберга – Марквардта. Одной из причин такой чувствительности является наличие нескольких минимумов - функция имеет минимумы при значении параметра а также .
Смотрите также
- Доверительный регион
- Метод Нелдера – Мида
- Варианты алгоритма Левенберга – Марквардта также использовались для решения нелинейных систем уравнений. [9]
Рекомендации
- ^ Левенберг, Кеннет (1944). «Метод решения некоторых нелинейных задач наименьших квадратов» . Квартал прикладной математики . 2 (2): 164–168. DOI : 10,1090 / QAM / 10666 .
- ^ Марквардт, Дональд (1963). "Алгоритм оценки нелинейных параметров методом наименьших квадратов". Журнал СИАМ по прикладной математике . 11 (2): 431–441. DOI : 10.1137 / 0111030 . hdl : 10338.dmlcz / 104299 .
- ^ Жирар, Андре (1958). "Отрывок из Теоретического и инструментального ревю ". Rev. Opt . 37 : 225–241, 397–424.
- ^ Винн, CG (1959). «Проектирование линз на электронно-цифровом компьютере: I». Proc. Phys. Soc. Лондон . 73 (5): 777–787. Bibcode : 1959PPS .... 73..777W . DOI : 10.1088 / 0370-1328 / 73/5/310 .
- ^ Моррисон, Дэвид Д. (1960). «Методы нелинейных задач наименьших квадратов и доказательства сходимости». Труды семинара Лаборатории реактивного движения по программам слежения и определению орбиты : 1–9.
- ^ Транструм, Марка К; Махта, Бенджамин Б; Сетна, Джеймс П. (2011). «Геометрия нелинейных наименьших квадратов с приложениями к неаккуратным моделям и оптимизации». Physical Review E . APS. 83 (3): 036701.
- ^ а б в г Транструм, Марка К; Сетна, Джеймс П. (2012). «Улучшения алгоритма Левенберга-Марквардта для нелинейной минимизации методом наименьших квадратов». arXiv : 1201,5885 .
- ^ «Нелинейная аппроксимация методом наименьших квадратов» . Научная библиотека GNU. Архивировано из оригинала на 2020-04-14.
- ^ Канцов, Кристиан; Ямасита, Нобуо; Фукусима, Масао (2004). «Методы Левенберга – Марквардта со свойствами сильной локальной сходимости для решения нелинейных уравнений с выпуклыми ограничениями» . Журнал вычислительной и прикладной математики . 172 (2): 375–397. DOI : 10.1016 / j.cam.2004.02.013 .
дальнейшее чтение
- Море, Хорхе Дж .; Соренсен, Дэниел К. (1983). «Вычисление шага доверительной области» (PDF) . SIAM J. Sci. Стат. Comput . 4 (3): 553–572. DOI : 10.1137 / 0904038 .
- Гилл, Филип Э .; Мюррей, Уолтер (1978). «Алгоритмы решения нелинейной задачи наименьших квадратов». Журнал СИАМ по численному анализу . 15 (5): 977–992. Bibcode : 1978SJNA ... 15..977G . DOI : 10.1137 / 0715063 .
- Пухоль, Хосе (2007). «Решение нелинейных обратных задач и метод Левенберга-Марквардта» . Геофизика . SEG. 72 (4): W1 – W16. Bibcode : 2007Geop ... 72W ... 1P . DOI : 10.1190 / 1.2732552 .[ постоянная мертвая ссылка ]
- Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Springer. ISBN 978-0-387-30303-1.
Внешние ссылки
- Подробное описание алгоритма можно найти в Численных рецептах в C, Глава 15.5: Нелинейные модели.
- CT Kelley, Итерационные методы оптимизации , SIAM Frontiers in Applied Mathematics, № 18, 1999, ISBN 0-89871-433-8 . Интернет-копия
- История алгоритма в новостях SIAM
- Учебник Ананта Ранганатана
- К. Мадсен, Х. Б. Нильсен, О. Тинглефф, Методы решения нелинейных задач наименьших квадратов (учебное пособие по нелинейным методам наименьших квадратов; код LM: аналитический секанс Якоби )
- T. Strutz: Data Fitting and Uncertainty (Практическое введение в взвешенный метод наименьших квадратов и другие аспекты). 2-е издание, Springer Vieweg, 2016 г., ISBN 978-3-658-11455-8 .
- HP Gavin, Метод Левенберга-Марквардта для нелинейных задач аппроксимации кривой методом наименьших квадратов ( включая реализацию MATLAB )