2 Необходимые и достаточные условия условного экстремума (Лекции по теории оптимизации и численным методам), страница 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) ;f ( x  )  max f ( x) ,xXxX(3.13)где X  x g j ( x)  0, j  1, , m .Утверждение 3.4 (необходимые условия минимума (максимума) первого порядка).Пусть x  – точка локального минимума (максимума) в задаче (3.13).

Тогда най-дется такое число 0  0 и вектор    (1 , ,  m ) T , не равные одновременно нулю итакие, что выполняются условия: стационарности обобщенной функции Лагранжа по x : L( x  ,  0 ,   ) 0, xii  1, , n ;(3.14 a) допустимости решения:g j (x )  0 ,19j  1,  , m ;(3.14 б) неотрицательности для условного минимума:j  0 ,j  1,  , m(3.14 в)(неположительности для условного максимума: j  0 , j  1,  , m ); дополняющей нежесткости: j g j ( x  )  0 ,j  1,  , m .(3.14 г)Если при этом градиенты активных в точке x  ограничений линейно независимы (выполняется условие регулярности), то 0  0 .З а м е ч а н и я.1.

Точки x  , удовлетворяющие системе (3.14), называются условно-стационар-ными.2. В отличие от случая ограничений типа равенств необходимые условия экстремума первого порядка формулируются отдельно для максимума и минимума.3. Если в решаемой задаче ограничения записаны в форме g j ( x)  0 , то их необхо-димо переписать в виде, используемом в (3.13):  g j ( x)  0 .4.

Далее будем использовать множество индексов ограничений, активных в точкеx , которое обозначим через J a .5. Точка экстремума, удовлетворяющая системе (3.18) при 0  0 , называется ре-гулярной, а при 0  0 – нерегулярной. Случай 0  0 отражает вырожденность ограничений.6. Из условия дополняющей нежесткости следует, что если ограничение в точкеx пассивное, т.е. g j ( x  )  0 , то j  0 , а если – активное, т.е. g j ( x  )  0 , то j  0(для минимума) и j  0 (для максимума).Утверждение 3.5 (достаточные условия минимума (максимума) первого порядка).Пусть имеется точка ( x  ,   ) , удовлетворяющая системе (3.14) при 0  0 , число активных ограничений в точке x  совпадает с числом n переменных (при этом условие регулярности выполняется).

Если j  0 для всех j  J a , то точка x  – точка условного локального минимума. Если j  0 для всех j  J a , то x  – точка условного локального максимума в задаче (3.13).Утверждение 3.6 (необходимое условие минимума (максимума) второго порядка).Пусть x  – регулярная точка минимума (максимума) в задаче (3.13) и имеетсярешение ( x  ,   ) системы (3.14). Тогда второй дифференциал классической функции Лагранжа, вычисленный в точке ( x  ,   ) , неотрицателен (неположителен):d 2 L( x  ,   )  0( d 2 L( x  ,   )  0 )20(3.15)для всех dx  R n таких, чтоdg j ( x  )  0 , j  J a , j  0 ( j  0 );dg j ( x  )  0 , j  J a , j  0 .Утверждение 3.7 (достаточные условия экстремума второго порядка).Пусть имеется точка ( x  ,   ) , удовлетворяющая системе (3.14) при 0  0 .

Еслив этой точке d 2 L( x  ,   )  0 ( d 2 L( x  ,   )  0 ) для всех ненулевых dx  R n таких, чтоdg j ( x  )  0 , j  J a , j  0 ( j  0 );dg j ( x  )  0 ,j  J a , j  0 ,то точка x  является точкой локального минимума (максимума) в задаче (3.13).Пример 2. Найти условный экстремум в задачеf ( x)  x12  x 22  extr ,g1 ( x)  x1  x 2  2  0 . 1. Составим обобщенную функцию Лагранжа:L  x,  0 ,  1    0 ( x12  x 22 )   1  x1  x 2  2  .2.

Выпишем необходимые условия первого порядка:а) L x ,  0 ,  1  x1 2 0 x1  1  0 , L x ,  0 ,  1  x2 2 0 x 2  1  0 ;б) x1  x 2  2  0 ;в) 1  0 (для минимума), 1  0 (для максимума);г) 1  x1  x 2  2  0 .3. Решим систему для двух случаев.Первый случай:  0  0 , тогда из условия «а» следует, что 1  0 , а это противоречит требованию утверждения 3.4 о существовании ненулевого вектора  0 ,   .TВторой случай:  0  0 . Поделив уравнения приведенной в п.

