2. Численные методы поиска безусловного экстремума. Методы первого и второго порядка (8 практических занятий с сайта кафеды 805)
Описание файла
Файл "2. Численные методы поиска безусловного экстремума. Методы первого и второго порядка" внутри архива находится в папке "8 практических занятий с сайта кафеды 805". PDF-файл из архива "8 практических занятий с сайта кафеды 805", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Занятие 2. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГОЭКСТРЕМУМА. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКА(продолжение занятия 1)Г. МЕТОД ФЛЕТЧЕРА–РИВСАПостановка задачиПусть дана функция 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 xf x2kk 12, f x k , f x k f x k 12k 1fx 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 2d10d 0x0x1Рис. 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 .T90 . Определим 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,58T0200 0,0373 3; 2,5T 0,368; 0,673 .T91 . Определим 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 26.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 .1k11kk б) если нет, то перейти к шагу 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 . Найдем граT4 1 .диент функции f ( x ) (4 x1 x 2 ; x1 2 x 2 )T и матрицу Гессе H x 1 22. Положим 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 16 0 .
Вычислим H x 0 : H x 0 . 1 21 2 7.7 0 . Вычислим H 1 x 0 :H 1 x 0 74 1 7 7 280 . Проверим выполнение условия H 1 x 0 0 . Так как 1 0 ,71 2 0 , то согласно критерию Сильвестра H 1 x 0 0 .71 2 3 17 .90 . Определим d 0 H 1 x 0 f x 0 7214 2,5 1 7 7 1 10 . Вычислим x ,12 01T 1 ,1 2T 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, 0Tесть точка локального минимума целевой функции 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. Проверить выполнение условия H x 0 :а) если условие выполняется, то найти d H x f x ;б) если нет, то положить d f x .Шаг 6. Вычислить элементы матрицы H x k .1k11kkkkkkШаг 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 . Найдем граT4 1 .диент функции f ( x ) (4 x1 x 2 ; x1 2 x 2 )T и матрицу Гессе H x 1 22. Положим 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 16 0 . Вычислим H x 0 : H x 0 . 1 2 27 0 . Вычислим H 1 x 0 : H 1 x 0 7 1 7 17.4 7 80 . Проверим выполнение условия H 1 x 0 0 .Так как 1 21 0, 2 0 , то согласно критерию Сильвестра H 1 x 0 0 .770Поэтому найдем d H1 x f x : d00T 1 , 1 (см.