Алгоритм Левенберга – Марквардта

Алгоритм, используемый для решения нелинейных задач наименьших квадратов

В математике и вычислениях, алгоритм Левенберга – Марквардта (LMA или просто LM ), также известный как затухающие наименьшие квадраты (DLS ), используется для решения нелинейных задач наименьших квадратов. Эти проблемы минимизации возникают, в частности, при наименьших квадратах аппроксимации кривой.

LMA используется во многих программных приложениях для решения общих задач аппроксимации кривой. Однако, как и во многих алгоритмах подгонки, LMA находит только локальный минимум, который не обязательно является глобальным минимумом. LMA интерполирует между алгоритмом Гаусса – Ньютона (GNA) и методом градиентного спуска. LMA более надежен, чем GNA, что означает, что во многих случаях он находит решение, даже если оно начинается очень далеко от конечного минимума. Для корректных функций и разумных начальных параметров LMA, как правило, немного медленнее, чем GNA. LMA также можно рассматривать как Гаусс – Ньютон, используя подход доверительной области.

Алгоритм был впервые опубликован в 1944 году Кеннетом Левенбергом, когда он работал в Франкфордском армейском арсенале. Он был повторно открыт в 1963 году Дональдом Марквардтом, который работал статистиком в DuPont, и независимо Жираром, Винном и Моррисоном.

• 1 Проблема
• 2 Решение
  • 2.1 Выбор параметра демпфирования
  • 2.2 Геодезическое ускорение
• 3 Пример
• 4 См. Также
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

Основное применение алгоритма Левенберга – Марквардта - задача аппроксимации кривой наименьших квадратов: задан набор $m\; \{\backslash \; displaystyle\; m\}$эмпирические пары $(xi,\; yi)\; \{\backslash \; displaystyle\; \backslash \; left\; (x\_\; \{i\},\; y\_\; \{i\}\; \backslash \; right)\}$независимых и зависимых переменных, найдите параметры $\beta \; \{\; \backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$модельной кривой $f\; (x,\; \beta )\; \{\backslash \; displaystyle\; f\; \backslash \; left\; (x,\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \}$так, чтобы сумма квадратов отклонений $S\; (\beta )\; \{\backslash \; displaystyle\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}$была свернуто:

$\beta \; ^\; \in \; argmin\; \beta \; \; S\; (\beta )\; \equiv \; argmin\; \beta \; \; \sum \; я\; =\; 1\; м\; [yi\; -\; f\; (xi,\; \beta )]\; 2,\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}\; \backslash \; in\; \backslash \; operatorname\; \{argmin\; \}\; \backslash \; limits\; \_\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; Equiv\; \backslash \; operatorname\; \{argmin\}\; \backslash \; limits\; \_\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{m\}\; \backslash \; left\; [y\_\; \{i\}\; -f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; right]\; ^\; \{2\},\}$который предполагается непустым.

Как и другие алгоритмы числовой минимизации, алгоритм Левенберга – Марквардта является итеративной процедурой. Чтобы начать минимизацию, пользователь должен предоставить начальное предположение для вектора параметров $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$. В случаях с одним минимумом используется неинформированное стандартное предположение, например $\beta \; T\; =\; (1,\; 1,\dots ,\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; ^\; \{\backslash \; text\; \{T\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1,\; \backslash \; 1,\; \backslash \; \backslash \; dots,\; \backslash \; 1\; \backslash \; end\; \{pmatrix\}\}\}$будут работать нормально; в случаях с множественными минимумами алгоритм сходится к глобальному минимуму только в том случае, если первоначальное предположение уже несколько близко к окончательному решению.

На каждой итерации вектор параметров $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$заменяется новой оценкой $\beta \; +\; \delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$. Чтобы определить $\delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$, функция $f\; (xi,\; \beta \; +\; \delta )\; \{\backslash \; displaystyle\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\}$аппроксимируется его линеаризацией :

$f\; (xi,\; \beta \; +\; \delta )\; \approx \; f\; (xi,\; \beta )\; +\; J\; я\; \delta ,\; \{\backslash \; displaystyle\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\; \backslash \; приблизительно\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; +\; \backslash \; mathbf\; \{J\}\; \_\; \{i\}\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\},\}$

