7.4. Метод Левенберга-Марквардта

Суть этого широко используемого метода проста. При минимизации по методу Ньютона-Гаусса мы требовали невырожденность матрицы Иногда матрица становится настолько плохо обусловленной, что практически обратить ее невозможно. К. Левенберг [152] предложил такие матрицы «подправлять» следующим образом. Вместо рассмотрим матрицу Тогда матрица всегда невырождена и обратима. Итерационный процесс минимизации суммы квадратов отклонений в методе Левенберга строится по формуле

где Поскольку считаем, что матрица может быть вырождена, можно даже предположить зато Для всех Формула (7.30) имеет много общего с ридж-оценкой (6.27).

Рассмотрим условия сходимости процесса (7.30). Воспользуемся теоремой 7.2. Условие (7.23), очевидно, выполняется. В методе Левенберга что накладывает определенные ограничения на поправки Можно доказать, что если то метод Левенберга сходится (точнее, во всех предельных точках последовательности градиент равен нулю).

Обозначим поправку в методе Левенберга к предыдущему вектору параметров

Свойства этой поправки при изменении параметра приводятся в теореме 7.3.

Поскольку (7.30) является ридж-оценкой линеаризованной регрессии (7.18), оценка (7.30) дает минимальную сумму квадратов отклонений регрессии (7.18) в классе оценок с фиксированной длиной (см. параграф 6.4).

Теорема 7.3.

а) длина вектора поправки является убывающей функцией , при увеличении от до монотонно убывает от до 0;

б) является возрастающей функцией и при изменении от до изменяется от до 1;

в) является убывающей функцией и при изменении от до изменяется от 1 до

Доказательство этой теоремы дано в параграфе 7.8.

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

Д. Марквардт [158] предложил другую поправку для корректировки матрицы

где Марквардт корректирует диагональные элементы матрицы в зависимости от их величины. Метод Марквардта часто используется при минимизации суммы квадратов отклонений. Используя теорему 7.2, можно найти условия сходимости этого метода.

Остановимся теперь на стратегии выбора Градиентный метод хорошо работает в начале итерационного процесса, т. е. когда начальное приближение находится на достаточном расстоянии от минимизирующего вектора. Наоборот, метод Ньютона-Гаусса, как правило, быстро сходится в случае, когда приближение лежит в непосредственной близости к оценке МНК. Поэтому алгоритм, который на первых итерациях работал бы как градиентный метод, а в конце итерационного процесса — как метод Ньютона-Гаусса, вобрал бы в себя лучшие характеристики обоих процессов. При надлежащем выборе можно добиться того, чтобы методы Левенберга и Марквардта обладали этими свойствами. Действительно, пусть в начале процесса минимизации значения будут относительно большими, а в конце процесса — малыми. Марквардт, в частности, предложил следующую процедуру:

1) на нулевом шаге полагаем

2) на шаге полагаем

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

б) если то полагаем

В [22] приведена программа на Алголе метода Марквардта с описанной процедурой выбора

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

Для примера рассмотрим оценивание регрессии (7.5). В качестве положим оценку МНК логарифмированной регрессии (7.13). В табл. 7.1 показана минимизация методом Марквардта. Отметим медленную скорость сходимости, а также равномерное снижение значения Таким образом, .

Остановимся теперь на сравнении методов Ньютона-Гаусса и Хартли и методов Левенберга-Марквардта. Как показывает практика расчетов, методы второй группы являются более «осторожными». Для регрессий, в которых нелинейности не очень велики (к таким, в частности, относятся регрессии, линейные в логарифмах), методы Ньютона-Гаусса и Хартли сходятся быстрее методов второй

Таблица 7.1 (см. скан)

группы. Для регрессий же с высокой степенью нелинейности более предпочтительными оказываются методы второй группы. При этом их скорость сходимости невысока, зато методы Ньютона-Гаусса и Хартли вовсе расходятся.

Иногда ни один из описанных методов не приводит к оценке МНК. В частности, сходимость часто отсутствует в регрессиях с функцией

которая представляет собой производственную функцию с постоянной эластичностью замены [12].

Остановимся на вопросе окончания процесса счета. Практически счет может быть остановлен, когда выполняются следующие условия:

а) поправка вектора мала;

б) градиент близок к нулю.

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

На практике значения выбирают равными Практика автора показывает, что часто вычисления приходится выполнять с двойной точностью. Как правило, это происходит с «плохо идентифицируемыми» регрессиями, для которых .

Большое значение для скорости сходимости процессов минимизации имеет выбор начального вектора параметров. В [123], например, предлагается следующая общая

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

Решение этой системы примем в качестве начального приближения процесса минимизации. Однако такой метод имеет существенный недостаток. Решение системы (7.33) требует привлечения нелинейных итерационных методов, если не сводятся к линейным функциям некоторым преобразованием. Однако если функция регрессии сводится к линейной с помощью некоторого преобразования, то хорошее начальное приближение может быть получено другим путем (см. параграф 7.6). Если же «действительно» нелинейны, то задача решения системы (7.33) может оказаться сложнее исходной задачи минимизации

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

Упражнения 7.4

(см. скан)