2 системы на  0 изаменив 1 на 1 , получим:021а) L x ,  1  x1 2 x1  1  0 , L x ,  1  x2 2 x 2  1  0 ;б) x1  x 2  2  0 ;в) 1  0 (для минимума), 1  0 (для максимума);г) 1  x1  x 2  2  0 .Из условия «г» дополняющей нежесткости следует:1) 1  0 (фактически решается задача поиска безусловного экстремума). Тогдаx1  x 2  0 , 1  0 и условие «б» выполняются. Выполняются необходимые условия идля минимума, и для максимума.2) 1  0 , тогда из системыx1  x 2  2  0,2 x1   1  0,2 x 2  1  0получим x1  x 2  1 ; 1  2 . Так как 1  0 , то необходимое условие минимума невыполняется (в точке 1,1 нет минимума), но выполняется необходимое условие максимума.

Таким образом, имеем две условно-стационарные точки.4. Проверим выполнение достаточных условий экстремума.TВ точке x   0, 0 ограничение не является активным, так как g1 ( x  )  2  0 ,поэтому достаточные условия первого порядка не удовлетворяются. Проверим условияTвторого порядка. Так как d 2 L( x  ,   )  2dx12  2dx 22  0 при dx  0 , то в точкеx   0, 0 – регулярный локальный условный минимум (рис.3).TВ точке x   1,1 ограничение является активным, но l  1  n  2 , поэтомудостаточное условие первого порядка не выполняется.

Проверим условие второго порядка. ИмеемTd 2 L( x  ,   )  2dx12  2dx 22 ,dg1 ( x  )  dx1  dx 2  0  dx1   dx 2 .Следовательно, d 2 L( x  ,   )  4dx 22  0 при dx 2  0 . Так как в этой точке 1  2  0 , тодостаточное условие максимума не выполняется. Проверим необходимое условие максимума второго порядка. Так как d 2 L( x  ,   )  4dx 22  0 при любых dx 2 , то необходимоеусловие максимума не выполняется, поэтому в точке x   1,1 максимума нет.T5. Вычислим значение функции в точке условного минимума: f ( x  )  0 . 22x2212x11xg1 ( x)  x1  x 2  2  0Рис. 3В.

УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ СМЕШАННЫХ ОГРАНИЧЕНИЯХПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f (x)  f  x1,, xn и функции ограничений типа равенств и неравенств: g j ( x)  0 , j  1,  , m ; g j ( x)  0 ,j  m  1,  , p , определяющие множество допустимых решений X .Требуется исследовать функцию f ( x) на экстремум, т.е. определить точки x   Xее локальных минимумов и максимумов на множестве X:f ( x  )  min f  x  ;f ( x  )  max f ( x) ,xX g j ( x)  0, j  1, , m; m  nгде X   xg j ( x )  0, j  m  1, , pxX(3.16).Утверждение 3.8 (необходимые условия минимума (максимума) первого порядка).Пусть x  – точка локального минимума (максимума) в задаче (3.16).

Тогда най-дется такое число 0  0 и вектор    ( 1 , ,  p ) T , не равные одновременно нулю итакие, что выполняются условия: стационарности обобщенной функции Лагранжа по x: L( x  ,  0 ,   ) 0, xii  1, , n ;(3.17 а) допустимости решения:g j ( x  )  0 , j  1,  , m ;g j ( x  )  0 , j  m  1,  , p ;23(3.17 б) неотрицательности для условного минимума:j  0 ,j  m  1,  , p(3.17 в)(неположительности для условного максимума: j  0 , j  m  1,  , p ); дополняющей нежесткости: j g j ( x  )  0 ,j  m  1,  , p .(3.17 г)Если при этом градиенты активных ограничений-неравенств и ограниченийравенств в точке x  линейно независимы (выполняется условие регулярности), то 0  0 .Следует подчеркнуть, что условия дополняющей нежесткости и знакоопределенности множителей Лагранжа записываются только для ограничений-неравенств.Утверждение 3.9 (достаточные условия минимума (максимума) первого порядка).Пусть имеется точка ( x  ,   ) , удовлетворяющая системе (3.17) при 0  0 ,суммарное число активных ограничений-неравенств в точке x  и ограничений-равенствсовпадает с числом n переменных (при этом условие регулярности выполняется).

Еслиj  0 для всех j  J a , то точка x  – точка условного локального минимума в задаче(3.16). Если j  0 для всех j  J a , то x  – точка условного локального максимума.Утверждение 3.10 (необходимые условия минимума (максимума) второго поряд-ка).Пусть x  – регулярная точка минимума (максимума) в задаче (3.16) и имеетсярешение ( x  ,   ) системы (3.17). Тогда второй дифференциал классической функцииЛагранжа, вычисленный в точке ( x  ,   ) , неотрицателен (неположителен):d 2 L( x  ,   )  0( d 2 L( x  ,   )  0 )для всех dx  R n таких, чтоdg j ( x  )  0 , j  1,  , m и j  J a , j  0 ( j  0 );dg j ( x  )  0 , j  J a , j  0 .Утверждение 3.11 (достаточные условия экстремума второго порядка).Пусть имеется точка ( x  ,   ) , удовлетворяющая системе (3.17) при 0  0 .