Процедура решения задачи

1. Используя алгоритм Ньютона, найти точку х _k, в которой выполняется по крайней мере один критерий окончания расчета.

2. Так как , то осуществить проверку выполнения достаточных

условий минимума > 0. Если условие выполнено, то точка х _k может рас­сматриваться как найденное приближение точки минимума х_*. Проверку вы­полнения достаточных условий минимума можно заменить проверкой функции f ( x ) на выпуклость.

Пример 2.1. Найти локальный минимум функции

.

□ I. Определение точки х _k, в которой выполняется по крайней мере один критерий окончания расчетов.

1. Зададим х₀,  М:  х₀ = (0,5; 1)^Т, ; М=10. Найдем градиент функции в произвольной точке  и матрицу Гессе .

2. Положим k = 0.

3⁰. Вычислим : = (3; 2,5)^Т.

4⁰. Проверим выполнение условия : = 3,9 > 0,1.

Переходим к шагу 5.

5⁰. Проверим выполнение условия : k = 0 <10. Переходим к шагу 6.

6⁰. Вычислим : .

7⁰. Вычислим : .

8⁰. Проверим выполнение условия >0. Так как , , то согласно критерию Сильвестра > 0.

9⁰. Определим .

10⁰. Вычислим .

11⁰. Проверим выполнение условий , :

 = 1,12 > 0,15; = 2>0,15.

Полагаем k = 1, переходим к шагу 3.

3¹. Вычислим : = (0,0)^T.

4¹. Проверим выполнение условия : = 0 <0,1. Расчет окончен. Заметим, что в точке х₁ выполняется необходимое условие первого по­рядка, поэтому она является стационарной точкой.

II. Анализ точки х₁.

Функция    является строго выпуклой, так как ее матрица вторых производных  в силу того, что , .

Найденная точка х₁ =(0,0)^T есть точка локального и одновременно глобального минимума f (х).

Рис. 9

 На рис. 9 траектория спуска изображена сплошной линией. ■

Метод Ньютона-Рафсона

Стратегия поиска

Стратегия метода Ньютона-Рафсона [Newton-Raphson] состоит в построении последова­тельности точек {х _k}, k = 0,1,..., таких, что  k = 0,1,.... Точки последовательности вычисляются по правилу

                     (7)

где х₀ задается пользователем; величина шага  определяется из условия

.                   (8)

Задача (7.5) может решаться либо аналитически с использованием необхо­димого условия минимума  с последующей проверкой достаточного условия , либо численно как задача

                                  (9)

где интервал [a , b]задается пользователем.

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

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

Построение последовательности {х _k} заканчивается в точке х _k, для кото­рой , где  - заданное число, или при (М - предельное чис­ло итераций), или при двукратном одновременном выполнении двух неравенств , , где  - малое положительное число.

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

Сходимость

Утверждение.  Пусть функция f ( x ) дважды непрерывно дифференцируема и сильно выпукла на Rⁿ , а ее матрица Гессе Н(х) удовлетворяет условию Липшица

.

Тогда последовательность {х _k } сходится независимо от выбора начальной тонки х₀ к точке минимума х_* с квадратичной скоростью

,

где т - оценка наименьшего собственного значения матрицы.

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

а) анализировать матрицу Гессе  на выполнение условия >0, k= 0,1,..., и заменять формулу  на форму­лу метода градиентного спуска  в случае его невыполнения;

б) производить анализ точки х _k с целью выяснения, является ли она най­денным приближением искомой точки х_*.