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

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

НайтиT⎛ ∂ f (x )∂ f (x ) ⎞⎟ .,...,градиент функции в произвольной точке ∇f ( x ) = ⎜⎜∂ x n ⎟⎠⎝ ∂ x1Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k< ε1 :а) если критерий выполнен, расчет закончен, x ∗ = x k ;б) если критерий не выполнен, то перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, то расчет окончен: x ∗ = x k ;б) если нет, то перейти к шагу 6.Шаг 6. Задать величину шага t k .( )Шаг 7. Вычислить x k +1 = x k − t k ∇f x k .Шаг 8.

Проверить выполнение условия() ( )f x k +1 − f x k < 0(или() ( )( )f x k +1 − f x k < − ε ∇f x k2):а) если условие выполнено, то перейти к шагу 9;tб) если условие не выполнено, положить t k = k и перейти к шагу 7.2Шаг 9. Проверить выполнение условийx k +1 − x k < ε 2 ,() ( )f x k +1 − f x k164< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) если хотя бы одно из условий не выполнено, положить k = k + 1 и перейти кшагу 3.Геометрическая интерпретация метода для n = 2 приведена на рис.

1.C1 > C 2 > C 3x2f ( x ) = C1x0− ∇f ( x 0 )x1x∗x2f (x ) = C3f (x ) = C 20x1Рис. 1Пример 1. Найти локальный минимум функции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 ) : ∇f (x )3 0 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 . Вычислим00T= 3,9 > 0,1 . Перейдем к шагу 5.5 0 . Проверим условие k ≥ M : k = 0 < 10 = M . Перейдем к шагу 6.6 0 . Зададим t 0 = 0,5 .7 0 . Вычислим x 1 : x 1 = (0,5;1) − 0,5(3; 2,5)T( )( )( )= ( −1;− 0,25) ; f x 1 = 2,31 .TT( ) ( )80 . Сравним f x 1 с f x 0 = 2 . Имеем f x 1 > f x 0 . Вывод: условие() ( )f x k +1 < f x k для k = 0 не выполняется. Зададим t 0 = 0,25 , перейдем к повторениюшагов 7, 8.7 01 .

Вычислим x 1 : x 1 = (0,5;1) − 0,25(3; 2,5)TT165( )= ( − 0,25; 0,375) ; f x 1 = 0,171 .T( )( )( ) ( )− x и f (x ) − f (x ) := 0,976 > 0,15 ;f (x ) − f (x ) = 1,829 > 0,15 .801 . Сравним f x 1 и f x 0 . Вывод: f x 1 < f x 0 . Перейдем к шагу 9.90 . Вычислим x 1x1 − x 001010Вывод: положим k = 1 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f ( x1 )31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,625; 0,51) .41 .

Вычислим1T= 0,81 > 0,1 . Перейдем к шагу 5.51 . Проверим условие k ≥ M : k = 1 < 10 = M . Перейдем к шагу 6.61 . Зададим t1 = 0,25 .71 . Вычислим x 2 : x 2 = ( − 0,25; 0,375) − 0,25 ( − 0,625; 0,5)TT( )= ( − 0,094; 0,25) ;Tf x 2 = 0,056 .( )( )( ) ( )− x и f (x ) − f (x ) := 0,2 > 0,15 ;f (x ) − f (x )81 . Сравним f x 2 с f x 1 . Вывод: f x 2 < f x 1 .

Перейдем к шагу 9.91 . Вычислим x 2x 2 − x112121= 0,115 < 0,15 .Вывод: положим k = 2 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )32 . Вычислим ∇f x 2 : ∇f x 2 = ( − 0,126; 0,406) .4 2 . Вычислим22T= 0,425 > 0,1 . Перейдем к шагу 5.5 2 . Проверим условие k ≥ M : k = 2 < 10 = M , перейдем к шагу 6.6 2 . Зададим t 2 = 0,25 .7 2 . Вычислим x 3 : x 3 = ( − 0,094; 0,25) − 0,25 ( − 0,126; 0,406)TT( )= ( − 0,063; 0,15) ;f x 3 = 0,021 .( )( )( ) ( )− x и f (x ) − f (x ) := 0,105 < 0,15 ;f (x ) − f (x ) = 0,035 < 0,15 .82 . Сравним f x 3 и f x 2 . Вывод: f x 3 < f x 2 .

