semopt4 (1013528), страница 2
Текст из файла (страница 2)
Проверить выполнение условия H ( x ) > 0 :а) если условие выполняется, то найти d = − H ( x ) ∇f ( x ) ;б) если нет, то положить d = −∇f ( x ) .Шаг 6. Вычислить элементы матрицы H x k .−1k−1−1kkkkkkШаг 9. Определить x k +1 = x k + t k d k .()Шаг 10. Найти шаг t k∗ из условия ϕ(t k ) = f x k + t k d k → min .tkШаг 11.
Вычислить x k +1 = x k + t k∗ d k .Шаг 12. Проверить выполнение неравенствx k +1 − x k() ( )f x k +1 − f x k< ε2,< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен и x ∗ = x k +1 ;б) в противном случае положить k = k + 1 и перейти к шагу 3.Пример 6. Найти локальный минимум функции f ( x ) = 2 x12 + x1x 2 + x 2 2 . I.
Определим точку x k , в которой выполняется по крайней мере один критерий окончания расчетов.1. Зададим x 0 , ε1 , ε 2 , M : x 0 = (0,5;1) , ε1 = 0,1; ε 2 = 0,15; M = 10 . Найдем граT⎛4 1⎞⎟⎟ .диент функции ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T и матрицу Гессе H (x ) = ⎜⎜⎝1 2⎠2. Положим k = 0 .180( )( )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .T( )4 0 .
Проверим выполнение условия ∇f x 0≤ ε1 :( )∇f x 0= 3,9 > 0,1 .5 0 . Проверим выполнение условия k ≥ M : k = 0 < 10 . Перейдем к шагу 6.( )( )⎛ 4 1⎞6 0 . Вычислим H x 0 : H x 0 = ⎜⎟.⎝ 1 2⎠⎛ 2⎜7 0 . Вычислим H −1 x 0 : H −1 x 0 = ⎜ 7⎜− 1⎜⎝ 7( )( )1⎞⎟7⎟.4 ⎟⎟7 ⎠−( )80 . Проверим выполнение условия H −1 x 0 > 0 .Так как Δ 1 =( )21> 0, Δ 2 = > 0 , то согласно критерию Сильвестра H −1 x 0 > 0 .770Поэтому найдем d = −H−1( x ) ∇f ( x ) : d00T⎛ 1⎞= ⎜ − ,− 1 ⎟ (см.
шаг 90 примера 5).⎝ 2⎠0T0109 . Определим: x = x + t 0 d0T⎞⎛ 1⎛1 ⎞= ⎜⎜ , 1⎟⎟ + t 0 ⎜⎜ − , − 1 ⎟⎟⎠⎝ 2⎝2 ⎠T⎞⎛1 1= ⎜⎜ − t 0 ,1 − t 0 ⎟⎟ .⎠⎝2 2100 . Определим t 0∗ из условия ϕ(t 0 ) = f ( x 0 + t 0 d 0 ) → min . Получимt0T⎛⎛ 1 1⎞⎜⎟⎜f ( x + t0 d ) = f ⎜ − t0 ,1 − t0 ⎟⎜ 2 2⎠⎝⎝00⎞⎟=⎟⎠2⎛1 1 ⎞⎛1 1 ⎞= 2 ⋅ ⎜⎜ − t0 ⎟⎟ + ⎜⎜ − t0 ⎟⎟ ⋅ (1 − t0 ) + (1 − t0 )2 = 2 ⋅ (1 − t0 )2 = ϕ(t0 ).⎝2 2 ⎠⎝2 2 ⎠dϕd 2ϕИз условия= 2 ⋅ 2 ⋅ (1 − t 0 ) ⋅ (−1) = 0 находим t 0∗ = 1 . При этом= 4 > 0 , т.е.dt 0d t 02найденная величина шага обеспечивает минимум функции ϕ(t 0 ) .01011 . Вычислим x = x +t0∗ d 0 :T⎞⎛1 1x = ⎜⎜ − ⋅ 1 , 1 − 1⎟⎟⎠⎝2 2112 0 .
Проверим выполнение условийx1 − x 0x1 − x 0< ε2,( ) ( )= 1,12 > 0,15 ;= (0, 0 )T .( ) ( )f x1 − f x 0f x1 − f x 0= 2 > 0,15 .( )∇f x 1< ε2 :Положим k = 1 и перейдем к шагу 3.( )( )31 . Bычислим ∇f x 1 : ∇f x 1 = (0;0 )T .41 . Проверим выполнение условия∇f x 1< ε1 :( )= 0 < 0,1 . Расчетокончен: x ∗ = x 1 .II. Проведем анализ точки x 1 .
Точка x ∗ = (0;0 )T – точка локального и одновременно глобального минимума f ( x ) (см. пример 5). 181.