где

$J\; i\; =\; \partial \; f\; (xi,\; \beta )\; \partial \; \beta \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{J\}\; \_\; \{i\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}\; \{\backslash \; partial\; \{\backslash \; boldsymbol\; \{\backslash \; beta\; \}\}\}\}\}$

- это градиент (вектор-строка в данном случае) $f\; \{\backslash \; displaystyle\; f\}$относительно $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$.

Сумма $S\; (\beta )\; \{\backslash \; displaystyle\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}$квадратных отклонений имеет минимум при нулевом градиенте относительно $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$. Приведенное выше приближение первого порядка для $f\; (xi,\; \beta \; +\; \delta )\; \{\backslash \; displaystyle\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\; \}$дает

$S\; (\beta \; +\; \delta )\; \approx \; \sum \; i\; =\; 1\; m\; [yi\; -\; f\; (xi,\; \beta )\; -\; J\; i\; \delta ]\; 2,\; \{\backslash \; displaystyle\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\; \backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\; \backslash \; приблизительно\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{m\}\; \backslash \; left\; [y\_\; \{i\}\; -f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; -\; \backslash \; mathbf\; \{J\}\; \_\; \{i\}\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right]\; ^\; \{2\},\}$

или в векторной записи

$S (β + δ) ≈ ‖ y - f (β) - J δ ‖ 2 = [y - f (β) - J δ] T [y - f (β) - J δ] = [y - f (β)] T [ y - f (β)] - [y - f (β)] TJ δ - (J δ) T [y - f (β)] + δ TJTJ δ = [y - f (β)] T [y - f (β)] - 2 [y - f (β)] TJ δ + δ TJTJ δ. {\ displaystyle {\ begin {align} S \ left ({\ boldsymbol {\ beta}} + {\ boldsymbol {\ delta}} \ right) \ приблизительно \ left \ | \ mathbf {y} - \ mathbf {f } \ left ({\ boldsymbol {\ beta}} \ right) - \ mathbf {J} {\ boldsymbol {\ delta}} \ right \ | ^ {2} \\ = \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) - \ mathbf {J} {\ boldsymbol {\ delta}} \ right] ^ {\ mathrm {T}} \ left [\ mathbf { y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) - \ mathbf {J} {\ boldsymbol {\ delta}} \ right] \\ = \ left [\ mathbf {y } - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm {T}} \ left [\ mathbf {y} - \ mathbf {f} \ left ({ \ boldsymbol {\ beta}} \ right) \ right] - \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm { T}} \ mathbf {J} {\ boldsymbol {\ delta}} - \ left (\ mathbf {J} {\ boldsymbol {\ delta}} \ right) ^ {\ mathrm {T}} \ left [\ mathbf { y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] + {\ boldsymbol {\ delta}} ^ {\ mathrm {T}} \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J} {\ boldsymbol {\ delta}} \\ = \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm {T}} \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] -2 \ left [\ mathbf {y} - \ mathbf {f} \ left ({\ boldsymbol {\ beta}} \ right) \ right] ^ {\ mathrm { T}} \ mathbf {J} {\ boldsymbol {\ delta}} + {\ boldsymbol {\ delta}} ^ {\ mathrm {T}} \ mathbf {J} ^ {\ mathrm {T}} \ mathbf {J } {\ boldsymbol {\ delta}}. \ end {align}}}$

Взяв производную от $S\; (\beta \; +\; \delta )\; \{\backslash \; displaystyle\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\; \backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\}$относительно $\delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$и установка результата на ноль дает

$(JTJ)\; \delta \; =\; JT\; [y\; -\; е\; (\beta )],\; \{\backslash \; displaystyle\; \backslash \; left\; (\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; mathbf\; \{J\}\; \backslash \; right)\; \{\backslash \; boldsymbol\; \{\backslash \; delta\; \}\}\; =\; \backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; left\; [\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{f\}\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; right],\}$