Перейдем к шагу 9.92 . Вычислим x 3x3 − x223232Вывод: положим k = 3 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )33 . Вычислим ∇f x 3 : ∇f x 3 = ( − 0,102; 0,237) .43 . Вычислим33T= 0,257 > 0,1 . Перейдем к шагу 5.53 . Проверим условие k ≥ M : k = 3 < 10 = M , перейдем к шагу 6.63 . Зададим t3 = 0,25 .166T73 . Вычислим x 4 : x 4 = ( − 0,063; 0,15) − 0,25 ( − 0,102; 0,237)T( )T= ( − 0,038; 0,091) ;Tf x 4 = 0,0076 .( )( ) ( ) ( )9 .

Вычислим x − x , f (x ) − f (x ) :x − x = 0,064 < 0,15 ;f (x ) − f (x ) = 0,015 < 0,15 .) − f (x ) < ε выполнены при k = 2,3 . РасчетУсловияx−x <ε ,f (xокончен. Найдена точка x = ( − 0,038; 0,091) ; f ( x ) = 0,0076 .83 . Сравним f x 4 и f x 3 : f x 4 < f x 3 .344k +13433k4k +123k2T44II. Проведем анализ точки x 4 . Функция f ( x ) = 2 x12 + x1x 2 + x 2 2 является дваждыдифференцируемой, поэтому проведем проверку достаточных условий минимума в точке⎛ 4 1⎞x 4 .

Для этого проанализируем матрицу Гессе H = ⎜⎟ . Матрица является постоянной⎝ 1 2⎠и положительно определенной (т.е. H > 0 ), так как оба ее угловых минора Δ 1 = 4 иΔ 2 = 7 положительны. Следовательно, точка x 4 = ( − 0,038; 0,091)Tесть найденное при-( )ближение точки локального минимума x ∗ = (0,0) , а значение f x 4 = 0,0076 есть найT( )денное приближение значения f x ∗ = 0 .

„Б. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКААлгоритмШаг 1. Задать x 0 , ε1 > 0 , ε 2 > 0 , предельное число итераций M. Найти градиентT⎛ ∂ f (x )∂ f (x ) ⎞⎟ .функции в произвольной точке ∇f ( x ) = ⎜⎜,...,⎟xx∂∂1n ⎠⎝Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x kа) если критерий выполнен, то x ∗ = x k ;б) если критерий не выполнен, то перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, то x ∗ = x k ;б) если нет, то перейти к шагу 6.Шаг 6.

Вычислить величину шага t k∗ из условия(.( )) → mintϕ(t k ) = f x k − t k ∇f x kk167< ε1 :( )Шаг 7. Вычислить x k +1 = x k − t k∗ ∇f x k .Шаг 8. Проверить выполнение условий(x k +1 − x k < ε 2 ,) ( )f x k +1 − f x k< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) если хотя бы одно из условий не выполнено, то положить k = k + 1 и перейти кшагу 3.Геометрическая интерпретация метода для n = 2 приведена на рис.

2.C1 > C 2x2f ( x ) = C1x0− ∇f ( x 0 )x1f (x ) = C 2x1Рис. 2Пример 2. Найти локальный минимум функции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 ) : ∇f (x )30 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 . Вычислим00T= 3,9 > 0,1 . Перейдем к шагу 5.5 0 . Проверим условие k ≥ M : k = 0 < 10 = M , перейдем к шагу 6.6 0 . Следующую точку найдем по формулеx 1 = x 0 − t 0 ∇f ( x 0 ) = (0,5; 1)T − t 0 (3; 2,5)T = (0,5 − 3t 0 ; 1 − 2,5 ⋅ t 0 )T .168Подставим полученные выражения x11 = 0,5 − 3t 0 , x 21 = 1 − 2,5 ⋅ t 0 для координатв f ( x ) : ϕ(t 0 ) = 2 ⋅ (0,5 − 3t 0 ) 2 + (0,5 − 3t 0 ) ⋅ (1 − 2,5 ⋅ t 0 ) + (1 − 2,5 ⋅ t 0 ) 2 . Найдем минимумфункции ϕ(t 0 ) по t 0 с помощью необходимых условий безусловного экстремума:dϕ(t 0 )dt 0= 4 ⋅ (0,5 − 3t 0 ) ⋅ (−3) + (−3) ⋅ (1 − 2,5t 0 ) + (−2,5) ⋅ (0,5 − 3t 0 ) + 2 ⋅ (1 − 2,5 ⋅ t 0 ) ⋅ (−2,5) =d 2 ϕ(t 0 )∗= 63,25 > 0 , найденное знаdt 02чение шага обеспечивает минимум функции ϕ(t 0 ) по t 0 .Заметим, что можно получить формулу для вычисления наилучшей величины шага∗t k на любой итерации из условия= −15,25 + 63,25 ⋅ t 0 = 0 .

