3. Необходимые и достаточные условия условного экстремума. Численные методы поиска условного экстремума (8 практических занятий с сайта кафеды 805)
Описание файла
Файл "3. Необходимые и достаточные условия условного экстремума. Численные методы поиска условного экстремума" внутри архива находится в папке "8 практических занятий с сайта кафеды 805". PDF-файл из архива "8 практических занятий с сайта кафеды 805", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Занятие 3.МЕТОДЫ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМАНЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ УСЛОВНОГОЭКСТРЕМУМАА. ОГРАНИЧЕНИЯ ТИПА РАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция 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) ,xXf ( x ) max f ( x) ,xXгде 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и заменитьj0наj ).В результате решения найти условно-стационарные точки x , выделив из нихполученные при 0 0 (они могут быть регулярными точками экстремума).Шаг 4.
Для выделенных на шаге 3 точек проверить выполнение достаточных условийэкстремума:а) записать выражение для второго дифференциала классической функции Лагранжав точке ( x , ) :152nnd L( x , ) 2i 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 21 x1 0 x1 1,21 1 21 x 2 0 x 2 1;21б) g1 ( x) x12 x 22 2 0 .3. Решением системы являются две условно-стационарные точки:A: x1 1, x 2 1, 1 1;2B: x1 1, x 2 1, 1 1.24.
Проверим выполнение достаточных условий экстремума: 2 L x , 1 2 L x , 1 а) d 2 L( x , 1 ) 2 1 dx12 21 dx 22 , так как 21 ,22x 2x1 2 L x , 1 x1x 2 2 L x , 1 0;x 2 x1 g1 ( x) g1 ( x) 2x2 ; 2 x1 , x1 x2в) исследуем точку A. Получаем dg1 A 2dx1 2dx 2 0 , откуда dx1 dx 2 .б) dg1 ( x ) 2 x1 dx1 2 x 2 dx 2 0 , так какС учетом полученного соотношения d 2 L A dx12 dx 22 2dx 22 0 при dx 2 0 .Поэтому в точке x 1,1 – регулярный условный локальный максимум.T154Исследуем точку B.
Получаем dg1 B 2dx1 2dx 2 0 , откуда dx1 dx 2 .С учетом полученного соотношения d 2 L B dx12 dx 22 2dx 22 0 при dx 2 0 .Поэтому в точке x 1, 1 – регулярный условный локальный минимум.T5. Подсчитаем значения функции в точках экстремума: f A 2, f B 2 .Графическое решение задачи изображено на рис. 2.
x222A1g 1 ( x ) x1 2 x 2 2 2 012122f (x ) 21Bx1f (x ) 02f (x ) 2Рис. 2Б. ОГРАНИЧЕНИЯ ТИПА НЕРАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x) f x1,, xn и функции ограничений g j ( x) g j x1 , , x n 0 , j 1, , m , определяющие множестводопустимых решений X .Требуется исследовать функцию f x на экстремум, т.е. определить точки x Xее локальных минимумов и максимумов на множестве X :f ( x ) min f ( x) ;xXf ( x ) max f ( x) ,xXгде X x g j ( x) 0, j 1, , m .Алгоритм решения задачиШаг 1.
Составить обобщенную функцию Лагранжа:mL x, 0 , 0 f ( x ) j g j ( x ) .j 1155Шаг 2. Записать необходимые условия минимума (максимума) первого порядка: L( x , 0 , )а) 0,i 1, , n ; xiб) g j ( x ) 0 , j 1, , m ;в) j 0 , j 1, , m (для минимума), j 0 , j 1, , m (для максимума);г) j g j ( x ) 0 , j 1, , m .Шаг 3.
Решить систему для двух случаев.Первый случай: 0 0 .Второй случай: 0 0 (при этом поделить условия, записанные на шаге 2, на 0 изаменитьj0на j ).В результате решения найти условно-стационарные точки x , выделив из нихполученные при 0 0 (они могут быть регулярными точками экстремума). В каждомиз двух случаев следует начинать с рассмотрения 2 m вариантов удовлетворения условия«г» дополняющей нежесткости.Шаг 4. Для выделенных на шаге 3 точек проверить выполнение достаточныхусловий экстремума первого или второго порядка.Для проверки выполнения достаточных условий первого порядка следует:а) определить число l активных в точке x ограничений;б) если l n и j 0 для всех j J a , то в точке x – условный локальныйминимум.
Если l n и j 0 для всех j J a , то в точке x – условныйлокальный максимум. Если l n или соответствующие множители Лагранжане удовлетворяют достаточным условиям первого порядка, проверитьдостаточные условия второго порядка.Для проверки выполнения достаточных условий второго порядка следует:а) записать выражение для второго дифференциала классической функцииЛагранжа в точке ( x , ) :nnd L( x , ) 2i 1 j 1 2 L( x , )dx i dx j ;x i x jб) записать условия, накладываемые на первые дифференциалы активныхограничений:n g (x )jdg j ( x ) dx i 0 , j J a ; j 0 ( j 0 ); xii 1n g j (x )i 1 xidg j ( x ) dx i 0 , j J a , j 0 ;в) исследовать знак второго дифференциала функции Лагранжа при ненулевыхdx , удовлетворяющих системе, составленной в п.б.
Если d 2 L( x , ) 0 , то156в точке x – условный локальный минимум. Если d 2 L( x , ) 0 , то в точкеx – условный локальный максимум.Если достаточные условия первого и второго порядка не выполняются, следуетпроверить выполнение необходимых условий второго порядка (см. утверждение 3.6 –лекция 2), следуя аналогичной процедуре. Если они выполняются, то требуетсядополнительное исследование, а если нет, то в точке x нет условного экстремума.Шаг 5. Вычислить значения функции в точках условного экстремума.Пример 2. Найти условный минимум в задачеf ( x) x12 ( x 2 2) 2 min ,g1 ( x) x12 x 22 1 0 ,g 2 ( x) x1 0 ,g 3 ( x) x 2 0 . 1.
Составим обобщенную функцию Лагранжа:L x, 0 , 0 x12 ( x 2 2) 2 1 ( x12 x 22 1) 2 ( x1 ) 3 ( x 2 ) .2. Выпишем необходимые условия минимума первого порядка: L x , 0 , а) 2 0 x1 21 x1 2 0 , x1 L x , 0 , 2 0 x 2 2 21 x 2 3 0 ; x2б) x12 x 22 1 0 , x1 0 , x 2 0 ;в) 1 0 , 2 0 , 3 0 ;г) 1 ( x12 x 22 1) 0 , 2 ( x1 ) 0 , 3 ( x 2 ) 0 .3. Решим систему для двух случаев.Первый случай: 0 0 , тогда условия “а” запишутся в виде21x1 2 0 ,21x 2 3 0 .Рассмотрим восемь вариантов выполнения условий «г» дополняющейнежесткости:1) 1 0 , 2 0 , 3 0 , при этом не удовлетворяется требование утверждения3.4;2) 1 0 , 2 0 , 3 0 , тогда x1 x 2 0 из условия «а», но первое условиедополняющей нежесткости не удовлетворяется;3) 1 0 , 2 0 , 3 0 , тогда из первого уравнения в условии «а» имеем 2 0 , т.е.
имеется противоречие;4) 1 0 , 2 0 , 3 0 , тогда из второго уравнения в условии «а» имеем 3 0 ,т.е. также имеется противоречие;1575) 1 0 , 2 0 , 3 0 , тогда x1 0 и из первого уравнения в условии «а»имеем 2 0 , т.е. имеется противоречие;6) 1 0 , 2 0 , 3 0 , тогда x 2 0 и из второго уравнения в условии «а»имеем 3 0 , т.е. также имеется противоречие;7) 1 0 , 2 0 , 3 0 , тогда не выполняются оба уравнения в условии “а”;8) 1 0 , 2 0 , 3 0 , тогда уравнения x1 x 2 0 , x12 x 22 1 0 ,следующие из условия “г”, вместе не выполняются.Условно-стационарных точек пока не найдено.Второй случай: 0 0 .