2 Необходимые и достаточные условия условного экстремума (Лекции по теории оптимизации и численным методам)

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

ФункцияpL  x,  0 ,     0 f ( x )    j g j ( x )(3.2)j 1называется обобщенной функцией Лагранжа, числа  0 , 1 , ,  p – множителями Ла-гранжа,   1 ,  ,  pT . Классической функцией Лагранжа называется функцияpL  x,    f ( x )    j g j ( x ) .(3.3)j 1Определение 3.2. Градиентом обобщенной (классической) функции Лагранжа по xназывается вектор-столбец, составленный из ее частных производных первого порядка поx i , i  1,...

, n :  L x ,  0 ,    x1, x L x ,  0 ,    (3.4)  L x ,  0 ,    xn  L x ,    x1.Lx, xLx,  x n  14Определение 3.3. Вторым дифференциалом обобщенной (классической) функцииЛагранжа L  x,  0 ,   L x,   называется функцияnd 2 L x ,  0 ,   n 2 L x ,  0 ,  x i x ji 1 j 1dx i dx j ,(3.5)n n 2 2 L x ,  dx i dx j  . d L x ,     i 1 j 1 x i x jОпределение 3.4. Первым дифференциалом ограничения g j ( x) называется функ-цияn g j ( x)i 1 xidg j ( x)  dxi ,j  1, , p .(3.6)Определение 3.5.

Ограничение g j ( x)  0 называется активным в точке x  , еслиg j ( x  )  0 . Если g j ( x  )  0 , то ограничение называется пассивным.Определение 3.6. Градиенты ограничений g 1 ( x), , g m ( x) являются линейно неза-висимыми в точке x  , если равенство  1g 1 ( x  )   2 g 2 ( x  )     m g m ( x  )  0 выполняется только при 1   2    m  0 .

Если существуют числа 1 ,  ,  m , одновременно не равные нулю, для которых равенство выполняется, то градиенты линейно зависимы. В этом случае один из них есть линейная комбинация остальных. Один векторg 1 ( x  ) тоже образует систему векторов: при g 1 ( x  )  0 линейно независимую, а приg 1 ( x  )  0 линейно зависимую.Система векторов, содержащая нулевой вектор, всегда линейно зависима. Еслиrang A  rang g 1 ( x  ) g 2 ( x  ) g m ( x  )  m , то система векторов линейно независима.Если rang A  m , то система линейно зависима.A. УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ ОГРАНИЧЕНИЯХ ТИПА РАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция 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где X  x g j ( x)  0, j  1, , m; m  n .15f ( x  )  max f ( x) ,xX(3.7)Утверждение 3.1 (необходимые условия экстремума первого порядка).Пусть x  есть точка локального экстремума в задаче (3.7).

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

Поэтому, как правило, рассматриваются два случая: 0  0 и 0  0 .Если 0  0 , в системе (3.8 а) полагают 0  1 . Это эквивалентно делению системы уравнений (3.8 a) на0и заменеj0на j . При этом обобщенная функция Лагранжа становит-ся классической, а сама система (3.8) имеет вид L( x  ,   ) 0, xig j (x )  0 ,i  1,  , n ;j  1,  , m .(3.9 a)(3.9 б)Здесь число уравнений равно числу неизвестных.Точка экстремума, удовлетворяющая системе (3.8) при 0  0 , называется регулярной, а при 0  0 – нерегулярной.

Случай 0  0 отражает вырожденность ограничений.При этом в обобщенной функции Лагранжа исчезает член, содержащий целевую функцию, ав необходимых условиях экстремума не используется информация, представляемая градиентом целевой функции.Утверждение 3.2 (необходимые условия экстремума второго порядка).Пусть x  – регулярная точка минимума (максимума) в задаче (3.7) и имеется решение ( x  ,   ) системы (3.9).

Тогда второй дифференциал классической функции Лагранжа,вычисленный в точке ( x  ,   ) , неотрицателен (неположителен):d 2 L( x  ,   )  0 d 2 L( x  ,   )  0 16(3.10)для всех dx  R n таких, чтоn g j (x )i 1 xidg j ( x )  dx i  0 ,j  1,  , m .(3.11)Утверждение 3.3 (достаточные условия экстремума).Пусть имеется точка ( x  ,   ) , удовлетворяющая системе (3.9).

