semopt4 (Практические занятия)

Занятие 4. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГОЭКСТРЕМУМА. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКА(продолжение занятия 3)Г. МЕТОД ФЛЕТЧЕРА–РИВСАПостановка задачиПусть дана функция f ( x) , ограниченная снизу на множестве R n и имеющаянепрерывные частные производные во всех его точках.Требуется найти локальный минимум функции f ( x) на множестве допустимыхрешений X = R n , т.е. найти такую точку x ∗ ∈ R n , чтоf ( x ∗ ) = minn f ( x) .x∈ RАлгоритмШаг 1.

Задать x 0 , ε1 > 0 , ε 2 > 0 , M – предельное число итераций. Найти градиент ∇f (x ) .Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k< ε1 :а) если критерий выполняется, то расчет окончен и x ∗ = x k ;б) если нет, то перейти к шагу 5.Шаг 5. Проверить условие k ≥ M :а) если неравенство выполняется, то расчет окончен и x ∗ = x k ;б) если нет, то при k = 0 перейти к шагу 6, а при k ≥ 1 перейти к шагу 7.( )Шаг 6. Определить d 0 = − ∇f x 0 .Шаг 7. Определитьβ k −1 =( )∇f x(∇f x2kk −1)2,( ( )[ ( ) (( )⎡⎧ ∇f x k , ∇ f x k − ∇ f x k − 1⎢⎪2⎪k −1⎢β∇fx=⎨⎢ k −1⎪⎢⎪⎩ 0, k ∈ J⎢⎣( )Шаг 8.

Определить d k = − ∇f x k + β k −1 d k −1 .()Шаг 9. Найти t k∗ из условия ϕ(t k ) = f x k + t k d k → min .tkШаг 10. Вычислить x k +1 = x k + t k∗ d k .Шаг 11. Проверить выполнение условийx k +1 − x k < ε 2 ,175() ( )f x k +1 − f x k< ε2 :) ] ),⎤k ∉J⎥⎥.⎥⎥⎥⎦а) в случае выполнения обоих условий в двух последовательных итерациях с номерами k и k − 1 расчет окончен, найдена точка x * = x k +1 ;б) если не выполняется хотя бы одно из условий, положить k = k + 1 и перейтик шагу 3.Геометрическая интерпретация метода для n = 2 изображена на рис. 4.x2x0− ∇f ( x 1 )x1C1 > C 2f ( x) = C1d 0 = −∇f ( x 0 )f ( x) = C 2d1β0d 0x∗0x1Рис. 4Пример 4.

Найти локальный минимум функции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ент функции в произвольной точке ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T .2.

Положим k = 0 .( )( )∇f (x )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 . Проверим условиеT0< ε1 :( )∇f x 0= 3,9 > 0,1 .5 0 . Проверим условие k ≥ M : k = 0 < 10 = M .( )6 0 . Определим d 0 = − ∇f x 0 : d 0 = − (3; 2,5) .T()90 . Определим t 0∗ из условия f x 0 + t 0 d 0 → min : t 0∗ = 0,24 (см.

пример 2, такt0как первая итерация выполняется по методу наискорейшего спуска).100 . Вычислим x 1 = x 0 + t 0∗ d 0 : x 1 = ( − 0,22; 0,4) .T110 . Проверим условия x 1 − x 0 < ε 2 ,176( ) ( )f x1 − f x 0< ε2 :( ) ( )x 1 − x 0 = 0,937 > 0,15 ;f x1 − f x 0= 0,17 − 2 = 1,83 > 0,15 .Положим k = 1 и перейдем к шагу 3.( )( )∇f (x )31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,48; 0,58) .41 . Проверим условие1T( )∇f x 1< ε1 := 0,752 > 0,1 .51 . Проверим условие k ≥ M : k = 1 < 10 = M .71 . Определим β 081 . Определим d 1( ): β = 0,0373 .=∇f (x )= − ∇f (x ) + β d :∇f x 1021d 1 = − ( − 0,48; 0,58)T0200− 0,0373 (3; 2,5)T(= ( 0,368; − 0,673) .T)91 .

Определим t1∗ из условия f x 1 + t1 d 1 → min . Воспользуемся формулойt1x 2 = x 1 + t1 d 1 = (− 0,22; 0,4)T + t1 (0,368 ; − 0,673)T = (− 0,22 + 0,368 t1 ; 0,4 − 0,673 t1 )T .Подставляя полученное выражение в f ( x ) , имеемϕ(t1 ) = 2 ⋅ (− 0,22 + 0,368 t1 ) 2 + (− 0,22 + 0,368 t1 ) ⋅ (0,4 − 0,673 t1 ) + (0,4 − 0,673 t1 ) 2 .Применяя необходимое условие безусловного экстремумаd ϕ(t1 )= 4 ⋅ (− 0,22 + 0,368 t1 ) ⋅ 0,368 + 0,368 ⋅ (0,4 − 0,673 t1 ) +d t1+ (− 0,22 + 0,368 t1 ) ⋅ (−0,673) + 2 ⋅ (0,4 − 0,673 t1 ) ⋅ (− 0,673) = 0 ,находим t1∗ ≅ 0,595 . Посколькуd 2 ϕ(t1 )d t1 2печивает минимум функции ϕ(t1 ) по t1 .= 0,952226 > 0 , найденное значение шага обес-101 .

