Если преобразования в первом равенстве (5.7) не доводить до конца, то вместо (5.8) получим

В случае дважды дифференцируемой целевой функции мож­ но получить еще одно выражение для 7^. Так как матрица Гессе функции (Qx, х ) /2 + (с, х) совпадает с матрицей Q, то во вто­ ром равенстве (5.6) можно заменить Q матрицей Гессе Н(хк) неквадратичной целевой функции:

(.Н(хк)рк, wk+l)

Теперь с помощью одной из формул (5.8)-(5.10) из первого равенства (5.6), записанного в виде

на любой к-й итерации можно найти вектор, определяющий направление спуска из точки х к на (А;+1 )-й итерации. Для квадратичной функции результат вычислений по каждой из формул (5.8)-(5.10) будет одинаковым, но для неквадратичной функции значения 7^ будут, вообще говоря, различными. По­ этому использование каждой из этих формул при минимизации неквадратичной функции f(x) может привести к построению своей системы направлений спуска. При этом в отличие от ква­ дратичной функции точка минимума в общем случае не будет найдена за конечное число итераций.

Более того, при выборе значения щ > 0 на каждой А;-й итерации в рекуррентном соотношении х к = х к~1 + я^рк при­ ходится минимизировать функцию

Это приводит к неизбежным погрешностям на каждой итера­ ции, которые могут вызвать нарушение сходимости алгоритма. Чтобы ослабить влияние погрешностей, используют процедуру

„обновления" алгоритма, состояющую в том, что в (5.11) пе­ риодически через заданное число итераций полагают 7&= 0. Соответствующий номер итерации называют моментом об­ новления алгоритма, или рестартом. Обычно при мини­ мизации целевой функции в Шп множество таких номеров имеет вид Х0 = {п, 2п, ..., mn, ...}, т Е N. Использование в алгорит­ ме рестартов позволяет избежать накопления вычислительных погрешностей и уменьшить вероятность построения после ка­ ждых п итераций линейно зависимых направлений спуска, но приводит к росту общего числа итераций, необходимых для достижения заданной точности поиска.

Опишем алгоритм минимизации дифференцируемой неква­ дратичной целевой функции f{x). Выбираем параметр £3 > 0 точности поиска и начальную точку ж0 G Rn, в которой вы­ числяем антиградиент w l = —grad/(cc°). Убедившись, что |гс711 > £ 3, формируем множество TQ моментов обновления ал­ горитма, полагаем k = 1 , принимаем р1 = w 1 и переходим к основной части алгоритма.

1. Минимизируя функцию фк{х) (5.12), находим значение Кк и точку х к= х к~1+ ЯкРк. В этой точке вычисляем антигра­ диент wk+l = —grad/(a;fc) и проверяем выполнение неравенства \wk+1\< £3. Если оно выполнено, то итерации прекращаем и полагаем ж* « ж*” 1, /(ж*) « f ( x k~1). В противном случае пе­

щаемся к п. 1 . В противном случае переходим к п. 3.

3. При помощи (5.8) или (5.9) вычисляем значение 7к и, используя (5.11), находим вектор рЛ+1. Полагаем к : = к + 1 и возвращаемся к п. 1 .

Пример 5.5. Используем описанный алгоритм для поис­ ка минимума функции f(x 1,^2) = (ж? —Х2 )2 + (х\ —I)2, рассмо­ тренной в примере 5.2. Зададим параметр точности поиска £3 = 10“3 и начальную точку х° = (—1 , —2), в которой /(ж0) = = 13.

в