lopt2 (1013491)
Текст из файла
Лекция 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Рис. 2Б.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
