1. Необходимые и достаточные условия безусловного экстремума. Численные методы поиска безусловного экстремума. Методы первого порядка (8 практических занятий с сайта кафеды 805)
Описание файла
Файл "1. Необходимые и достаточные условия безусловного экстремума. Численные методы поиска безусловного экстремума. Методы первого порядка" внутри архива находится в папке "8 практических занятий с сайта кафеды 805". PDF-файл из архива "8 практических занятий с сайта кафеды 805", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
ПРАКТИЧЕСКИЕ ЗАНЯТИЯЗанятие 1. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯБЕЗУСЛОВНОГО ЭКСТРЕМУМАПостановка задачиДана дважды непрерывно дифференцируемая функция f ( x) , определенная намножестве X R n .Требуется исследовать функцию f ( x) на экстремум, т.е. определить точки x R nее локальных минимумов и максимумов на R n :f ( x ) min f ( x) ;f ( x ) max f ( x) .xR nxR nСхема исследования функций на безусловный экстремумНеобходимые условия экстремумапервого порядкаДостаточные условияэкстремумаВычислить значения функциив точках экстремумаНет экстремумаНеобходимые условия экстремумавторого порядкаПродолжениеисследованийНет экстремумаНеобходимые условия экстремума первого порядка.
Пусть x R n есть точкалокального минимума (максимума) функции f ( x) на множестве R n и f ( x) дифференцируема в точке x . Тогда все частные производные функции f ( x) первого порядка вточке x равны нулю, т.е. f ( x ) 0, xi146i 1,..., n .Точки x , удовлетворяющие необходимому условию, называются стационарными.Рассмотрим определитель матрицы Гессе H ( x ) , вычисленной в стационарнойh11 h12 h1n h2 nhh.точке x * : det H ( x ) 21 22 hn1 hn 2 hnn1. Определители 1 h11 ,h 2 11h21h12,..., n h22h11 h1n называютсяhn1 hnnугловыми минорами.2. Определители m -го порядка ( m n ), получающиеся из определителя матрицыH ( x ) вычеркиванием каких-либо ( n m ) строк и ( n m ) столбцов с одними и темиже номерами, называются главными минорами.Первый способ проверки достаточных и необходимых условий второго порядка.Критерий проверки достаточных условий экстремума (критерий Сильвестра).Если знаки угловых миноров строго положительны:1 0 , 2 0 ,..., n 0 ,то точка x является точкой локального минимума.Если знаки угловых миноров чередуются, начиная с отрицательного:1 0 , 2 0 , 3 0 ,..., 1 n n 0,то точка x является точкой локального максимума.Критерий проверки необходимых условий экстремума второго порядка1.
Для того чтобы матрица Гессе H ( x ) была положительно полуопределенной( H ( x ) 0 ) и точка x может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры определителя матрицы Гессе были неотрицательны.2. Для того чтобы матрица Гессе H ( x ) была отрицательно полуопределенной( H ( x ) 0 ) и точка x может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны,а все главные миноры нечетного порядка – неположительны.Второй способ проверки достаточных и необходимых условий второго порядка(с помощью собственных значений матрицы Гессе).Собственные значения i , i 1,..., n , матрицы H ( x ) размеров n n находятсякак корни характеристического уравнения (алгебраического уравнения n -й степени):147h11 H ( x ) E h21h1nh22 h2nh12hn1hn 2 0. hnn Таблица1п/п1Второй способТип стационарной точки x 1 0,..., n 0Локальный минимум21 0,..., n 0Локальный максимум31 0,..., n 041 0,..., n 051 0,..., n 06 i имеют разныезнакиМожет быть локальный минимум,требуется дополнительное исследованиеМожет быть локальный максимум,требуется дополнительное исследованиеТребуется дополнительное исследованиеНет экстремумаПример 1.
Найти экстремум функции f x x12 x 22 x32 x1 x1 x 2 2 x3 намножестве R 3 . 1. Запишем необходимые условия экстремума первого порядка: f ( x) 2 x1 1 x2 0 , x1 f ( x) 2 x2 x1 0 , x2 f ( x) 2 x3 2 0 . x3T1 2В результате решения системы получим стационарную точку x , , 1 .3 32. Проверим выполнение достаточных условий экстремума.148 Первый способ. Матрица Гессе имеет вид H x1 2 0 , 2 2 1 0 1 2 0 . Так как 0 0 2 2 1 4 1 3 0 , 3 2 3 6 0 , т.е.
знаки угловых миноров1 2чередуются, начиная с отрицательного, то точка x – точка локального максимума.Второй способ. Найдем собственные значения матрицы Гессе:2 det H E 102 0.02 010Отсюда 2 [ (2 ) 2 1] 0 и 1 2 0, 2 1 0, 3 3 0 . Так как все собственные значения матрицы Гессе отрицательны, то в точке x – локальный максимум.43. Вычислим значение функции в точке локального максимума: f ( x ) .3322Пример 2.
Найти экстремум функции f ( x) x1 x 2 x 3 x 2 x3 3 x1 6 x 2 2на множестве R 3 . 1. Запишем необходимые условия экстремума первого порядка: f ( x) 3 x12 3 0 , x1 f ( x) 2 x2 x3 6 0 , x2 f ( x) 2 x3 x2 0 . x3В результате решения системы получим две стационарные точки:Tx1 1, 4, 2 ,Tx 2 1, 4, 2 .2. Проверим выполнение достаточных условий в 6 x1 0мя способами. Составим матрицу Гессе H ( x) 0 2 0 1TИсследуем точку x1 1, 4, 2 .149каждой стационарной точке дву01.2 Первый способ.
Матрица Гессе имеет вид6 0 0H (x ) 0 2 1 .0 1 21Так как6 01 6 0, 2 12 0, 3 18 0 , то точка x1 является точкой локального0 2минимума.Второй способ. Найдем собственные значения матрицы Гессе:60000221 6 2 1 0 .12Отсюда 1 6 0, 2 3 0, 3 1 0 и точка x1 является точкой локального минимума.TИсследуем точку x 2 1, 4, 2 .Первый способ. Матрица Гессе имеет вид 6 0 0H ( x ) 0 2 1 . Так как 0 1 226 0 12 0, 3 18 0 , то достаточные условия экстремума0 2не выполняются.
Согласно схеме (см. рис.) проверим необходимые условия экстремумавторого порядка. Главные миноры первого порядка ( m 1 ) получаются из6 0 01 6 0, 2 3 002 1 в результате вычеркивания n m 3 1 2 строк и 2 столбцов с одина1 2ковыми номерами: 6 , 2, 2. Главные миноры второго порядка ( m 2 ) получаются из 3 врезультате вычеркивания n m 3 2 1 строк и столбцов с одинаковыми номерами: 3, –12, –12. Главный минор третьего порядка ( m 3 ) получается из 3 в результате вычеркивания n m 3 3 0 строк и столбцов, т.е. совпадает с 3 18 .
Отсюда следует, чтонеобходимые условия экстремума второго порядка не выполняются. Так как матрицаГессе не является нулевой, то можно сделать вывод о том, что в точке x 2 нет экстремума.Второй способ. Найдем собственные значения матрицы Гессе:6 000210122 6 2 1 0 .Отсюда 1 6 0, 2 3 0, 3 1 0 , т.е. собственные значения имеют разные знаки.Поэтому в точке x 2 нет экстремума.3. Вычислим значение целевой функции в точке x1 локального минимума:f ( x1 ) 12 . 150ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГОЭКСТРЕМУМА. МЕТОДЫ ПЕРВОГО ПОРЯДКАПостановка задачиПусть дана функция 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 k151 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 )x1xx2f (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,53; 2,5T 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,253; 2,5TT152 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,5TT 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 .