Вычислим x 2 = x 1 + t1∗ d 1 : x 2 = (0,0010; 0,000) .T( ) ( ) <ε :f (x ) − f (x ) = 0,17 > 0,15 .111 . Проверим условия x 2 − x 1 < ε 2 ,x 2 − x 1 = 0,456 > 0,15 ;f x 2 − f x1221Положим k = 2 и перейдем к шагу 3.( )4 . Проверим условие ∇f ( x ) < ε :Найдена точка x = (0,001; 0) ; f ( x ) = 2 ⋅ 10( )32 .

Вычислим ∇f x 2 : ∇f x 2 = ( 0,003; 0,006) .222T12177T( ) = 0,0067 < 0,1 . Расчет окончен.∇f x 2−6.II. Проведем анализ точки x 2 . Функция f ( x ) = 2 x12 + x1x 2 + x 2 2 есть квадратичная функция двух переменных, имеющая положительно определенную матрицу⎡4 1 ⎤вторых производных H = ⎢⎥ . Это позволяет сделать вывод, что функция f ( x )⎣1 2⎦имеет единственный минимум, приближение которого x 2 = (0,001; 0)итерации. ■Tнайдено за двеМЕТОДЫ ВТОРОГО ПОРЯДКАА. МЕТОД НЬЮТОНААлгоритмШаг 1.

Задать x 0 , ε1 > 0, ε 2 > 0 , M – предельное число итераций. Найти градиент ∇f (x ) и матрицу Гессе H (x ) .Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k≤ ε1 :а) если неравенство выполнено, то расчет окончен и x ∗ = x k ;б) в противном случае перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, расчет окончен и x ∗ = x k ;б) если нет, перейти к шагу 6.( )Шаг 7.

Найти обратную матрицу H ( x ) .Шаг 8. Проверить выполнение условия H ( x ) > 0 :а) если H ( x ) > 0 , то перейти к шагу 9;Шаг 6. Вычислить элементы матрицы H x k .−1k−1−1kk( )б) если нет, то перейти к шагу 10, положив d k = −∇f x k .( ) ( )Шаг 9. Определить d k = − H −1 x k ∇f x k .Шаг 10. Найти точку x k +1 = x k + t k d k ,( ) ( )) < f (x ) , если dположив t k = 1 , если d k = − H −1 x k ∇f x k ,(или выбрав t k из условия f x k +1kШаг 11. Проверить выполнение условийx k +1 − x k < ε 2 ,(k( )= −∇f x k .) ( )f x k +1 − f x k< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) в противном случае положить k = k + 1 и перейти к шагу 3.178Пример 5.

Найти локальный минимум функции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 .( )( )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.5 0 . Проверим выполнение условия k ≥ M : k = 0 < 10 . Перейдем к шагу 6.⎛ 4 1⎞6 0 . Вычислим H x 0 : H x 0 = ⎜⎟.⎝ 1 2⎠1⎞⎛ 2− ⎟⎜7⎟.7 0 . Вычислим H −1 x 0 :H −1 x 0 = ⎜ 7⎜− 1 4 ⎟⎜⎟⎝ 7 7 ⎠280 . Проверим выполнение условия H −1 x 0 > 0 . Так как Δ 1 = > 0 ,71Δ 2 = > 0 , то согласно критерию Сильвестра H −1 x 0 > 0 .71⎞⎛ 2− ⎟⎛ 3 ⎞ ⎛ 1⎞⎜7 ⎟ ⎜ ⎟ = ⎜− ⎟ .90 .

Определим d 0 = − H −1 x 0 ∇f x 0 = − ⎜ 7214⎟ ⎜⎝ 2,5 ⎟⎠ ⎜⎜ − 1 ⎟⎟⎜−⎜⎟⎝⎠⎝ 7 7 ⎠( ) ( )( )( )( )( )( ) ( )⎛1 ⎞10 . Вычислим x = ⎜ ,1⎟⎝2 ⎠01T⎛ 1⎞+ ⎜ − ,−1⎟⎝ 2⎠T= (0, 0) .T110 . Проверим выполнение условий x 1 − x 0 < ε 2 ,( ) ( )f x1 − f x 0< ε2 :( ) ( ) = 2 > 0,15 . Положим k = 1 и перейдем к шагу 3.3 .

Вычислим ∇f ( x ) : ∇f ( x ) = (0, 0) .x1 − x 0 = 1,12 > 0,15; f x1 − f x 0111T( )41 . Проверим выполнение условия ∇f x 1( )< ε1 : ∇f x 1= 0 < 0,1 . Расчетокончен. Заметим, что в точке x 1 выполняется необходимое условие первого порядка,поэтому она является стационарной точкой.II. Проведем анализ точки x 1 . Для функции f ( x ) = 2 x12 + x1x 2 + x 2 2 матрица⎛ 4 1⎞вторых производных H = ⎜⎟ > 0 в силу того, что Δ 1 = 4 > 0, Δ 2 = 7 > 0 . Поэто⎝ 1 2⎠му точка x 1 = (0, 0)Tесть точка локального минимума целевой функции f ( x ) .

„179Б. МЕТОД НЬЮТОНА–РАФСОНААлгоритмШаг 1. Задать x 0 , ε1 > 0, ε 2 > 0 , M – предельное число итераций. Найти градиент ∇f (x ) и матрицу Гессе H (x ) .Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение условия ∇f x k≤ ε1 :а) если неравенство выполнено, то расчет закончен и x ∗ = x k ;б) если нет, перейти к шагу 5.Шаг 5. Проверить выполнение условия k ≥ M :а) если неравенство выполнено, расчет окончен и x ∗ = x k ;б) если нет, перейти к шагу 6.( )Шаг 7. Найти обратную матрицу H ( x ) .Шаг 8.