УМК (1013374), страница 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Рис. 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