Если в этой точкеd 2 L( x  ,   )  0 d 2 L( x  ,   )  0(3.12)для всех ненулевых dx  R n таких, чтоn g j (x )i 1 xidg j ( x )  dx i  0 ,j  1,  , m ,то точка x является точкой локального минимума (максимума) в задаче (3.7).З а м е ч а н и я.1. Достаточные и необходимые условия экстремума второго порядка проверяются вусловно-стационарных точках, которые удовлетворяют системе (3.8) при 0  0 или системе (3.9), так как для практики, безусловно, представляет интерес случай, когда в функцииЛагранжа присутствует целевая функция, экстремум которой ищется.2. Иногда удается проверить условие линейной независимости градиентов ограничений на множестве X (см. определение 3.6.).

Если оно выполняется, то на шаге 1 следует записать классическую функцию Лагранжа (3.3), на шаге 2 можно записывать сразу систему(3.9), а на шаге 3 отсутствует случай 0  0 .3. Для нахождения графического решения задачи (при n  2, m  1 ) следует:а) построить множество допустимых решений X ;б) построить семейство линий уровня целевой функции и найти точки их касания скривыми, описывающими ограничения.

Эти точки являются «подозрительными» на условный экстремум;в) исследовать поведение целевой функции при движении вдоль ограничения к исследуемой точке и от нее. Классифицировать точки, используя определение экстремума (cм. определения 1.1 и 1.2).f ( x)  C 2f ( x)  C 4C 4  C 3  C 2  C141325f ( x)  C 36f ( x)  C1g ( x)  0Рис. 117На рис. 1 в точках 1 – 2, 4 – 6 линии уровня касаются ограничения. Исследованиеповедения функции в этих точках при движении по стрелкам показывает, что в точках 1,4, 6 – локальный максимум, так как при приближении к ним функция возрастает, а затемубывает; в точках 2, 5 – локальный минимум, так как при приближении к ним функцияубывает, а затем возрастает; в точке 3 нет условного экстремума, поскольку при приближении к ней и удалении дальше от нее функция возрастает.4. При решении примеров для упрощения записи на шагах 2 и 3 алгоритма будемопускать знак «  », оставляя его только для значений x и  , соответствующих условностационарным точкам.Пример 1.

Найти экстремум функции f ( x)  x12  x 22 на множествеX  x x1  x 2  2  0 : f ( x)  x12  x 22  extr , g1 ( x)  x1  x 2  2  0 . Проверим условие регулярности. Так как g1 (1,1) T  0 , то условие выполняется(см. определение 3.6). Поэтому будем пользоваться классической функцией Лагранжа(3.3).1. Составим функцию Лагранжа:L x, 1   x12  x 22  1 x1  x 2  2  .2.

Выпишем необходимые условия экстремума первого порядка:а) L x ,  1  2 x1  1  0  x1   x1б) g1 ( x)  x1  x 2  2  0 .12, L x ,  1  x2 2 x 2  1  0  x 2  12;3. Решение системы: x1  x 2  1, 1  2 – условно-стационарная точка.4. Проверим выполнение достаточных условий экстремума: 2 L x ,  1   2 L  x ,  1 а) d 2 L( x  ,  1 )  2dx12  2dx 22 , так как 2,x12x 22 2 L x , 1  2 L x ,  1  0;x 2 x1 g1 ( x)  g1 ( x) 1;б) dg1 ( x  )  dx1  dx 2  0 , так как x1 x2x1x 2в) выразим дифференциал dx1 через dx 2 : dx1  dx 2 и подставим в d 2 L ;г) так как d 2 L( x  , 1 )  4dx 22  0 при dx 2  0 , то в точке x   1,1локальный условный минимум.T- регулярный5. Подсчитаем значение функции в точке условного экстремума: f ( x  )  2 .Графическое решение задачи приведено на рис.

2.Линии уровня функции f ( x) представляются окружностями, а множество допустимых решений X – графиком прямой. В точке x  1, 1 , f ( x )  2 достигается глобальный минимум (рис. 2). Глобальный максимум на данном множестве не существует.Заметим, что в точке x  линии уровня целевой функции касаются кривой, описывающейограничения. T18ff ( x )  x1 2  x 2 2x1  x 2  2  0x22x1  x 2  2  022x  (1, 1)Тf (x )  1x   (1, 1) Т11x12x2f (x )  2x1XРис.