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

Геометрическая интерпретация метода для п =2приведена на рис. 2.

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

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. Анализ точки х₄.

Функция

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