semopt2 (Практические занятия)

Занятие 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. Решением системы являются две условно-стационарные точки: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 + 2λ 1∗ dx 22 , так как== 2λ∗1 ,22∂x1∂x 2∂ 2 L (x , λ 1 )∂x1∂x 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 = 0−121−22f (x ) = 2−1Bx1f (x ) = 0−2f (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) ;{}x∈Xf ( x ∗ ) = max f ( x) ,x∈Xгде 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 изаменитьλ∗jλ∗0на λ∗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 ∗ , λ ∗ ) :∂ 2 L( x ∗ , λ ∗ )d L( x , λ ) = ∑ ∑dx i dx j ;∂x i ∂x ji =1 j =1б) записать условия, накладываемые на первые дифференциалы активныхограничений:n ∂ g (x∗ )j∗dg j ( x ) = ∑dx i = 0 , j ∈ J a ; λ∗j > 0 ( λ∗j < 0 );∂ xii =1∗2n∂ g j (x∗ )i =1∂ xidg j ( x ) = ∑∗∗nndx 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 + 2λ1 x1 − λ 2 = 0 ,∂ x1∂ L (x , λ 0 , λ )= 2λ 0 (x 2 − 2) + 2λ1 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 , тогда условия “а” запишутся в виде2λ1x1 − λ 2 = 0 ,2λ1x 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 ,т.е. также имеется противоречие;5) λ1 ≠ 0 , λ 2 ≠ 0 , λ 3 = 0 , тогда x1 = 0 и из первого уравнения в условии «а»имеем λ 2 = 0 , т.е. имеется противоречие;1576) λ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 .

Поделив уравнения приведенной в п.2 системы на λ 0 иλλλзаменив 1 на λ1 , 2 на λ 2 , 3 на λ 3 , получим:λ0λ0λ0∂ L ( x, λ )∂ L (x , λ )= 2 ( x 2 − 2) + 2 λ 1 x 2 − λ 3 = 0 ;а)= 2 x1 + 2λ1 x1 − λ 2 = 0 ,∂ x2∂ x1б) 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 .Рассмотрим восемь вариантов выполнения условий дополняющей нежесткости:1) λ1 = 0 , λ 2 = 0 , λ 3 = 0 , тогда x1 = 0, x 2 = 2 и не выполняется первоеограничение в условии «б»;2) λ1 ≠ 0 , λ 2 = 0 , λ 3 = 0 , тогдаx12 + x 22 − 1 = 0 ,2 x1 (1 + λ1 ) = 0 ,2 (x 2 − 2) + 2λ1 x 2 = 0 .Если λ1 = −1 , то третье уравнение не удовлетворяется. Если x1 = 0 , то x 2 = ±1 .Ограничениям в условии «б» удовлетворяет x 2 = 1 , при этом λ1 = 1 .