УМК (1013374), страница 27
Текст из файла (страница 27)
СМЕШАННЫЕ ОГРАНИЧЕНИЯПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция 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 ) ;x∈X⎧⎪ g j ( x) = 0, j = 1,… , m; m < nгде X = ⎨ xg j ( x) ≤ 0, j = m + 1,… , p⎪⎩f ( x ∗ ) = max f ( x) ,x∈X⎫⎪⎬.⎪⎭Алгоритм решения задачиШаг 1. Составить обобщенную функцию Лагранжа:pL ( x, λ 0 , λ ) = λ 0 f ( x ) + ∑ λ j g j ( x ) .j =1Шаг 2. Записать необходимые условия минимума (максимума) первого порядка:∂ L( x ∗ , λ ∗0 , λ ∗ )= 0,i = 1,… , n ;а)∂ xiб) g j ( x ∗ ) = 0 , j = 1, … , m ; g j ( x ∗ ) ≤ 0 , j = m + 1, … , p ;в) λ∗j ≥ 0 , j = m + 1, … , p (для минимума),λ∗j ≤ 0 , j = m + 1, … , p (для максимума);г) λ ∗j g j ( x ∗ ) = 0 , j = m + 1, … , p .Шаг 3.
Решить систему для двух случаев:Первый случай: λ∗0 = 0 .Второй случай: λ∗0 ≠ 0заменитьλ∗jλ∗0(приэтом поделить условия «а», «в», «г» наλ∗0 ина λ∗j ).В результате найти условно-стационарные точки x ∗ , выделив из них полученныепри λ∗0 ≠ 0 (они могут быть регулярными точками экстремума). В каждом из двух160случаев следует начинать с рассмотрения 2 p − m вариантов удовлетворения условия «г»дополняющей нежесткости.Шаг 4. Для выделенных на шаге 3 точек проверить выполнение достаточныхусловий экстремума первого или второго порядка.Для проверки достаточных условий первого порядка следует:а) определить число l ограничений-равенств и активных ограничений-неравенств;б) если l = n и λ∗j > 0 для всех j ∈ J a , т.е. для всех активных ограниченийнеравенств, то в точке x ∗ – локальный минимум.
Если l = n и λ∗j < 0 для всехj ∈ J a , то в точке x ∗ – локальный максимум. Если l < n или соответствующиемножители Лагранжа не удовлетворяют достаточным условиям первогопорядка, проверить достаточные условия второго порядка.Для проверки достаточных условий второго порядка следует:а) записать выражение для второго дифференциала классической функцииnnЛагранжа в точке ( x ∗ , λ ∗ ) : d 2 L( x ∗ , λ ∗ ) = ∑ ∑i =1 j =1∂ 2 L( x ∗ , λ ∗ )dx i dx j ;∂x i ∂x jб) записать условия, накладываемые на первые дифференциалы ограниченийравенств и активных в точке x ∗ ограничений-неравенств:n ∂ g (x∗ )j∗dg j ( x ) = ∑dx i = 0 , j = 1, … , m и j ∈ J a ; λ∗j > 0 ( λ∗j < 0 );∂ xii =1n∂ g j (x∗ )i =1∂ xidg j ( x ) = ∑∗dx i ≤ 0 , j ∈ J a , λ∗j = 0 ;в) исследовать знак второго дифференциала функции Лагранжа для ненулевых dx ,удовлетворяющих системе из п.б.
Если d 2 L( x ∗ , λ ∗ ) > 0 , то в точке x ∗ –условныйлокальный минимум. Если d 2 L( x ∗ , λ ∗ ) < 0 , то в точке x ∗ –условный локальный максимум. Если достаточные условия экстремума невыполняются, следует проверить выполнение необходимых условий второгопорядка (см. утверждение 3.10 – лекция 2), следуя аналогичной процедуре. Еслиони выполняются, то требуется дополнительное исследование, а если нет, то вточке x ∗ нет условного экстремума.Шаг 5. Вычислить значения функции в точках условного экстремума.Пример 3.
Найти условный экстремум в задачеf ( x) = x1 − x 22 → extr ,g1 ( x) = x1 − x 2 − 1 = 0 ,g 2 ( x) = x12 + x 22 − 5 ≤ 0 . 1. Составим обобщенную функцию Лагранжа:L ( x, λ 0 , λ ) = λ 0 ( x1 − x 22 ) + λ 1 ( x1 − x 2 − 1) + λ 2 ( x12 + x 22 − 5) .2. Выпишем необходимые условия минимума и максимума первого порядка:∂ L (x , λ 0 , λ )∂ L (x , λ 0 , λ )а)= λ 0 + λ1 + 2λ 2 x1 = 0 ,= −2λ 0 x 2 − λ1 + 2λ 2 x 2 = 0 ;∂ x1∂ x2161б) x1 − x 2 − 1 = 0 , x12 + x 22 − 5 ≤ 0 ;в) λ 2 ≥ 0 (для минимума), λ 2 ≤ 0 (для максимума);г) λ 2 ( x12 + x 22 − 5) = 0 .3. Решим систему для двух случаев.Первый случай: λ 0 = 0 , тогда условие «а» имеет видλ1 + 2λ 2 x1 = 0,− λ1 + 2λ 2 x 2 = 0 .Рассмотрим два варианта удовлетворения условия «г»:1) λ 2 = 0 , тогда λ1 = 0 и не удовлетворяется условие утверждения 3.8;2) λ 2 ≠ 0 , тогда система уравненийx12 + x 22 − 5 = 0,x1 − x 2 − 1 = 0удовлетворяется в двух точках: x1 = 2, x 2 = 1; x1 = −1, x 2 = −2 .
Складывая двауравнения в условии «а», получаем 2λ 2 ( x1 + x 2 ) = 0 . Так как λ 2 ≠ 0 , то x1 = − x 2 , что неудовлетворяется в обеих найденных точках.Второй случай: λ 0 ≠ 0 . Поделив уравнения приведенной в п.2 системы на λ 0 иλλзаменив 1 на λ1 , 2 на λ 2 , запишем условие «a» в видеλ0λ0∂ L (x , λ )∂ L (x , λ )= 1 + λ1 + 2λ 2 x1 = 0 ,= −2 x 2 − λ1 + 2λ 2 x 2 = 0 .∂ x1∂ x2Остальные условия сохраняют вид.Рассмотрим два варианта удовлетворения условия «г»:1) λ 2 = 0 , тогда1 + λ1 = 0,−2 x 2 − λ1 = 0,x1 − x 2 − 1 = 0 .31Отсюда имеем λ1 = −1, x 2 = , x1 = .
В результате получили условно-стационарную2231точку А: x1∗ = , x 2∗ = , λ∗1 = −1, λ∗2 = 0 , в которой удовлетворяется необходимое22условие и минимума, и максимума;2) λ 2 ≠ 0 , тогдаx12 + x 22 − 5 = 0,x1 − x 2 − 1 = 0,1 + λ1 + 2λ 2 x1 = 0,−2 x 2 − λ 1 + 2 λ 2 x 2 = 0 .Получаем еще две условно-стационарные точки:1552В : x1∗ = 2, x 2∗ = 1, λ∗1 = − , λ∗2 = > 0 ; С : x1∗ = −1, x 2∗ = −2, λ∗1 = , λ∗2 = > 0 ,3636в которых удовлетворяются необходимые условия минимума.4. Проверим выполнение достаточных условий экстремума первого порядка.162В точке А ограничение-неравенство не является активным, поэтому l = 1 < n = 2 иусловия не выполняются. В точках В и С ограничение-неравенство активное, поэтомуl = n = 2 . В обеих точках λ∗2 > 0 , поэтому в них достигается условный локальныйминимум.Проверим достаточные условия экстремума второго порядка из методическихсоображений (в точке А это требуется обязательно).В точке А ограничение-неравенство не является активным:d 2 L ( A ) = 2λ∗2 dx12 + 2λ∗2 − 2 dx 22 = −2dx 22 ,()dg 1 ( A ) = dx1 − dx 2 = 0 .Отсюда имеем: dx1 = dx 2 и d 2 L ( A ) = −2dx12 < 0 при dx1 ≠ 0 .
Поэтому в точке А –локальный условный максимум.В точках B и C ограничение-неравенство активно.15d 2 L (B ) = dx12 − dx 22 ,33Исследуем точку В : dg1 (B ) = dx1 − dx 2 = 0,dg 2 (B ) = 2 x1∗ dx1 + 2 x 2∗ dx 2 = 4dx1 + 2dx 2 = 0 .Отсюда следует, что dx1 = dx 2 = 0 и d 2 L (B ) ≡ 0 , поэтому требуется дополнительноеисследование.51d 2 L ( C ) = dx12 − dx 22 ,33dg1 ( C ) = dx1 − dx 2 = 0,Исследуем точку С:dg 2 ( C ) = −2dx1 − 4dx 2 = 0.Отсюда имеем: dx1 = dx 2 = 0 и d 2 L (q ) ≡ 0 .
Требуется дополнительное исследование.Из рис. 4 следует, что в точке В – условный локальный минимум, а в точке С –условный глобальный минимум.55. Значения функции в точках экстремума: f ( A ) = , f (B ) = 1, f (C ) = −5 . 4x2g1 ( x) = 0f ( x) =1g 2 ( x) = 0B12−11−554A2x1− 1X−2CРис. 4163f ( x) = 1f ( x) = 0f ( x) = −5Занятие 3.
ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГОЭКСТРЕМУМА. МЕТОДЫ ПЕРВОГО ПОРЯДКАПостановка задачиПусть дана функция f ( x) , ограниченная снизу на множестве R n и имеющаянепрерывные частные производные во всех его точках.Требуется найти локальный минимум функции f ( x) на множестве допустимыхрешений X = R n , т.е. найти такую точку x ∗ ∈ R n , чтоf ( x ∗ ) = minn f ( x) .x∈ RА. МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМАлгоритмШаг 1. Задать x 0 , 0 < ε < 1 , ε1 > 0 , ε 2 > 0 , M – предельное число итераций.
НайтиT⎛ ∂ f (x )∂ f (x ) ⎞⎟ .,...,градиент функции в произвольной точке ∇f ( x ) = ⎜⎜∂ x n ⎟⎠⎝ ∂ x1Шаг 2. Положить k = 0 .( )Шаг 3. Вычислить ∇f x k .( )Шаг 4. Проверить выполнение критерия окончания ∇f x k< ε1 :а) если критерий выполнен, расчет закончен, x ∗ = x k ;б) если критерий не выполнен, то перейти к шагу 5.Шаг 5. Проверить выполнение неравенства k ≥ M :а) если неравенство выполнено, то расчет окончен: x ∗ = x k ;б) если нет, то перейти к шагу 6.Шаг 6. Задать величину шага t k .( )Шаг 7. Вычислить x k +1 = x k − t k ∇f x k .Шаг 8.
Проверить выполнение условия() ( )f x k +1 − f x k < 0(или() ( )( )f x k +1 − f x k < − ε ∇f x k2):а) если условие выполнено, то перейти к шагу 9;tб) если условие не выполнено, положить t k = k и перейти к шагу 7.2Шаг 9. Проверить выполнение условийx k +1 − x k < ε 2 ,() ( )f x k +1 − f x k164< ε2 :а) если оба условия выполнены при текущем значении k и k = k − 1 , то расчетокончен, x ∗ = x k +1 ;б) если хотя бы одно из условий не выполнено, положить k = k + 1 и перейти кшагу 3.Геометрическая интерпретация метода для n = 2 приведена на рис.
1.C1 > C 2 > C 3x2f ( x ) = C1x0− ∇f ( x 0 )x1x∗x2f (x ) = C3f (x ) = C 20x1Рис. 1Пример 1. Найти локальный минимум функцииf ( x ) = 2 x12 + x1x 2 + x 2 2 . I. Определим точку x k , в которой выполнен по крайней мере один из критериевокончания расчетов.1. Зададим x 0 , ε1 , ε 2 , M : x 0 = (0,5;1) , ε1 = 0,1 ; ε 2 = 0,15 ; M = 10 . Найдем граTдиент функции в произвольной точке ∇f ( x ) = (4 x1 + x 2 ; x1 + 2 x 2 )T .2. Положим k = 0 .( ) ( )∇f (x ) : ∇f (x )3 0 . Вычислим ∇f x 0 : ∇f x 0 = (3; 2,5) .4 0 . Вычислим00T= 3,9 > 0,1 .
Перейдем к шагу 5.5 0 . Проверим условие k ≥ M : k = 0 < 10 = M . Перейдем к шагу 6.6 0 . Зададим t 0 = 0,5 .7 0 . Вычислим x 1 : x 1 = (0,5;1) − 0,5(3; 2,5)T( )( )( )= ( −1;− 0,25) ; f x 1 = 2,31 .TT( ) ( )80 . Сравним f x 1 с f x 0 = 2 . Имеем f x 1 > f x 0 . Вывод: условие() ( )f x k +1 < f x k для k = 0 не выполняется. Зададим t 0 = 0,25 , перейдем к повторениюшагов 7, 8.7 01 . Вычислим x 1 : x 1 = (0,5;1) − 0,25(3; 2,5)TT165( )= ( − 0,25; 0,375) ; f x 1 = 0,171 .T( )( )( ) ( )− x и f (x ) − f (x ) := 0,976 > 0,15 ;f (x ) − f (x ) = 1,829 > 0,15 .801 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
