Методы оптимизации (стр. 9 из 11)

Рис. 8

Построение последовательности {х_k} заканчивается в точке х_k, для которой

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

Сходимость

Утверждение. Пусть f(x) дважды непрерывно дифференцируемая сильновыпуклая функция с константой l > 0 на Rⁿ и удовлетворяет условию

,

где L > 0, а начальная точка такова, что

, т.е.

,

где

.. Тогда последовательность {x^k} сходится к точке минимума с квадратичной скоростью

.

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

, практическое использование которого крайне затруднено, так как постоянные l и L, как правило, неизвестны или требуют трудоемкого исследования для их определения. Поэтому при практическом использовании метода Ньютона следует:

а) анализировать матрицу Н(х_k)на выполнение условия Н(х_k) < 0

и заменять формулу на формулу в случае его невыполнения;

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

Замечание 2.При решении задачи поиска безусловного максимума формула (6) не изменяется, так как в этом случае Н(х_k) < 0.

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

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 траектория спуска изображена сплошной линией. ■

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

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

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

k= 0,1,.... Точки последовательности вычисляются по правилу

(7)

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

определяется из условия

.(8)

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

с последующей проверкой достаточного условия , либо численно как задача