где $J\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{J\}\}$- это матрица Якоби, $i\; \{\backslash \; displaystyle\; i\}$- th ro w равно $J\; i\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{J\}\; \_\; \{i\}\}$, а где $f\; (\beta )\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\}\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}$и $y\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{y\}\}$- векторы с $i\; \{\backslash \; displaystyle\; i\}$-й компонент $f\; (xi,\; \beta )\; \{\backslash \; displaystyle\; f\; \backslash \; left\; (x\_\; \{i\},\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}$и $yi\; \{\backslash \; displaystyle\; y\_\; \{i\}\}$соответственно. Вышеупомянутое выражение, полученное для $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$, относится к методу Гаусса-Ньютона. Матрица Якоби, как определено выше, является (в общем случае) не квадратной матрицей, а прямоугольной матрицей размером $m\; \times \; n\; \{\backslash \; displaystyle\; m\; \backslash \; times\; n\}$, где $n\; \{\backslash \; displaystyle\; n\}$- количество параметров (размер вектора $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$). Умножение матриц $(JTJ)\; \{\backslash \; displaystyle\; \backslash \; left\; (\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; mathbf\; \{J\}\; \backslash \; right)\}$дает требуемый $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$квадратная матрица и произведение матрица-вектор с правой стороны дает вектор размера $n\; \{\backslash \; displaystyle\; n\}$. Результатом является набор из $n\; \{\backslash \; displaystyle\; n\}$линейных уравнений, которые можно решить для $\delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$.

Вклад Левенберга заключается в замене этого уравнения на «версию с затуханием»:

$(JTJ\; +\; \lambda \; I)\; \delta \; =\; JT\; [y\; -\; f\; (\beta )],\; \{\backslash \; displaystyle\; \backslash \; left\; (\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\; \}\}\; \backslash \; mathbf\; \{J\}\; +\; \backslash \; lambda\; \backslash \; mathbf\; \{I\}\; \backslash \; right)\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; =\; \backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; left\; [\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{f\}\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; right],\}$

где $I\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{I\}\}$- единичная матрица, давая как приращение $\delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$к оценочному вектору параметров $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$.

(Неотрицательный) коэффициент демпфирования $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$корректируется на каждой итерации. Если уменьшение $S\; \{\backslash \; displaystyle\; S\}$происходит быстро, можно использовать меньшее значение, приближая алгоритм к алгоритму Гаусса – Ньютона, тогда как если итерация дает недостаточное уменьшение остатка, $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$может быть увеличено, делая шаг ближе к направлению градиентного спуска. Обратите внимание, что градиент из $S\; \{\backslash \; displaystyle\; S\}$относительно $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\}$равно $-\; 2\; (JT\; [y\; -\; f\; (\beta )])\; T\; \{\backslash \; displaystyle\; -2\; \backslash \; left\; (\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; left\; [\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{f\}\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; right]\; \backslash \; right)\; ^\; \{\backslash \; mathrm\; \{T\}\}\}$. Следовательно, для больших значений $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$шаг будет делаться примерно в направлении, противоположном градиенту. Если либо длина вычисленного шага $\delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$, либо уменьшение суммы квадратов из последнего вектора параметров $\beta \; +\; \delta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; +\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\}$ниже предопределенных пределов, итерация останавливается, а вектор последнего параметра $\beta \; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{\backslash \; \backslash \; beta\}\}\}$считается решением.

