Алгоритм Гаусса – Ньютона - Gauss–Newton algorithm

Аппроксимация зашумленной кривой с помощью модели асимметричного пика с использованием алгоритма Гаусса – Ньютона с переменным коэффициентом затухания α.
Вверху: исходные данные и модель.
Внизу: эволюция нормализованной суммы квадратов ошибок.

Алгоритм Гаусса-Ньютона используется для решения нелинейных наименьших квадратов проблем. Это модификация метода Ньютона для нахождения минимума в виде функции . В отличие от метода Ньютона, алгоритм Гаусса – Ньютона можно использовать только для минимизации суммы квадратов значений функции, но он имеет то преимущество, что вторые производные, которые может быть сложно вычислить, не требуются.

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

Метод назван в честь математиков Карла Фридриха Гаусса и Исаака Ньютона и впервые появился в работе Гаусса 1809 года Theoria motus corporum coelestium in sectionibus conicis solem ambientum .

Описание

Заданные функции (часто называемые остатками) переменных с алгоритмом Гаусса – Ньютона итеративно находят значение переменных, которое минимизирует сумму квадратов

Начиная с первоначального предположения о минимуме, метод переходит к итерациям.

где, если r и β - векторы-столбцы , элементы матрицы Якоби равны

а символ обозначает транспонирование матрицы .

Если m  =  n , итерация упрощается до

что является прямым обобщением метода Ньютона в одном измерении.

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

Тогда метод Гаусса – Ньютона можно выразить через якобиан функции как

Обратите внимание , что это левый Псевдообратный из .

Примечания

Предположение m  ≥  n в формулировке алгоритма необходимо, поскольку в противном случае матрица не обратима и нормальные уравнения не могут быть решены (по крайней мере, однозначно).

Алгоритм Гаусса – Ньютона может быть получен путем линейной аппроксимации вектора функций r i . Используя теорему Тейлора , мы можем писать на каждой итерации:

с . Задача найти минимизирующую сумму квадратов правой части; т.е.

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

Нормальные уравнения - это n одновременных линейных уравнений с неизвестными приращениями . Они могут быть решены за один шаг, используя разложение Холецкого , или, лучше, с QR - разложение с . Для больших систем итерационный метод , такой как метод сопряженных градиентов , может быть более эффективным. Если существует линейная зависимость между столбцами J r , итерации не пройдут, так как станет сингулярным.

Когда сложный сопряженная форма должна быть использована: .

Пример

Расчетная кривая, полученная с помощью и (синим цветом) в сравнении с наблюдаемыми данными (красным цветом)

В этом примере алгоритм Гаусса – Ньютона будет использоваться для подгонки модели к некоторым данным путем минимизации суммы квадратов ошибок между данными и прогнозами модели.

В биологическом эксперименте, изучающем связь между концентрацией субстрата [ S ] и скоростью реакции в ферментно-опосредованной реакции, были получены данные в следующей таблице.

я 1 2 3 4 5 6 7
[ S ] 0,038 0,194 0,425 0,626 1,253 2,500 3,740
Показатель 0,050 0,127 0,094 0,2122 0,2729 0,2665 0,3317

Требуется найти кривую (модельную функцию) вида

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

Обозначим через и значения [ S ] и ставки соответственно, с . Пусть и . Найдем и такое, что сумма квадратов остатков

сводится к минимуму.

Якобиан вектора невязок по неизвестным представляет собой матрицу с -й строкой, имеющей элементы

Начиная с начальных оценок и после пяти итераций алгоритма Гаусса – Ньютона получены оптимальные значения и . Сумма квадратов остатков уменьшилась с начального значения 1,445 до 0,00784 после пятой итерации. График на рисунке справа показывает кривую, определенную моделью для оптимальных параметров с наблюдаемыми данными.

Свойства сходимости

Можно показать , что приращение Δ является направлением спуска для S , и, если алгоритм сходится, то предел является стационарной точкой из S . Однако не гарантируется сходимость, даже локальная сходимость, как в методе Ньютона , или сходимость при обычных условиях Вульфа.

Скорость сходимости алгоритма Гаусса – Ньютона может приближаться к квадратичной . Алгоритм может медленно или не сходиться вообще , если начальное предположение далеко от минимума или матрица является плохо обусловленной . Например, рассмотрим задачу с уравнениями и переменной, заданной как

Оптимальный - при . (На самом деле оптимум находится на для , потому что , но .) Если , то проблема на самом деле линейная, и метод находит оптимум за одну итерацию. Если | λ | <1, то метод линейно сходится и погрешность уменьшается асимптотически с коэффициентом | λ | на каждой итерации. Однако если | λ | > 1, то метод даже не сходится локально.

Вывод из метода Ньютона

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

Рекуррентное соотношение для метода Ньютона минимизации функции S параметров имеет вид

где г обозначает вектор градиента в S , а Н обозначает матрицу Гессе из S .

Поскольку градиент определяется как

Элементы гессиана вычисляются путем дифференцирования элементов градиента , относительно :

Метод Гаусса – Ньютона получается путем игнорирования членов второй производной (второй член в этом выражении). То есть гессиан аппроксимируется

где - элементы якобиана J r . Градиент и приближенный гессиан можно записать в матричных обозначениях как

Эти выражения подставляются в приведенное выше рекуррентное соотношение, чтобы получить операционные уравнения

