lopt2 (1013491), страница 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 . Еслив этой точке 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 ,то точка x ∗ является точкой локального минимума (максимума) в задаче (3.16).24Пример 3.

Характеристики

Список файлов лекций