Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 19
Текст из файла (страница 19)
Вместо отдельного исследования систем (6), (?) ~=о можно рассмотреть одну систему С (х, Л) = Ло~'(х)+ 5' ,Л,д.'(х) = О, д,(х) = О, 1 = 1,, в, з =! (л„л„..., л,) Фо, последовательно полагая в ней Ло = 1, Л, = — 1 и Л, = О, 2 Ло = 1. '=! Система (8) с учетом условий нормировки представляет собой систему и+в+1 уравнений с и+в+1 неизвестными (х, Л) =(х',..., х", Л„л„... ..., Л,).
Решив ее, мы найдем точки х = о множества (1), подозрительные на экстремум, и соответствующие им множители Лагранжа Л = Л(о). Для выяснения того, будет ли в этих точках в действительности реализовываться локальный минимум или максимум, нужно провести дополнительное изучение свойств функции ?(х) в окрестности точки о с учетом ограничений (1). Здесь могут быть привлечены геометрические, физические и т.
п. соображения. При выполнении. условий теорем Вейерштрасса из $1 можно быть уверенным, что хотя бы одна из найденных точек о окажется точкой глобального минимума или максимума. Для выяснения характера экстремума точек о могут быть привлечены вторые производные функции Лагранжа по переменной х — об этом речь пойдет в Э 5. 63 4 3. ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ 62 Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА Изложенная схема поиска экстремума функции на множестве (1) составляет суть правила (метода) множителей Лагранжа.
Для иллюстрации этого правила рассмотрим несколько примеров. Пример 1. Пусть требуется на п-мерной единичной сфере Х = = (х е Е": ~х~' = (х, х) = 1) найти точку, сумма квадратов расстояний от которой до р данных точек х„..., х, была бы минимальной. Иначе говоря, ь нужно минимизировать функцию Г(х) = 2,' (х — х,.!' при условии д(х) = = (х, х) — 1 =О. Как и в примере 2.2, здесь удобнее пользоваться следчющим Р Р представлением функции Т(х) = р(х!' — 2р(х, то) + 2 (х,)о, где хо = — 2 х! р = ~=! Составим функцию Лагранжа этой задачи: л",(х, Л) = Л т" (х)+ Л ((х, х) — 1).
Система (8) имеет вид й,(х, Л) = 2рЛо(х — хо)+2Лт, =О, (х, х) = 1 (Ло> Л) т-О. (9) При Ло =0 эта система, очевидно, не имеет решения. Поэтому здесь можем принять Л, = 1 или Л = — 1. При х ФО из системы (9) получаем две точки: о = -">- и с = — ~, подозрительные на экстремум. Соответствующие этим !о! ' 1~Г точкам множители Лагранжа нетрудно выписать явно. Однако они нам ниже явно не понадобятся, важен лишь факт их существования. Поскольку Х компактное множество, функция т(х) непрерывна на Х, то согласно теоремам 1.1, 1.4 эта функция достигает на Х своего глобального минимума и максимума. Но точки глобального экстремума, конечно же, удовлетворяют системе (9).
Но система (9) при т Р'= 0 имеет всего два решения х! и о,. Следовательно, одна из этих точек является точкой глобального минимума, другая — точкой глобального максимума. Вычислив и сравнив значения Т'(о!), Т"(о,), нетрудно убедиться, что о, = то — точка глобального минимума со значением 1(о,)=Т",=р — 2~2„х,,~+ 2 х,.', о,= — ~~~ — точка Р ! Р глобального максимума со значением Т(о,) =т"'=у+2~ 2; х,.~+ 2, 'хо. По!=! скольку при х ~ О у функции Г(х) других точек экстремума на Х нет, то > (о!) <Г(х) ох 6 Х, х>ьхо и >(х) <Г(оо) чх ЕХ, хфох т. е.
экстремумы строгие. Рассмотрим случай х = О. Тогда системе (9) удовлетворяют все точки о, для которых ~о ~ = 1. Это значит, что из необходимых условий экстремума (9) при т = 0 нам не удалось извлечь никакой полезной информации — все точки единичной сферы как были, так и остались подозрительными на эк- Р стремум. Однако нетрудно убедиться, что при х =О Т'(х) = р+ 2; х,'. = сопз1 о=! 'о!х е Х, и рассматриваемая задача стала тривиальной: можно сказать, что все точки х е Х являются точкой абсолютного минимума (или максимума).
П р и м е р 2. Определим точки экстремума функции Г(и) = х на множестве Х = (и = (х, у) е Е'! д(х) = х' — уо = О). Функция Лагранжа здесь равна й(и, Л) = Л х+ Л(хз — у'). Система (8) запишется в виде: Ло+3Лх~=О, — 2Лу=О, хо — у>=0, (Л Л)фО Из этой системы находим единственную точку о = (О, 0), подозрительну>о на экстремум. Ей соответствует конус Лагранжа Л(о) = (Л = (Л, = О, Л): !!!Л ф 0). Нетрудно видеть, что точка о = 0 в этой задаче является точкой глобального минимума. В самом деле, из равенства хз — у'=0 следует, что Т(и) = х=(у')'П > 0=1"(0) =г', Чи Е Х.
Здесь Г" =+со. 2. Изложим правило множителей Лагранжа для задачи поиска точек экстремума функции г"(х) на множестве, имеющем более общий вид; (10) Х = (х Е Е": д,(х) < О,, д (х) < О, д „,(х) = О,..., д,(х) =0), где предполагается, что функции Т"(х), д,(х), , д,(х) определены на всем пространстве Е". Ограничения д>(х) = О, Е = гп + 1,...,в, как и в (1), будем называть ограничениями тйпа равенств, а ограничения д,.(х) < О, о = 1,..., гп — ограничениями типа неравенств.
В (10) не искл>очаются возможности, когда отсутствуют ограничения типа равенств (е = гп) или типа равенств (гп =0); при г = гп = 0 множество Х = Е" получаем задачу на безусловный экстремум из Э 2. Для исследования задачи поиска экстремума функции Т"(х) на множестве (10) введем функцию Лагранжа л,(х, Л) = Ло,1'(х) + ~ Л д (х) ,=! переменных х е Е", Л е Е"+', внешне ничем не отличающуюся от функции (3), но здесь, оказывается, достаточно ограничиться рассмотрением лишь неотрицательных множителей Л„..., Л.„соответствующих ограничениям типа неравенств.
Т е о р е м а 2. Пусть х„— точка локального минимума функции Т(х) на множестве (10), функции г"(х), д,(х),..., д (х) дифференцируемы в точке х„функции д„~>(х),..., д,(х) непрерывно дифференцируемы в некотог>ой окрестности точки х,. Тогда существуют множители Лагранжа Л = (Л',..., Л;) такие, что Л тОО, Ло)~0, Л!~)0, Л" ))О Ю (х Л*)=0 Л*д.(х)=0 4=1 гп Отметим, что теорему 2 в литературе иногда называют теоремой Каруша — Джона 1234; 5861. Доказательство этой теоремы требует развития некоторого математического аппарата, и оно будет ниже проведено двумя способами для несколько более общих множеств, чем (10) (см. $4.8, Э 5,16).
Из теоремы 2 следует, что точками локального минимума функции Т(х) на множестве (10) могут быть лишь те точки х Е Е", для которых существуют множители Лагранжа Л = (Л,..., Л,), такие, что пара (х, Л) является решением системы ЛоР(х)+ 2 Лзд'(х) =О, Л>д(х)=0, д(х) <О, о =1,...,т, !'= ! д(х)=0, 4=о>+1,...,г, ЛФО, Л >О Л >О, ..., Л )О. (11) Пусть о — какая-либо фиксированная точка локального минимума функции ~(х) на множестве (10), Множество всех точек Л, для которых пара 64 З 3. ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ Гл. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА (х = и, Л) является решением системы (11), будем называть множителями Лагранжа, соответствующими точке и, и будем обозначать через Л = Л(и).
Нетрудно видеть, что если (и, Л) — решение системы (11), то (и, свЛ) при всех а > О также является решением этой системы, так что Л(о) — конус. Этот конус, как и в случае множества (1), будем называть конусом Лагранжа точки и. Равенства Льде(х) =О, 4 =1,..., гп, из (11) принято называть условиями дополняющей нежгсткости. Если д,.(и) < 0 при некотором в, 1 < ь' < пь, то из условия дополняющей нежесткости следует, что координата Л, =0 у всех Л е Л(и); с другой стороны, если у некоторого набора Л е Л(и) оказалось, что Ль > 0 при некотором ь', 1 ( ь' ( гп, то соответствующее д,(и) = О. Ограничение д,(х) < 0 называется активным в точке и, если дв(и) =О, и пассивным (нвактивным) в точке и, если дв(и) <О.
Ограничения дв(х) =О, в = тп+ 1,..., з, в любой точке и е Х, конечно, являются активными. Замечание 2. Как и выше (см. замечание 1), нетрудно убедиться, что точки и локального максимума функции 1'(х) на множестве (10) и соответствующие им множители Лагранжа Л являются решением системы Ло,1'(х)+ 2 Л,д,'(х) =О, Л,дв(х) =О, д,(х) <О, ь =1,,т, д(х)=0, в =ив+1,..., з, Л=(Ло Л1 Л,)ФО Ло(0 Л1)0, ..., Л„,)0. (12) Множество всех Л, для которых пара (х = и, Л) является решением си- стемы (12), будем обозначать через Л (и).
Множество Л (и) и здесь будет конусом, и его также будем называть конусом Лагранжа. Отличие этого конуса от конуса, соответствующего точке локального минимума в том, что здесь у всех точек Л е Л (и) координата Ло < О. Такие соглашения о знаке Ло, как уже отмечалось в замечании 1, несмотря на всю свою условность, позволят нам несколько унифицировать дальнейшее изложение. Так как Л(и), Л (и) конусы, то в системах (11), (12) условие Л ФО можно заменить каким-либо условием нормировки, взяв, например, ~А~в= 2 Л,'.=1.
ь=о Вместо отдельного исследования систем (11),(12) можно рассмотреть одну систему С,(х, Л)=ЛоГ(х)+ 2 Л,д(х)=0, Льд(х)=0, д(х)(0, т=1 ь = 1,..., т, дв(х) = О, ь' = гп + 1,..., з, Л=(Л„Л„...,Л,)~0, Л,>0, ..., Л„)0, (13) е полагая в ней последовательно Ло=1, Ло= — 1 и Ло=О, е', Л, =1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
