Алгоритм Гаусса-Ньютона используется для решения нелинейных наименьших квадратов проблем. Это модификация метода Ньютона для нахождения минимума в виде функции . В отличие от метода Ньютона, алгоритм Гаусса – Ньютона может использоваться только для минимизации суммы квадратов значений функции, но он имеет то преимущество, что вторые производные, которые может быть сложно вычислить, не требуются. [1]
Проблемы нелинейных наименьших квадратов возникают, например, в нелинейной регрессии , когда параметры в модели ищутся так, чтобы модель хорошо согласовывалась с имеющимися наблюдениями.
Метод назван в честь математиков Карла Фридриха Гаусса и Исаака Ньютона и впервые появился в работе Гаусса 1809 года Theoria motus corporum coelestium in sectionibus conicis solem ambientum . [2]
Описание
Для m функций r = ( r 1 ,…, r m ) (часто называемых остатками) от n переменных β = ( β 1 ,…, β n ) при m ≥ n алгоритм Гаусса – Ньютона итеративно находит значение переменные, минимизирующие сумму квадратов [3]
Начиная с первоначального предположения для минимума метод продолжается итерациями
где, если r и β - векторы-столбцы , элементы матрицы Якоби равны
и символ обозначает транспонирование матрицы .
Если m = n , итерация упрощается до
что является прямым обобщением метода Ньютона в одном измерении.
При подборе данных, где цель состоит в том, чтобы найти такие параметры β , чтобы данная модельная функция y = f ( x , β ) наилучшим образом соответствовала некоторым точкам данных ( x i , y i ), функции r i являются остатками :
Тогда метод Гаусса – Ньютона можно выразить через якобиан J f функции f как
Обратите внимание, что является левой Псевдообратный из.
Заметки
Предположение m ≥ n в формулировке алгоритма необходимо, поскольку в противном случае матрица J r T J r не обратима и нормальные уравнения не могут быть решены (по крайней мере, однозначно).
Алгоритм Гаусса – Ньютона может быть получен путем линейной аппроксимации вектора функций r i . Используя теорему Тейлора , мы можем писать на каждой итерации:
с участием . Задача найти Δ, минимизирующую сумму квадратов правой части; т.е.
является линейной задачей наименьших квадратов , которая может быть решена явно, давая нормальные уравнения в алгоритме.
Нормальные уравнения - это n одновременных линейных уравнений с неизвестными приращениями Δ. Они могут быть решены за один шаг, используя разложение Холецкого , или, лучше, с QR - разложение на J г . Для больших систем итерационный метод , такой как метод сопряженных градиентов , может быть более эффективным. Если существует линейная зависимость между столбцами J r , итерации не удастся, поскольку J r T J r становится сингулярным.
Когда сложный : C nC следует использовать конъюгированную форму:.
Пример
В этом примере алгоритм Гаусса – Ньютона будет использоваться для подгонки модели к некоторым данным путем минимизации суммы квадратов ошибок между данными и прогнозами модели.
В биологическом эксперименте, изучающем связь между концентрацией субстрата [ 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 после пятой итерации. График на рисунке справа показывает кривую, определенную моделью для оптимальных параметров с наблюдаемыми данными.
Свойства сходимости
Можно показать [4] , что приращение Δ является направлением спуска для S , и, если алгоритм сходится, то предел является стационарной точкой из S . Однако не гарантируется сходимость, даже локальная сходимость, как в методе Ньютона , или сходимость при обычных условиях Вульфа. [5]
Скорость сходимости алгоритма Гаусса – Ньютона может приближаться к квадратичной . [6] Алгоритм может сходиться медленно или не сходиться вообще, если первоначальное предположение далеко от минимума или матрицав плохом состоянии . Например, рассмотрим проблему с уравнения и переменная, заданная
Оптимум на . (На самом деле оптимум при для , так как , но .) Если , то фактически задача является линейной, и метод находит оптимум за одну итерацию. Если | λ | <1, то метод линейно сходится и погрешность уменьшается асимптотически с коэффициентом | λ | на каждой итерации. Однако если | λ | > 1, то метод даже не сходится локально. [7]
Вывод из метода Ньютона
В дальнейшем алгоритм Гаусса – Ньютона будет выведен из метода Ньютона для оптимизации функций с помощью аппроксимации. Как следствие, скорость сходимости алгоритма Гаусса – Ньютона может быть квадратичной при определенных условиях регулярности. В целом (при более слабых условиях) скорость сходимости линейна. [8]
Рекуррентное соотношение для метода Ньютона минимизации функции S параметров является
где г обозначает вектор градиента в S , а Н обозначает матрицу Гессе из S .
С , градиент определяется выражением
Элементы гессиана вычисляются путем дифференцирования элементов градиента, , относительно :
Метод Гаусса – Ньютона получается путем игнорирования членов второй производной (второй член в этом выражении). То есть гессиан аппроксимируется
где являются элементами якобиана J r . Градиент и приближенный гессиан можно записать в матричных обозначениях как
Эти выражения подставляются в приведенное выше рекуррентное соотношение, чтобы получить операционные уравнения
Сходимость метода Гаусса – Ньютона не гарантируется во всех случаях. Приближение
условие, которое необходимо соблюдать, чтобы иметь возможность игнорировать члены производной второго порядка, может быть справедливым в двух случаях, для которых следует ожидать сходимости: [9]
- Значения функции по величине невелики, по крайней мере, около минимума.
- Функции только "умеренно" нелинейны, так что относительно невелика по величине.
Улучшенные версии
В методе Гаусса – Ньютона сумма квадратов невязок S может не уменьшаться на каждой итерации. Однако, поскольку Δ - направление спуска, если только является стационарной точкой, справедливо для всех достаточно малых . Таким образом, если происходит расхождение, одним из решений является использование дроби вектора приращения Δ в формуле обновления:
- .
Другими словами, вектор приращения слишком длинный, но он по- прежнему указывает на «гору», так происходит только часть пути будет уменьшать целевую функцию S . Оптимальное значение дляможно найти с помощью алгоритма линейного поиска , то есть по величинеопределяется путем нахождения значения, которое минимизирует S , обычно с использованием метода прямого поиска в интервалеили поиск строки с возвратом, такой как поиск Armijo-line . Обычноследует выбирать так, чтобы он удовлетворял условиям Вульфа или Гольдштейна . [10]
В случаях, когда направление вектора сдвига таково, что оптимальная доля α близка к нулю, альтернативным методом обработки расхождения является использование алгоритма Левенберга – Марквардта , метода доверительной области . [3] Нормальные уравнения изменены таким образом, что вектор приращения поворачивается в направлении наискорейшего спуска ,
где D - положительная диагональная матрица. Обратите внимание, что когда D является единичной матрицей I и, тогда , поэтому направление Δ приближается к направлению отрицательного градиента.
Так называемый параметр Марквардта также может быть оптимизирован линейным поиском, но это неэффективно, так как вектор сдвига необходимо пересчитывать каждый раз изменено. Более эффективная стратегия заключается в следующем: Когда происходит дивергенция, увеличивают параметр Марквардта до тех пор , пока не будет уменьшение S . Затем сохраняйте значение от одной итерации к следующей, но уменьшайте его, если возможно, до достижения порогового значения, когда параметр Marquardt может быть установлен на ноль; минимизация S тогда становится стандартной минимизацией Гаусса – Ньютона.
Масштабная оптимизация
Для крупномасштабной оптимизации метод Гаусса – Ньютона представляет особый интерес, поскольку часто (хотя, конечно, не всегда) верно, что матрица более разреженный, чем приблизительный гессен. В таких случаях само пошаговое вычисление обычно необходимо выполнять с помощью приближенного итерационного метода, подходящего для больших и разреженных задач, такого как метод сопряженных градиентов .
Чтобы такой подход работал, нужен как минимум эффективный метод вычисления продукта.
для некоторого вектора p . При разреженном хранении матриц , как правило, практично хранить строкив сжатом виде (например, без нулевых записей), что затрудняет прямое вычисление вышеуказанного продукта из-за транспонирования. Однако, если определить c i как строку i матрицы, выполняется следующее простое соотношение:
так что каждая строка вносит дополнительный и независимый вклад в продукт. Помимо соблюдения практической структуры разреженной памяти, это выражение хорошо подходит для параллельных вычислений . Обратите внимание, что каждая строка c i является градиентом соответствующей невязки r i ; Имея это в виду, приведенная выше формула подчеркивает тот факт, что остатки вносят вклад в проблему независимо друг от друга.
Связанные алгоритмы
В квазиньютоновском методе , таком как метод Дэвидона, Флетчера и Пауэлла или Бройдена – Флетчера – Гольдфарба – Шанно ( метод BFGS ), оценка полного гессиана строится численно с использованием первых производных только так, чтобы после n циклов уточнения метод по своим характеристикам приближался к методу Ньютона. Обратите внимание, что квазиньютоновские методы могут минимизировать общие вещественные функции, тогда как методы Гаусса – Ньютона, Левенберга – Марквардта и т. Д. Подходят только для нелинейных задач наименьших квадратов.
Другой метод решения задач минимизации с использованием только первых производных - это градиентный спуск . Однако этот метод даже приближенно не учитывает вторые производные. Следовательно, это очень неэффективно для многих функций, особенно если параметры сильно взаимодействуют.
Заметки
- ^ Mittelhammer, Ron C .; Миллер, Дуглас Дж .; Судья Джордж Г. (2000). Эконометрические основы . Кембридж: Издательство Кембриджского университета. С. 197–198. ISBN 0-521-62394-4.
- ^ Floudas, Christodoulos A .; Пардалос, Панос М. (2008). Энциклопедия оптимизации . Springer. п. 1130. ISBN 9780387747583. CS1 maint: обескураженный параметр ( ссылка )
- ^ а б Бьорк (1996)
- ^ Бьорк (1996), стр. 260.
- ^ Маскаренхас (2013), "Расходимость BFGS и Гаусса методов Ньютона", математического программирования , 147 (1): 253-276, Arxiv : 1309.7922 , DOI : 10.1007 / s10107-013-0720-6
- ^ Бьорк (1996), стр. 341, 342.
- ^ Флетчер (1987), стр. 113.
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 04.08.2016 . Проверено 25 апреля 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ Nocedal (1999), стр. 259.
- ^ Нокедаль, Хорхе. (1999). Численная оптимизация . Райт, Стивен Дж., 1960-. Нью-Йорк: Спрингер. ISBN 0387227423. OCLC 54849297 .
Рекомендации
- Бьорк, А. (1996). Численные методы решения задач наименьших квадратов . СИАМ, Филадельфия. ISBN 0-89871-360-9.
- Флетчер, Роджер (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: Джон Вили и сыновья . ISBN 978-0-471-91547-8..
- Нокедаль, Хорхе; Райт, Стивен (1999). Численная оптимизация . Нью-Йорк: Спрингер. ISBN 0-387-98793-2.
Внешние ссылки
- Вероятность, статистика и оценка . Алгоритм подробно описан и применяется к биологическому эксперименту, обсуждаемому в качестве примера в этой статье (стр. 84 с неопределенностями в расчетных значениях).
Реализации
- Artelys Knitro - это нелинейный решатель с реализацией метода Гаусса – Ньютона. Он написан на C и имеет интерфейсы с C ++ / C # / Java / Python / MATLAB / R.