УМК (1013374), страница 25
Текст из файла (страница 25)
Найдем собственные значения матрицы Гессе:−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Занятие 2.НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ УСЛОВНОГОЭКСТРЕМУМАА. ОГРАНИЧЕНИЯ ТИПА РАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x) = f ( x1 ,… , x n )и функции ограничений g j ( x) = g j ( x1 ,… , x n ) = 0, j = 1,… , m , определяющие множестводопустимых решений X .Требуется исследовать функцию f ( x) на экстремум, т.е.
определить точки x ∗ ∈ X еелокальных минимумов и максимумов на множестве X :f ( x ∗ ) = min f ( x) ,x∈X{f ( x ∗ ) = max f ( x) ,x∈X}где X = x g j ( x) = 0, j = 1,… , m; m < n .Алгоритм решения задачиШаг 1. Составить обобщенную функцию Лагранжа:mL ( x, λ 0 , λ ) = λ 0 f ( x ) + ∑ λ j g j ( x ) .j =1Шаг 2. Записать необходимые условия экстремума первого порядка:∂ L( x ∗ , λ ∗0 , λ ∗ )= 0,а)∂ xiб) g j ( x ∗ ) = 0 ,i = 1, … , n ;j = 1, … , m .Шаг 3. Решить систему для двух случаев.Первый случай: λ∗0 = 0 .Второй случай: λ∗0 ≠ 0 (при этом поделить условие «а» на λ∗0 и заменитьλ∗jλ∗0наλ∗j ).В результате решения найти условно-стационарные точки x ∗ , выделив из нихполученные при λ∗0 ≠ 0 (они могут быть регулярными точками экстремума).Шаг 4. Для выделенных на шаге 3 точек проверить выполнение достаточных условийэкстремума:а) записать выражение для второго дифференциала классической функции Лагранжав точке ( x ∗ , λ ∗ ) :152nnd L( x , λ ) = ∑ ∑∗2∗i =1 j =1∂ 2 L( x ∗ , λ ∗ )dx i dx j ;∂x i ∂x jб) записать систему в точке x ∗ :n∂ g j (x∗ )i =1∂ xidg j ( x ) = ∑∗dx i = 0 ,j = 1, … , m ;в) из предыдущей системы выразить любые m дифференциалов dxi через остальные( n − m ) и подставить в d 2 L( x ∗ , λ ∗ ) ;г) если d 2 L( x ∗ , λ ∗ ) > 0 при ненулевых dx , то в точке x ∗ – условный локальныйминимум.
Если d 2 L( x ∗ , λ ∗ ) < 0 при ненулевых dx , то в точке x ∗ – условныйлокальный максимум. Если достаточные условия экстремума не выполняются,следует проверить выполнение необходимых условий второго порядка, следуяаналогичной процедуре. Если они выполняются, то требуется дополнительноеисследование, а если не выполняются, то в точке x ∗ нет условного экстремума.Шаг 5. Вычислить значения функции в точках условного экстремума.З а м е ч а н и я.1. Иногда удается проверить условие линейной независимости градиентовограничений на множестве X . Если оно выполняется, то на шаге 1 следует записатьклассическую функцию Лагранжа, на шаге 2 можно записывать сразу систему при λ 0 = 1 , ана шаге 3 отсутствует случай λ∗0 = 0 .2. Для графического решения задачи (при n = 2, m = 1 ) следует:а) построить множество допустимых решений X;б) построить семейство линий уровня целевой функции и найти точки их касания скривыми, описывающими ограничения.
Эти точки являются «подозрительными» наусловный экстремум;в) исследовать поведение целевой функции при движении вдоль ограничения кисследуемой точке и от нее. Классифицировать точки, используя определение экстремума(cм. определения 1.1 и 1.2 – лекция 1).f ( x) = C 2f ( x) = C 4C 4 > C 3 > C 2 > C141325f ( x) = C 36f ( x) = C1g ( x) = 0Рис. 1153На рис. 1 в точках 1 – 2, 4 – 6 линии уровня касаются ограничения. Исследованиеповедения функции в этих точках при движении по стрелкам показывает, что в точках 1,4, 6 – локальный максимум, так как при приближении к ним функция возрастает, а затемубывает; в точках 2, 5 – локальный минимум, так как при приближении к ним функцияубывает, а затем возрастает; в точке 3 нет условного экстремума, поскольку приприближении к ней и удалении дальше от нее функция возрастает.3. При решении примеров для упрощения записи на шагах 2 и 3 алгоритма будемопускать знак « ∗ », оставляя его только для значений x и λ , соответствующих условностационарным точкам.Пример 1.
Найти условный экстремум в задачеf ( x) = x1 + x 2 → extr ,g1 ( x) = x12 + x 22 − 2 = 0 .T Проверим условие регулярности. Так как ∇g1 ( x) = ( 2 x1 , 2 x 2 ) ≠ 0 для всехx ∈ X , то условие выполняется (см. определение 3.6 – лекция 2). Поэтому будемпользоваться классической функцией Лагранжа.1. Составим функцию Лагранжа:()L ( x , λ1 ) = x1 + x 2 + λ1 x12 + x 22 − 2 .2. Выпишем необходимые условия экстремума первого порядка:а)∂ L (x , λ 1 )∂ x1∂ L (x , λ 1 )∂ x2= 1 + 2λ1 x1 = 0 ⇒ x1 = −1,2λ1= 1 + 2λ1 x 2 = 0 ⇒ x 2 = −1;2λ1б) g1 ( x) = x12 + x 22 − 2 = 0 .3.