Алгоритм Левенберга имеет недостаток в том, что если значение коэффициента демпфирования $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$велико, $JTJ\; +\; \lambda \; I\; \{\backslash \; displaystyle\; \backslash \; mathbf\; инвертируется\; \{J\}\; ^\; \{\backslash \; text\; \{T\}\}\; \backslash \; mathbf\; \{J\}\; +\; \backslash \; lambda\; \backslash \; mathbf\; \{I\}\}$вообще не используется. Флетчер представил, что мы можем масштабировать каждый компонент градиента в соответствии с кривизной, чтобы было большее движение вдоль направлений, где градиент меньше. Это позволяет избежать медленного схождения в направлении небольшого градиента. Поэтому Флетчер в своей статье 1971 года «Модифицированная подпрограмма Марквардта для нелинейных наименьших квадратов» заменил единичную матрицу $I\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{I\}\}$диагональной матрицей, состоящей из диагональных элементов $JTJ\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; text\; \{T\}\}\; \backslash \; mathbf\; \{J\}\}$, таким образом делая масштаб решения инвариантным:

$[JTJ\; +\; \lambda \; diag\; \; (\; JTJ)]\; \delta \; =\; JT\; [y\; -\; f\; (\beta )].\; \{\backslash \; displaystyle\; \backslash \; left\; [\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; mathbf\; \{J\}\; +\; \backslash \; lambda\; \backslash \; operatorname\; \{diag\}\; \backslash \; left\; (\backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; mathbf\; \{J\}\; \backslash \; right)\; \backslash \; right]\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\}\; =\; \backslash \; mathbf\; \{J\}\; ^\; \{\backslash \; mathrm\; \{T\}\}\; \backslash \; left\; [\backslash \; mathbf\; \{y\}\; -\; \backslash \; mathbf\; \{f\}\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\; \backslash \; right].\}$

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

Выбор параметра демпфирования

Были выдвинуты различные более или менее эвристические аргументы для лучший выбор для параметра демпфирования $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$. Существуют теоретические аргументы, показывающие, почему некоторые из этих вариантов гарантируют локальную сходимость алгоритма; однако этот выбор может привести к тому, что глобальная сходимость алгоритма будет страдать от нежелательных свойств наискорейшего спуска, в частности, очень медленной сходимости, близкой к оптимальной.

Абсолютные значения любого выбора зависят от того, насколько хорошо масштабируется исходная проблема. Марквардт рекомендовал начинать со значения $\lambda \; 0\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{0\}\}$и множителя $\nu >1\; \{\backslash \; displaystyle\; \backslash \; nu>1\}$. Первоначальная установка $\lambda \; =\; \lambda \; 0\; \{\backslash \; displaystyle\; \backslash \; lambda\; =\; \backslash \; lambda\; \_\; \{0\}\}$и вычисление остаточной суммы квадратов $S\; (\beta )\; \{\backslash \; displaystyle\; S\; \backslash \; left\; (\{\backslash \; boldsymbol\; \{\backslash \; beta\}\}\; \backslash \; right)\}$после одного шага от начальной точки с коэффициентом демпфирования $\lambda \; =\; \lambda \; 0\; \{\backslash \; displaystyle\; \backslash \; lambda\; =\; \backslash \; lambda\; \_\; \{0\}\}$и, во-вторых, с $\lambda \; 0\; /\; \nu \; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{0\}\; /\; \backslash \; nu\}$. Если оба из них хуже начальной точки, то демпфирование увеличивается путем последовательного умножения на $\nu \; \{\backslash \; displaystyle\; \backslash \; nu\}$, пока не будет найдена лучшая точка с новым коэффициентом демпфирования $\lambda \; 0\; \nu \; k\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{0\}\; \backslash \; nu\; ^\; \{k\}\}$для некоторых $k\; \{\backslash \; displaystyle\; k\}$.

Если u se коэффициента демпфирования $\lambda \; /\; \nu \; \{\backslash \; displaystyle\; \backslash \; lambda\; /\; \backslash \; nu\}$приводит к уменьшению квадрата невязки, затем это принимается как новое значение $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$(и новое оптимальное местоположение принимается как полученное с этим коэффициентом демпфирования), и процесс продолжается; если использование $\lambda \; /\; \nu \; \{\backslash \; displaystyle\; \backslash \; lambda\; /\; \backslash \; nu\}$привело к худшему остатку, но использование $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$привело к лучше невязка, тогда $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$остается без изменений, а новый оптимум принимается как значение, полученное с помощью $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$как коэффициент демпфирования.