Отсюда t 0 ≅ 0,24 . Так как(.( )) → mintϕ(t k ) = f x k − t k ∇f x kИмеем( ) (∇f x k = 4 x1k + x 2k ; x1k + x 2k)Tk( ) [(2k1k2t k∗=)) + (x − t (4x + x ))(x+ ( x − t ( x + x )) .ϕ(t k ) = 2 x1k − t k (4 x1k + x 2k )Из условия((4 4 x1 + x 2)k 2(4 x1k(+ 2 4 x1Определим t 0∗ : t 0∗ = 0,24 .k12k1( )k2)− t k (x1k + x 2k ) ++ 2x 2 kkk+ 2x 2)) + 2 (x2T)k 2.k+ 2x 2T= ( − 0,22; 0,4) .17 0 . Найдем x 1 = x 0 − t 0∗ ∇f x 0 : x 1 = (0,5;1) − 0,24(3; 2,5)T( ) ( ):80 .

Вычислим x 1 − x 0 : x 1 − x 0 = 0,937 > 0,15 . Вычислим f x 1 − f x 0( ) ( )f x1 − f x 0= 1,83 > 0,15 . Вывод: положим k = 1 и перейдем к шагу 3.( ) ( )∇f (x ) = 0,752 > 0,1 .31 . Вычислим ∇f x 1 : ∇f x 1 = ( − 0,48; 0,58) .41 . ВычислимT151 . Проверим условие k ≥ M : k = 1 < 10 = M .61 . Определим t1∗ : t1∗ = 0,546 (см. п. 6 0 ).( )71 . Найдем x 2 = x 1 − t1∗ ∇f x 1 :x 2 = ( − 0,22; 0,4) − 0,546 ( − 0,48; 0,58)Tx 2 − x1= (0,04; 0,08) .TT( ) ( )= 0,41 > 0,15 ;f (x ) − f (x )81 . Вычислим x 2 − x 1 ,f x 2 − f x1 :2169)]2k12k2k2) + (x+ x )(x+ x2kkk1kkdϕ= 0 получаемdt kk(; x k − t k ∇f x k = x1k − t k 4 x1k + x 2k ; x 2k − t k x1k + x 2k1= 0,156 > 0,15 .T,Положим k = 2 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x )32 .

Вычислим ∇f x 2 : ∇f x 2 = (0,24; 0,2) .4 2 . Вычислим22T= 0,312 > 0,1 .5 2 . Проверим условие k ≥ M : k = 2 < 10 = M .6 2 . Определим t 2∗ : t 2∗ = 0,24 (см. п. 6 0 ).( )7 2 . Найдем x 3 = x 2 − t 2∗ ∇f x 2 :x 3 = (0,04; 0,08)− 0,24 (0,24; 0,2)T= ( − 0,0176; 0,032) .T( ) ( ):= 0,0749 < 0,15 ;f (x ) − f (x )82 . Вычислим x 3 − x 2 ,x3 − x2Tf x3 − f x232= 0,0116 < 0,15 .Положим k = 3 и перейдем к шагу 3.( ) ( )∇f (x ) : ∇f (x ), f ( x ) = 0,00127 .33 . Вычислим ∇f x 3 : ∇f x 3 = ( − 0,012; − 0,0816) .43 . Вычислим3x 3 = ( − 0,0176; 0,032)T3T= 0,082 < 0,1 . Расчет окончен.