Ф.П. Васильев - Методы оптимизации (1125241), страница 64
Текст из файла (страница 64)
(2) где Х вЂ” заданное множество из Е", функции /(х), д (х), с =1,..., з, определены на Ха. Здесь не исключаются возможности, когда отсутствуют либо ограничения дс(х) < 0 типа неравенств (тп = 0), либо ограничения дс(х) =0 типа равенств (з = т), либо оба вида ограничений (тп = з =О, Х = Х ).
— — — о. Если Хо = Я, то получим задачи, рассмотренные в главе 2, Разумеется, и само множество Ха в (2) может задаваться ограничениями типа равенств и неравенств. При выделении множества Хо обычно руководствуются тем, чтобы Х, имело простую структуру, чтобы легко (без трудоемкой вычислительной работы) можно было проверить включение хе Х, указать какую-либо конкретную точку из Хо, чтобы легко было проектировать точку на Х,. В задачах линейного программирования (глава 3) роль Ха играл неотрицательный ортант Я", Часто множество Хо представляет собой параллелепипед Хо = (х = (х',..., х") ю Л": сгс < х' < рс, г = 1,..., и), где сгы /Зг — заданные числа, сг,.</Зг (возможно, некоторые сгс=оо, Дс=+оо) Функция Лагранжа для задачи (1),(2) определяется также, как в главе 2 .С(х, Л) = Ло?(х) + Л,дс(х)+... + Л,д,(х), (3) (4) (6) (6) Сразу же заметим, что при Ха = Е условие (6) эквивалентно равенству С,(х„, Л) =0 — это легко доказывается с помощью тех же рассуждений, использованных в теореме 2.3 в аналогичной ситуации.
Отсюда следует, что при Ха = В" теорема 1 превращается в теорему 2.3.2. Поэтому, доказав теорему 1, мы получим также и доказательство теорем 2.3.1, 2.3,2, Как и в главе 2, числа Л = (Л,..., Л ) из (3)-(6) будем называть множителями где х=(х',...,х")ЕХа, Л =(Ло,...,Л„)ЕЛ'т', Л, >О,..., Л„,>0, Теорема 1.
Пусть множество Х задается условиями (2), гдв Х, — выпуклое множество из Я, функции /(х), дс(х), г = 1,, з, опре- делвньс на Х,. Пусть х„Е Х вЂ” точка локального минимума в зада- че (1), (2), пусть функций /(х), д,(х),..., д„(х) дифференцируемы в точ- ке х„а функции д „(х),..., д,(х) непрерьсвно дифференцируемьс в неко- торой окрестности 0(х„г) й Х, точки х„. Тогда существуют числа Л =(Ло,...,Л,) такие, что Л =(Л„..., Л,) фО, Л, >О, Л, >О,..., Л. >О, (Е,(х„Л), х — х,) > 0 Чх Е Хо, Лс да(х„) = О, г' = 1,..., т.
212 Гл, 4, ЭЛЕМЕНТЫ ВЪ|ПУКЛОГО АНАЛИЗА Лагранжа, соответствующими точке х,; равенства (6) — условиями дополняюи4гй нежгсткости. Будем также придерживаться прежних определений активных и пассивных ограничений: ограничение д,. (х) < 0 активно в точке х„если д,.(х„) =О, и пассивно в точке х„, если д,(х,) < О. Из теоремы 1 следует, что точками локального минимума в задаче (1), (2) могут быть лишь те точки х = е, для которых существуют множители Аагранжа Л =(Ло,..., Л,), такие, что пара (е, Л) е В" +"+ ' является решением системы (Ло1'(е)+ Л,д,'(е)+... +Л,д,'(е), х — е) >0 Чх Е Х„ Л,д,(е)=0, а =1,, гп; еЕХо, д,(е)<0> ..., д,„(е)<0, д „,(е)=0, ..., д,(е)=0, (8) Л фО Ло~)0~ Л )~0 (9) Множество всех тех Л, для которых пара (е, Л) — решение системы (7)— (9), будем обозначать через Л = Л(е), Так как если (е, Л) — решение системы (7)-(9), то пара (е, рЛ) при Чр > 0 также решение этой системы. Следовательно, А(е) — конус, который как и в главе 1, будем называть конусом Лагранжа.
Предлагаем читателю доказать, что Л(е) — выпуклый конус, а конус Л(е) Ы (0) замкнут. 3 а м е ч а н и е 1. Если е — точка локального максимума функции Х(х) на множестве (2), то учитывая, что е — точка локального минимума функции ( — Х(х)), и применяя к ( — Х(х)) теорему 1, получим, что для точки локального максимума существуют множители Лагранжа Л = (Ло,..., Л,), такие, что пара (е, Л) удовлетворяет соотношениям (7), (8), а условие (9) заменяется на ЛфО, Ло<0, Л,>0,, Л >О. (10) множество таких Л образует выпуклый конус, который также будем обозначать через А(е) и называть конусом Лагранжа точки локального максимума. В системах (7) — (9) и (7), (8), (10) условие Л фО можно заменить каким- либо условием нормировки, например, )Л|о = 2; Ло = 1.
Для выявления то=о чек, подозрительных на локальный экстремум (минимум или максимум) достаточно рассмотреть систему (7), (8) с требованием Л, > О,..., Л > О, последовательно полагая в ней Ло =1, Л, = — 1 и Л, = О, 2; Л,'. = 1. При ;=о обсуждении теоремы 2.3 было замечено, что вариационные неравенства (л".,(е, Л), х — е) > 0 Чх Е Х, вообще говоря, могут быть записаны в виде системы и уравнений. Поэтому можно сказать, что система (7), (8) с учетом условий нормировки, содержит подсистему из и+ в+ 1 уравнений с и+ о+1 неизвестными (е, Л ).
Определив решения этой подсистемы и отобрав из них те, которые удовлетворяют остальным условиям (7)-(9) или (10), получим множество точек е, подозрительных на локальный экстремум, и соответствующий множитель Л из конуса А(е). Описанный подход к поиску точек экстремума функции Х(х) на множестве (2), как и в главе 2, будем называть правилом множителей Лагранжа. Д о к а з а т е л ь с т в о теоремы 1 проведем, используя методику книги 1670] (гл. 4, Я 2). Пусть Х, = Х(х,) =(4: 1 < а < гп, д|(х„) =О) — множество номеров активных ограничений в точке х, (возможность 1„= 0 здесь не исключается), пусть ~1,~ — количество номеров Х„, Определим множество А, „Ъ! -''1:о .-'1,; Тогда среди чисел (Л „..., Л,) найдутся отличные от нуля числа, так как в противном случае из (11) следовала бы линейная зависимость векторов е„ ..., е„, представляющих базис подпространства Х ~.
Кроме того, из (11) следует, что Л,(д,.'(х„), Ь) = — 2 , 'а, (е,, Ь) = О, ЧЬ Е 1л|п Хо. '= л+| ~ =! Но (лп Хо=ай Хо — х„, поэтому полагая в этом равенстве Ь=х — х„, хЕа((Хо, имеем: 2; Л,.(д,.'(х,), х — х,) =О Чхе Х саПХо. Отсюда следует, что набор чисел Л =(Л =О, Л, =О,, Л„=О, Л, „..., Л,), где (Л „„..., Л,) фО взяты из предыдущего равенства, удовлетворяют всем условиям (4) — (6).
Теорему 1 остается доказать для случая, когда система векторов тд„+,'(х,),..., д,'(х„), е„..., е ) линейно независима. Покажем, что тогда введенные выше множества А и В не пересекаются. Допустим, что А й П В ф |2|, Тогда найдется точка х Е г1 Х„такая, что ао —— (Х'(х„), х — х,) < О, а,. = (д,.'(х.), х — х,) < О, Чо Е 1„ а,. = (д,'(хч), х — х,) = О, ЧТ = го+ 1,, г.
(12) Обозначим Ь = х — х,, Линейно независимую систему (д,'(х„), ..., д,'(х,), е„..., е„) дополним до базиса пространства В" любыми подходящим образом выбранными векторами е„, „..., е„, „„и введем функции 1|(г, г)=д,.(х„+ оЬ+т), 4 =1,..., г — гп; Х,. (г, $) = (е...,„, т), Е = з — гп + 1,..., и. -:;);о В 3. ОБОСНОВАНИЕ ПРАВИЛА МНОЖИТЕЛЕЙ ЛАГРАНЖА 213 ::1Л Р (11) Л;д (х,)+ ~ а,е, =О, (Л „„..., Л„а...
а„) фО =т+| 214 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Ь 3. ОБОснОВАние пРАВилА мнОжителей лАГРАнжА 215 Рассмотрим систему и уравнений (14-) 1(г, з) = (Х!(г, 1),..., 1.(г,, т)) =0 относительно и неизвестных г = (г„..., г„'). Для доказательства разрешимости системы (14) воспользуемся йзвестйой из математического анализа теоремой о неявных функциях 1327; 350; 352; 534], С этой целью прежде всего заметим, что /(О, О) = О. Далее, функции /!(г, г) непрерывно дифференцируемы в окрестности точки (О, 0), причем с учетом (12), (13): Таким образом, якобиан '"' "1 системы (14) в точке (0,0), предо(Л" у) аХ(о, о~ ставляющий собой определитель квадратной матрицы †~~ †) со строками д „'(х.),..., д,'(х.),е„..., е„,«, образующими базис в Е", отличен от нуля.
Все условия теоремы о неявных функциях выполнены. Согласно этой теореме существуют непрерывно дифференцируемые функции т = г(з) = = (г!(г),..., г„(г)), определенные при всех $, !»'] < 1», где» вЂ” достаточно малое положительное число, и такие, что ,(0)=0, /(т(г), з)аз 0 Ч1, ]г]< з, Дифференпируя последнее тождество по 1, получаем а1(р» „(1)+а1(ГЫ.аваО ],]< Ц Отсюда при г =0 с учетом равенства д»' - =0 будем иметь: — у.'- т (0) = , дХКЬО! ау(оо, о~ ! =О, Однако матрица ~ невырожденная, поэтому г (О)= О. Это значит, что г(г) = г(0) + гг'(0) + о(г) = о(г), т. е.
11!и г(г)/1 =О. Таким образом, найдена вектор-функция г(г) = (г!(г),..., г„(г)), для которой д!(х„+»(хс — х„) + г(»)) =О, » = т+ 1,..., з, (е!, г(т)) =О, » =1,..., 㻠— а+ т, ~»] <»„! 1пп т(»)/1 =О. (15) Покажем, что по кривой х = х(1) = х„+ 1(т, — х.) + г(1) можно двигаться, оставаясь в множестве Х при всех г, 0 < 1 < г!,*где 1! — достаточно малое число, 0 < г! < ш!п(г„; Ц. В самом деле, равенства (е!, г(г)) = О, «' = 1,... ...,Р, означают, что г(т) е 1.!и Х,. Кроме того, х е г! Х„!пп г(г)/г = О, поэтому х+г(1)/! и Х«при всех малых 1. Тогда, учитывая выпуклость Х, имеем х(г) = г (х + г(г)/г ) + (1 — г )х, н Х, тг, 0 < т < 1!.
Далее, первые авенства (15) означают, что д!(х(1)) = О, 0 < г < Ф„Ч«' = т+ 1,..., з. окажем, что д!(х(»)) < 0 Ч1, 0 < 1 < Гн и !!!» = 1,..., т. Если «Е Х„, то д!(х.) =О, и с учетом (12) имеем д!(х(г )) = д (х,) + (д,.'(х ), Г(х — х ) + г(»)) + о(») = = З((д,.'(х„), х — х,) + (д,.'(х,), г(»)/1) + о(»)/»] < 0 при всех малых г > О. Если» ф Х., 1 <» < т, то д!(х„) <0 и в силу непрерывности д,.(х) неравенство д,(х(1)) =д!(х, + г(х — х,)+ г(1)) <О также сохранится при всех малых г > О. Таким образом, существует достаточно малое число т! > О, такое, что х(г) и Х при всех г, О < т < г!.
Берн при необходимости г! еще меньшим, с учетом (12) имеем У( (1)) — Х(х,)=З ~(Л'(х.), х — х.)+(1!'(х„), (З)/1)+-'(»-)1 <О !ХЗ, О< т < 1!. Однако х(г)- х, при 1 — 0 и х(1) и х, 0 < г < $„и последнее неравенство противоречит тому, что х, — точка локального минимума в задаче (1), (2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