Сходимость метода Гаусса – Ньютона не гарантируется во всех случаях. Приближение

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

  1. Значения функции невелики по величине, по крайней мере, около минимума.
  2. Функции являются лишь «умеренно» нелинейными, поэтому их величина относительно невелика.

Улучшенные версии

В методе Гаусса – Ньютона сумма квадратов остатков S может не уменьшаться на каждой итерации. Однако, поскольку Δ - направление спуска, если не является стационарной точкой, это справедливо для всех достаточно малых . Таким образом, если происходит расхождение, одним из решений является использование части вектора приращения Δ в формуле обновления:

.

Другими словами, вектор приращения слишком длинный, но он по- прежнему указывает на «гору», так происходит только часть пути будет уменьшать целевую функцию S . Оптимальное значение для можно найти с помощью алгоритма поиска строки , то есть величина определяется путем нахождения значения, которое минимизирует S , обычно с использованием метода прямого поиска в интервале или поиска строки с возвратом, такого как поиск строки Armijo. . Обычно его следует выбирать так, чтобы он удовлетворял условиям Вульфа или условиям Гольдштейна .

В случаях, когда направление вектора сдвига таково, что оптимальная доля α близка к нулю, альтернативным методом обработки дивергенции является использование алгоритма Левенберга – Марквардта , метода доверительной области . Нормальные уравнения модифицируются таким образом, что вектор приращения поворачивается в направлении наискорейшего спуска ,

где D - положительная диагональная матрица. Обратите внимание, что когда D является единичной матрицей I и , следовательно, направление Δ приближается к направлению отрицательного градиента .

Так называемый параметр Марквардта также может быть оптимизирован с помощью линейного поиска, но это неэффективно, поскольку вектор сдвига необходимо пересчитывать каждый раз при изменении. Более эффективная стратегия заключается в следующем: Когда происходит дивергенция, увеличивают параметр Марквардта до тех пор , пока не будет уменьшение S . Затем сохраняйте значение от одной итерации к следующей, но уменьшайте его, если возможно, до достижения порогового значения, когда параметр Marquardt может быть установлен на ноль; минимизация S тогда становится стандартной минимизацией Гаусса – Ньютона.

Масштабная оптимизация

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

Чтобы такой подход работал, нужен как минимум эффективный метод вычисления продукта.

для некоторого вектора p . При хранении с разреженной матрицей , как правило, практично хранить строки в сжатом виде (например, без нулевых записей), что затрудняет прямое вычисление вышеуказанного произведения из-за перестановки. Однако, если определить c i как строку i матрицы , будет выполнено следующее простое соотношение:

так что каждая строка вносит аддитивный и независимый вклад в продукт. Помимо соблюдения практической структуры разреженной памяти, это выражение хорошо подходит для параллельных вычислений . Обратите внимание, что каждая строка c i является градиентом соответствующего остатка r i ; Имея это в виду, приведенная выше формула подчеркивает тот факт, что остатки вносят вклад в проблему независимо друг от друга.

Связанные алгоритмы

В квазиньютоновском методе , таком как метод Дэвидона, Флетчера и Пауэлла или Бройдена – Флетчера – Гольдфарба – Шанно ( метод BFGS ), оценка полного гессиана строится численно с использованием только первых производных, так что после n циклов уточнения По своим характеристикам метод близок к методу Ньютона. Обратите внимание, что квазиньютоновские методы могут минимизировать общие вещественные функции, тогда как методы Гаусса – Ньютона, Левенберга – Марквардта и т. Д. Подходят только для нелинейных задач наименьших квадратов.

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

Примечания

  1. ^ Mittelhammer, Ron C .; Миллер, Дуглас Дж .; Судья Джордж Г. (2000). Эконометрические основы . Кембридж: Издательство Кембриджского университета. С. 197–198. ISBN 0-521-62394-4.
  2. ^ Floudas, Christodoulos A .; Пардалос, Панос М. (2008). Энциклопедия оптимизации . Springer. п. 1130. ISBN 9780387747583.
  3. ^ а б Бьорк (1996)
  4. ^ Бьорк (1996), стр. 260.
  5. ^ Маскаренхас (2013), "Расходимость BFGS и Гаусса методов Ньютона", математического программирования , 147 (1): 253-276, Arxiv : 1309,7922 , DOI : 10.1007 / s10107-013-0720-6
  6. ^ Бьорк (1996), стр. 341, 342.
  7. ^ Флетчер (1987), стр. 113.
  8. ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 04.08.2016 . Проверено 25 апреля 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )
  9. ^ Nocedal (1999), стр. 259.
  10. ^ Нокедаль, Хорхе. (1999). Численная оптимизация . Райт, Стивен Дж., 1960-. Нью-Йорк: Спрингер. ISBN 0387227423. OCLC  54849297 .

использованная литература

внешние ссылки

  • Вероятность, статистика и оценка . Алгоритм подробно описан и применяется к биологическому эксперименту, обсуждаемому в качестве примера в этой статье (стр. 84 с неопределенностями в расчетных значениях).

Реализации

  • Artelys Knitro - это нелинейный решатель с реализацией метода Гаусса – Ньютона. Он написан на C и имеет интерфейсы с C ++ / C # / Java / Python / MATLAB / R.