semopt1 (Практические занятия)
Описание файла
Файл "semopt1" внутри архива находится в папке "Практические занятия". PDF-файл из архива "Практические занятия", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 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) .x∈R nx∈R nСхема исследования функций на безусловный экстремумНеобходимые условия экстремумапервого порядкаДостаточные условияэкстремумаВычислить значения функциив точках экстремумаНет экстремумаНеобходимые условия экстремумавторого порядкаПродолжениеисследованийНет экстремумаНеобходимые условия экстремума первого порядка. Пусть x ∗ ∈ R n есть точкалокального минимума (максимума) функции f ( x) на множестве R n и f ( x) дифференцируема в точке x ∗ .
Тогда все частные производные функции f ( x) первого порядка вточке x ∗ равны нулю, т.е.∂ f ( x∗ )= 0,∂ xi146i = 1,..., n .Точки x ∗ , удовлетворяющие необходимому условию, называются стационарными.Рассмотрим определитель матрицы Гессе H ( x∗ ) , вычисленной в стационарнойh11 h12h1nhhh2n.точке x * : det H ( x∗ ) = 21 22hn1hn 2hnn1.
Определители Δ1 = h11 ,hΔ 2 = 11h21h12,..., Δ n =h22h11h1nназываютсяhn1hnnугловыми минорами.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 -й степени):147H ( x∗ ) − λE =h11 − λh12h1nh21h22 − λh2nhn1hn 2= 0.… hnn − λТаблица1п/п1Второй способТип стационарной точки x ∗λ1 > 0,..., λ n > 0Локальный минимум2λ1 < 0,..., λ n < 0Локальный максимум3λ1 ≥ 0,..., λ n ≥ 04λ1 ≤ 0,..., λ n ≤ 05λ1 = 0,..., λ n = 06λ i имеют разныезнакиМожет быть локальный минимум,требуется дополнительное исследованиеМожет быть локальный максимум,требуется дополнительное исследованиеТребуется дополнительное исследованиеНет экстремумаПример 1.
Найти экстремум функции f ( x ) = − x12 − x 22 − x 32 − 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 ⎠⎝ 3∗2. Проверим выполнение достаточных условий экстремума.148( )Первый способ. Матрица Гессе имеет вид H xΔ1 = −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 ) =10−2 − λ= 0.0−2 − λ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 x 3 − 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 1⎝TИсследуем точку x1∗ = (1, − 4, 2 ) .149каждой стационарной точке дву0⎞⎟1⎟.2 ⎟⎠Первый способ. Матрица Гессе имеет вид⎛6 0 0⎞⎜⎟H (x ) = ⎜ 0 2 1 ⎟ .⎜0 1 2⎟⎝⎠1∗Так как6 0Δ1 = 6 > 0, Δ 2 == 12 > 0, Δ 3 = 18 > 0 , то точка x1∗ является точкой локального0 2минимума.Второй способ. Найдем собственные значения матрицы Гессе:6−λ000022−λ1= ( 6 − λ ) ⎡ ( 2 − λ ) − 1⎤ = 0 .⎥⎦⎣⎢12−λОтсюда λ1 = 6 > 0, λ 2 = 3 > 0, λ 3 = 1 > 0 и точка x1∗ является точкой локального минимума.TИсследуем точку x 2∗ = ( −1, − 4, 2 ) .Первый способ.
Матрица Гессе имеет вид⎛− 6 0 0⎞⎜⎟H ( x ) = ⎜ 0 2 1 ⎟ . Так как⎜ 0 1 2⎟⎝⎠2∗−6 0= −12 < 0, Δ 3 = −18 < 0 , то достаточные условия экстремума0 2не выполняются. Согласно схеме (см. рис.) проверим необходимые условия экстремумавторого порядка. Главные миноры первого порядка ( m = 1 ) получаются из−6 0 0Δ1 = − 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 − λ0002−λ1012−λ2= ( −6 − λ ) ⎡ ( 2 − λ ) − 1 ⎤ = 0 .⎢⎣⎥⎦Отсюда λ1 = − 6 < 0, λ 2 = 3 > 0, λ 3 = 1 > 0 , т.е. собственные значения имеют разные знаки.Поэтому в точке x 2 ∗ нет экстремума.3. Вычислим значение целевой функции в точке x1∗ локального минимума:f ( x1∗ ) = −12 .
150Пример 3. Найти экстремум функции f ( x) = − x12 + 2 x1 x2 − x22 − 4 x32на множествеR3. 1. Выпишем необходимые условия экстремума первого порядка:∂ f ( x)= −2 x1 + 2 x2 = 0 ,∂ x1∂ f ( x)= 2 x1 − 2 x2 = 0 ,∂ x2∂ f ( x)= − 8 x3 = 0 .∂ x3В результате решения системы получим бесконечное множество стационарных точек,удовлетворяющих соотношениям x1∗ = x 2∗ , x3∗ = 0 .2. Проверим выполнение достаточных условий экстремума.Первый способ. Матрица Гессе имеет видΔ1 = −2 < 0, Δ 2 =−222−2= 0,0 ⎞⎛ −2 2⎜⎟H ( x ) = ⎜ 2 −2 0 ⎟ . Так как⎜ 0 0 − 8⎟⎝⎠∗−220Δ3 = 2−20 = 0 , то достаточные условия экстре-00−8мума не выполняются.
Согласно схеме (см. рис.) проверим необходимые условия второгопорядка. Поступим аналогично решению примера 2.Главные миноры первого порядка получаются из Δ 3 в результате вычеркиваниядвух строк и столбцов с одинаковыми номерами: –2, –2, –8. Главные миноры второго порядка получаются из Δ 3 в результате вычеркивания по одной строке и столбцу с одинаковым номером: 16, 16, 0. Главный минор третьего порядка совпадает с Δ 3 = 0 . Так каквсе главные миноры четного порядка неотрицательны, а все миноры нечетного порядканеположительны, то можно сделать вывод о том, что в исследуемых стационарных точках может быть максимум и требуется продолжение исследования.Второй способ.
Найдем собственные значения матрицы Гессе:−2 − λ202020−2 − λ= ( − 8 − λ ) ⎡ ( −2 − λ ) − 4 ⎤ = 0 .⎢⎣⎥⎦− 8−λ0Отсюда λ1 = − 8 < 0, λ 2 = 0, λ 3 = − 4 < 0 , т.е. собственные значения неположительны. Поэтому в стационарных точках может быть максимум.23. Функция f ( x) может быть записана в виде f ( x) = − ( x1 − x2 ) − 4 x32 . В каждойиз найденной в п.
1 стационарной точке f ( x∗ ) = 0 . Исходя из структуры функции f ( x)можно сделать вывод о том, что для любых x ∈ R 3 справедливо: f ( x) ≤ f ( x∗ ) = 0 . На основании определения 1.1 (см. лекцию 1) функция на множестве точек, удовлетворяющихусловию x1∗ = x 2∗ , x3∗ = 0 , достигает глобального максимума. 151.