Эффективная стратегия управления параметром демпфирования, называемая отложенным удовлетворением, состоит в небольшом увеличении параметра для каждого шага вверх и уменьшении на большую величину для каждого шага вниз. Идея, лежащая в основе этой стратегии, заключается в том, чтобы избежать слишком быстрого спуска в начале оптимизации, тем самым ограничивая шаги, доступные в будущих итерациях, и, следовательно, замедляя сходимость. Было показано, что увеличение в 2 раза и уменьшение в 3 раза является эффективным в большинстве случаев, в то время как для больших задач могут работать более экстремальные значения с увеличением в 1,5 раза и уменьшением в раз. из 5.

Геодезическое ускорение

При интерпретации шага Левенберга – Марквардта как скорости $vk\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{v\}\}\; \_\; \{k\}\}$вдоль геодезического пути в пространстве параметров, можно улучшить метод, добавив член второго порядка, который учитывает ускорение $ak\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{a\}\}\; \_\; \{k\}\}$вдоль геодезической

$vk\; +\; 1\; 2\; ak\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{v\}\}\; \_\; \{k\}\; +\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \{\backslash \; boldsymbol\; \{\; a\}\}\; \_\; \{k\}\}$

где $ak\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{a\}\}\; \_\; \{k\}\}$- решение

$J\; kak\; =\; -\; fvv.\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{J\}\}\; \_\; \{k\}\; \{\backslash \; boldsymbol\; \{a\}\}\; \_\; \{k\}\; =\; -\; f\_\; \{vv\}.\}$

Поскольку этот член геодезического ускорения зависит только от производной по направлению $fvv\; =\; \sum \; \mu \; \nu \; v\; \mu \; v\; \nu \; \partial \; \mu \; \partial \; \nu \; е\; (x)\; \{\backslash \; displaystyle\; f\_\; \{vv\}\; =\; \backslash \; sum\; \_\; \{\backslash \; mu\; \backslash \; nu\}\; v\; \_\; \{\backslash \; mu\}\; v\; \_\; \{\backslash \; nu\}\; \backslash \; partial\; \_\; \{\backslash \; mu\}\; \backslash \; partial\; \_\; \{\backslash \; nu\}\; f\; (\{\backslash \; boldsymbol\; \{x\}\})\}$по направлению скорости $v\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{v\}\; \}\}$, он не требует вычисления полной производной матрицы второго порядка, требуя лишь небольших накладных расходов с точки зрения затрат на вычисления. Поскольку производная второго порядка может быть довольно сложным выражением, может быть удобно заменить ее конечно-разностным приближением

$fvvi\; \approx \; fi\; (x\; +\; h\; \delta )\; -\; 2\; fi\; (x)\; +\; fi\; (Икс\; -\; час\; \delta )\; час\; 2\; знак\; равно\; 2\; час\; (fi\; (x\; +\; час\; \delta )\; -\; fi\; (x)\; час\; -\; J\; я\; \delta )\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; f\_\; \{vv\}\; ^\; \{i\}\; \backslash \; приблизительно\; \{\backslash \; frac\; \{f\_\; \{i\}\; (\{\backslash \; boldsymbol\; \{x\}\}\; +\; h\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\})\; -\; 2f\_\; \{i\}\; (\{\backslash \; boldsymbol\; \{x\}\})\; +\; f\_\; \{i\}\; (\{\backslash \; boldsymbol\; \{x\}\}\; -\; h\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\})\}\; \{h\; ^\; \{2\}\}\}\; \backslash \backslash \; =\; \{\backslash \; frac\; \{2\}\; \{h\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{f\_\; \{i\}\; (\; \{\backslash \; boldsymbol\; \{x\}\}\; +\; h\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\})\; -\; f\_\; \{i\}\; (\{\backslash \; boldsymbol\; \{x\}\})\}\; \{h\}\}\; -\; \{\backslash \; boldsymbol\; \{J\}\}\; \_\; \{i\}\; \{\; \backslash \; boldsymbol\; \{\backslash \; delta\}\}\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

