10.2. Численное решение с помощью итеративных методов поиска

В обшем случае невозможно минимизировать функцию

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

Решение в этом случае можег быть получено с помощью итеративных численных методов. Существует обширная литература по численным задачам такого рода. Общие вопросы изложены, например, в работах Луенбергера [270], Бретсекаса [45] или Денниса и Шнабеля [97].

Численная минимизация. Методы численной минимизации функции пересчитывают оценку точки минимума итеративно. Обычно это делается в соответствии уравнением

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

1. Методы, использующие только значения функции.

2. Методы, использующие значения функции V, а также значения ее градиента.

3. Методы, использующие значения функции, ее градиента и гессиана (матрицу вторых производных).

Типичный представитель группы 3 соответствует алгоритмам Ньютона, в которых коррекция в (10.36) выбирается в ньютоновском направлении:

Наиболее важный подкласс группы 2 состоит из квазиньютоновских методов, которые формируют каким-либо образом оценку гессиана, а затем используют (10.37). Алгоритмы группы 1 либо формируют оценки градиента с помощью разностных аппроксимаций и действуют далее как квазиньютоновские методы, либо имеют другие специфические особенности поиска. (См. работу Пауэлла [328].)

Разработано множество стандартных программ, использующих эти идеи. Наиболее простым для пользователя средством идентификации могло бы быть наличие такой программы, снабженной соответствующей информацией, и предоставление поиска минимума самой программе. В любом случае необходимо иметь возможность вычисления значений функции (10.34) в требуемой точке 0. При этом основная трудность связана с вычислением ошибок предсказания . Эта задача сама по себе может быть как простой, так и сложной. Сравните, например, структуры моделей раздела 4.2 и примера 4.1.

Градиент функции (10.34) равен

Здесь, как обычно, -матрица градиента по 0. Основные вычислительные сложности в (10.38) связаны с нахождением последовательности . В разделе 10.3 обсуждаются способы вычисления для некоторых общих структур моделей. Однако для некоторых моделей прямые способы вычисления у могут быть запрещены, и тогда приходится обращаться к методам минимизации из группы 1 или формировать оценки с помощью разностных аппроксимаций. В работе Челлстрема, Эссебу и Острема [202] описан общий алгоритм идентификации такого типа.

Некоторые схемы поиска. Рассмотрим случай скалярной выходной величины и квадратичного критерия

В численном анализе эта задача известна как нелинейная задача наименьших квадратов. Великолепное пользующееся авторитетом рассмотрение этой задачи представлено в книге Денниса и Шнабели [97, гл. 10]. Критерий (10.39) имеет градиент

Тогда общее семейство процедур поиска задается в виде

где означает итерацию; -матрица, изменяющая направление поиска (она обсуждается ниже), а размер шага выбирается так, чтобы

Следует также помнить, что обычно задача минимизации содержит ограничения: Часто, однако, граница множества соответствует границе устойчивости предсказателя (ср. с определением 4.1), поэтому быстро возрастает при приближении 0 к При этом ограничение легко может быть учтено соответствующим выбором

Наиболее просто в качестве R взять единичную матрицу

при этом (10.41) становится градиентным методом, или методом наискорейшего спуска. Этот метод очень эффективен вблизи минимума; но обычно при этом лучше алгоритм Ньютона. Для (10.39) гессиан равен

где -матрица Гессе ошибки предсказания

Выбирая

получим из (10.41) метод Ньютона. Однако вычисление всех элементов может оказаться слишком дорогим. Допустим теперь, что существует такое значение при котором ошибки предсказания являются независимыми. Тогда это значение доставляет минимум Вблизи вторая сумма (10.44) будет при этом близка к нулю, поскольку Таким образом, имеем

При решении задачи минимизации методом Ньютона необходимо иметь хорошее приближение матрицы Гессе только в окрестности точки минимума. Это объясняется тем, что методы Ньютона обладают одношаговой сходимостью для квадратичных функций. Если значения функции в промежутке между текущей итерацией и точкой минимума не могут быть достаточно хорошо аппроксимированы квадратичной функцией, эффект от использования гессиана в (10.37) не столь важен. Более того, опуская последнюю сумму в (10.44), получаем такую оценку гессиана, которая всегда является положительно полуопределенной матрицей. Это делает численную процедуру алгоритмом спуска и гарантирует сходимость к стационарной точке. Таким образом, приходим к выводу, что

является очень удобным выбором для решения рассматриваемой задачи. Этот метод известен также как метод Гаусса - Ньютона. В литературе по статистике процедура получила название накопления” [335]. В литературе по управлению также используются термины: модифицированный метод Ньютона — Рафсона и метод квазилинеаризации. Деннис и Шнабель [97] использовали термин Гаусса - Ньютона

для (10.41) и (10.47) при и предложили термин метод Гаусса - Ньютона с затуханием в случае регулируемого размера шага

Несмотря на то, что выражение (10.46) всегда является положительно полуопределенным, оно может быть вырожденным или близким к вырождению. Например, это случаи перепараметризованной модели или недостаточно информативных данных. Тогда в (10.41) возникает ряд вычислительных трудностей. Известны различные способы преодоления этих трудностей, называемые методами регуляризации. Один общий способ представляет собой процедуру Левенберга - Марквардта [234, 278]. При этом в качестве аппроксимации гессиана используется

где — некоторое малое положительное число.

Если в точке минимума ошибки предсказания зависимые, проведенные рассуждения не верны. В этом случае вторая сумма в (10.44) не обязана быть пренебрежимо малой вблизи точки минимума, а (10.46) не обязательно является хорошим приближением гессиана. Тогда обычно используют известную первую сумму аппроксимации гессиана и оценивают вторую сумму методом секущей (см. [98]).

Корреляционное уравнение. Решение уравнения (10.35) полностью аналогично минимизации (10.34) (см., например, [97]). Стандартные численные процедуры представляют собой метод подстановки (соответствующий (10.41) и

и метод Ньютона - Рафсона (соответствующий (10.41) и