semopt3 (1013527)
Текст из файла
Занятие 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 . Расчет окончен.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