где $f\; (x)\; \{\backslash \; displaystyle\; f\; (\{\backslash \; boldsymbol\; \{x\}\})\}$и $J\; \{\backslash \; displaystyle\; \{\backslash \; boldsymbol\; \{J\}\}\}$уже были вычислены алгоритмом, поэтому для вычисления требуется только одна дополнительная оценка функции $f\; (x\; +\; h\; \delta )\; \{\backslash \; displaystyle\; f\; (\{\backslash \; boldsymbol\; \{x\}\}\; +\; h\; \{\backslash \; boldsymbol\; \{\backslash \; delta\}\})\}$. Выбор шага конечных разностей $h\; \{\backslash \; displaystyle\; h\}$может повлиять на стабильность алгоритма, и значение около 0,1 обычно является разумным в целом.

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

$2\; \Vert \; ak\; \Vert \; \Vert \; vk\; \Vert \; \le \; \alpha \; \{\backslash \; Displaystyle\; \{\backslash \; frac\; \{2\; \backslash \; left\; \backslash \; |\; \{\backslash \; boldsymbol\; \{a\}\}\; \_\; \{k\}\; \backslash \; right\; \backslash \; |\}\; \{\backslash \; left\; \backslash \; |\; \{\backslash \; boldsymbol\; \{v\}\}\; \_\; \{k\}\; \backslash \; right\; \backslash \; |\}\}\; \backslash \; leq\; \backslash \; alpha\}$

где $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$обычно фиксируется на значение меньше 1, с меньшими значениями для более сложных задач.

Добавление члена геодезического ускорения может позволить значительно увеличить скорость сходимости, и это особенно полезно, когда алгоритм движется через узкие каньоны в ландшафте целевой функции, где разрешенные шаги меньше и выше точность из-за se Условие порядка дает существенные улучшения.

Плохое соответствие Лучшее соответствие Лучшее соответствие

В этом примере мы пытаемся учесть функцию $y\; =\; a\; cos\; \; (\; b\; X)\; +\; b\; sin\; \; (a\; X)\; \{\backslash \; displaystyle\; y\; =\; a\; \backslash \; cos\; \backslash \; left\; (bX\; \backslash \; right)\; +\; b\; \backslash \; sin\; \backslash \; left\; (aX\; \backslash \; right)\}$с использованием алгоритма Левенберга – Марквардта реализована в GNU Octave как функция leasqr. Графики показывают, что параметры $a\; =\; 100\; \{\backslash \; displaystyle\; a\; =\; 100\}$, $b\; =\; 102\; \{\backslash \; displaystyle\; b\; =\; 102\}$, использованные в исходной кривой, постепенно улучшаются. Только тогда, когда параметры на последнем графике выбраны наиболее близко к исходному, кривые точно соответствуют. Это уравнение является примером очень чувствительных начальных условий для алгоритма Левенберга – Марквардта. Одной из причин такой чувствительности является наличие нескольких минимумов - функция $cos\; \; (\beta \; x)\; \{\backslash \; displaystyle\; \backslash \; cos\; \backslash \; left\; (\backslash \; beta\; x\; \backslash \; right)\}$имеет минимумы при значении параметра $\beta \; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{\backslash \; beta\}\}\}$и $\beta \; ^\; +\; 2\; n\; \pi \; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{\backslash \; beta\}\}\; +\; 2n\; \backslash \; pi\}$.

• Доверительная область
• Метод Нелдера – Мида
• Для решения нелинейных систем уравнений также использовались варианты алгоритма Левенберга – Марквардта.

• Подробное описание алгоритма можно найти в Численные рецепты в C, Глава 15.5: Нелинейные модели
• C. Т. Келли, Итерационные методы оптимизации, 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 реализация включена)