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

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

2. Провести анализ точки х _k с целью установить, является ли точка х_к найденным приближением решения задачи. Процедура анализа определяется на­личием у функции f (х) непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных условий минимума: матрица Гессе  Если  то точка х _k есть найденное приближение искомой точки х_*. Если , то следует провести проверку функции f (х) на выпук­лость в Q-окрестности точки х _k, используя критерий выпуклости для функций : функция f ( x ) выпукла (строго выпукла) в том и только в том случае, если . Если функция f ( x ) выпукла (строго вы­пукла), то х _k есть найденное приближение точки х_*.

Определение: Матрицей Гессе Н(х) дважды непрерывно дифференцируемой в точке х функции f ( x ) называется матрица частных производных второго порядка, вычисленной в данной точке:

,

где

Определители , , …,  называются угловыми минорами.

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

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

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

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

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

4⁰. Вычислим : = 3,9 > 0,1. Переходим к шагу 5.

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

6⁰. Зададим  = 0,5 .

7⁰. Вычислим х₁: х₁ = (0,5; 1)^T -0,5(3; 2,5)^T = (-1; -0,25)^T; f (х₁) = 2,31.

8⁰. Сравним f (х₁) с f (х₀) = 2. Имеем f (х₁) > f (х₀). Вывод: условие  для k = 0 не выполняется. Зададим  = 0,25, переходим к по­вторению шагов 7, 8.

7⁰¹. Вычислим х₁: х₁ = (0,5; 1)^T-0,25(3; 2,5)^T = (-0,25; 0,375)^T;  f (х₁) = 0,171.

8⁰¹. Сравним f (х₁) и f (х₀). Вывод: f ( x ₁ ) < f ( x ₀ ). Переходим к шагу 9.

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

=0,976 > 0,15; = 1,829 > 0,15.

Вывод: полагаем k =1 и переходим к шагу 3.

3¹. Вычислим : = (-0,625;0,51)^Т.

4¹. Вычислим :  = 0,81. Переходим к шагу 5.

5¹. Проверим условие : k = 1 < 10 = M. Переходим к шагу 6.

6¹. Зададим  = 0,25.

7¹. Вычислим х₂: х₂ = (-0,25; 0,375)^T - 0,25 (-0,625; 0,5)^T = (-0,094; 0,25)^T; f (х₂)  = 0,056.

8¹. Сравним f (х₂)  с f (х₁). Вывод: f (х₂) < f (х₁). Переходим к шагу 9.

9¹. Вычислим и :

= 0,2 > 0,15;   = 0,115 < 0,15.

Вывод: полагаем k = 2 и переходим к шагу 3.

3². Вычислим : = (-0,126; 0,406)^Т.

4². Вычислим : = 0,425 > 0,1. Переходим к шагу 5.

5². Проверим условие : k = 2 < 10 = М, переходим к шагу 6.

6². Зададим  =0,25.

7². Вычислим х₃: х₃ = (-0,094; 0,25)^T -0,25(-0,126; 0,406)^T = (-0,063;0,15)^T ; f (х₃)  = 0,021.

8². Сравним f (х₃)  и f (х₂) . Вывод: f (х₃)  < f (х₂).Переходим к шагу 9.

9². Вычислим  и :

= 0,105 < 0,15; = 0,035 < 0,15.

Вывод: полагаем k =3 и переходим к шагу 3.

3³. Вычислим : = (-0,102; 0,237)^T.

4³. Вычислим : = 0,257 > 0,1 . Переходим к шагу 5.

5³. Проверим условие : k = 3<10 = М, переходим к шагу 6.

6³. Зададим  = 0,25.

7³. Вычислим х₄: х₄ = (-0,063; 0,15)^T - 0,25(-0,102; 0,237)^T = (-0,038; 0,091)^Т; f (х₄) = 0,0076.

8³. Сравним f (х₄) и f (х₃): f (х₄) < f (х₃).

9³. Вычислим  и :

= 0,064 < 0,15; = 0,015 < 0,15.

Условия ,  выполнены при k = 2,3. Расчет окончен. Найдена точка х₄ = (-0,038; 0,091)^Т; f ( x ₄ ) = 0,0076.

На рис. 3 полученные точки соединены пунктирной линией.

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

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

Рис. 3

Матрица постоянна и является положительно определенной (т.е. H > 0) , так как оба ее угловых минора  = 4 и  = 7 положительны. Следовательно, точка х₄=(-0,038; 0,091)^T есть найденное приближение точки локального минимума х_* = (0,0)^T, а значение f ( x ₄ ) =0,0076 есть найденное приближение значения f ( x _* ) =0. Заметим, что условие H > 0, есть одновременно условие строгой выпуклости функции . Следовательно, х₄ = (-0,038; 0,091)^T, f ( x ₄ ) =0,0076 есть найден­ные приближения точки глобального минимума f ( x ) и ее наименьшего значе­ния на R ². ■