Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 66
Текст из файла (страница 66)
Приведем еще одно достаточное условие нормальности точки у из множества (2) при тп = з, Пусть существует точка х Е Х, для которой дг(х) < О, з = 1,..., тп. Это условие в литературе принято называть условием Слейтера. Если выполнено условие Слейтера и, кроме того Хо — выпуклое множество и функции дг(х), з = 1,..., т, выпуклы на Хо, то, оказывается, выполняется условие (18). В самом деле, положим с] = х — у. Тогда точка х=у+ьа ЕХо при с = 1о=1.
Кроме того, из выпуклости функций д,.(х) на Х и теоремы 2 2 следует, что 0> д (х) =д (х) — д (у) > (дл(у), х — у) ='(д,,'(у), с(~ Чз' Е 1(у). Как видим, условие (]8) выполнено. Следовательно,у — нормальная точка множества (2) при т = з. Кратко скажем, что понятие анормальной точки для множеств (2) можно ввести точно также, как в $ 2.4 (определение 2.4.5); тогда в конусе Лагранжа А(у) существует точка Л с координатой Ло = О, конус Л(у)() (0) неострый. Нетрудно привести примеры задач, когда в конусе Лагранжа все наборы Л имеют координату Л =О. Пример 1.
Задача: 7(х)ес — х- !п], хеХс=(хеХо: д(х)=х'<0), где Х =(хеЕ'. О< х< а), а>0 (возможно, а=+со). Тогда Х=(0) =Х„ 1, = О, фУнкциЯ ЛагРанжа й(х, Л) = — Лох+ Лх', х Е Хо, Л > О. Система (7)- (9) имеет вид: (-Ло+ 2ЛУ)(х — У) ) 0 !гх Е Хо ЛУ~ =О, Уз < Оз Л =(Лшл)~0 Л >О Л >О. Отсюда видно, что у = О. Тогда первое неравенство этой системы дает; — Л х > 0 Чх е [О, а], что возможно только при -Ло > О. С другой стороны Л > О. Следовательно, Л, = О, и конус Л(0) = (Л = (О, Л): Л > 0). Упражнения 1. С помощью правила множителей Лагранжа исследовать задачи на экстремум, если: а) 1(м) = а +у +з, Х =(м=(х, у, з) еХо, а+у.из=11< 1; > 1]), Хо —— (м=(чу, з) еЕ; е>0), или Хо — — (м=(а,р,з)ЕЕ~: м)О,У~)0), или Хо — -Ез; б) 1(о) =Ми(и+У)-Мил — з!и У, Х =(м=(ж У) Е Хо, с + У < 2а), Хо — — (и =(ж, У) ЕЕ: а >О) или Хо-— Ез.
2. Найти решения задач: а) Пм)=2м ~+4езу з!п1, оеХ=(м=(жу)еЕз: з>О,У)о,а~у~<1]; б) 1(м)=а+у з П~-~!и1, меХ=(м=(м у з)еЕ~: м>0, у>о,з)о,м у+а а<1). 3. Нейти точки экстремума функции 1(м) = ]о — а]з, где о= (а!, аз) е Ез — з!щаиная точка, иа множествах Х! — -(иеЕ: а~+у <1), Хз — — (обЕ; и +у ~ )!), Хз=(ми Еь! а +У =1) Указание: изобразить на плоскости Е множества Х и линии уровня функции 1(м), 9 9. Теорема Куна — Таккера. Двойственная задача 1. Перейдем к рассмотрению условий оптимальности для задач выпуклого программирования.
Под вььпуклым программированием понимается раздел теории экстремальных задач, в котором изучаются задачи минимизации [или максимизации] выпуклых [вогнутых] функций на выпуклых множествах. В частности, задача 7(х) — !п11 х Е Х (1) Х = (х Е Х : д (х) < О, з = 1,..., тп; д (х) = О, з = тп + 1,..., з), (2) исследованная в Э 8, превращается в задачу выпуклого программирования, если Х вЂ” выпуклое множество, функции 1(х), д,(х),..., д (х) выпуклы на Х, а д,. (х)= (аз, х) — (!о з' = т+1,..., з — линейные функции с известными а! е Е", ]!,. е ]к (теорема 2.11). Такую задачу кратко принято называть выпуклой задачей. Ряд характерных свойств выпуклых задач были отмечены выше (см., например, теоремы 2.1, 2.3, 2.12, 6.4). Важное место в теории выпуклого программирования занимает теорема о седловой точке функции Лагранжа, известная в литературе под названием теоремы Куна — Таккера.
Эта теорема дает необходимое и достаточное условие оптимальности в задаче (1), (2), т. е. условие принадлежности той 218 Гп 4. ЭЛЕМЕНТЫ, БЫНУКЛОГО АНАЛИЗА или иной точки множеству Х,= (х е Х:7(х);= 1п1 У(т«) = !.)-Для формуох лировки теоремы, Куна — Таккера введем функцию Ь(х«Л) =Дх)+ 2 Л!д!(х)4 (,3)! называемую в отличие от (8,3) нормальной функцией Лагранжа задачи (1), (2), где х е Хо, а переменные Л, = (Л„..., Лч) принадлежат множеству И, =(Л = (Л,„..., Л,) е Е'! Л, > О,..., Л„, > О). (4) Определение 1. Точку(х, Л*)е-ХонИ называют свдловой точкай функции Лагранжа, (3),, если.
Х,(х., Л) < Х(х., Л") < Х(х, Л )! !ГхЕ Хо, Л ЕИо. (5) Прежде чем переходить к выяснению связи между седловой точкой функции, Лагранжа и решением задачи (,1), (2)«дадим другу!о равносильную (5). формулировку определения еедловой точи«и. Л'ем ма 1. Для того чтобы точка (х„Л*) ЕХ хИо, была свдловой точкой функции Лагранжа, необходимо и достаточно, чхтобы выполнялись следующие угловая: «(х,Л*)<Ь(х;Л ), ох*ЕХо (6) Л1,*.д!(х,) = О, 4 = 1,..., гп, хч Е Х. (7) Подчеркнем, что в лемме 1«от множеств Х,, и, функций Дх), д,(х), 4 = = 1,..., г, не требуется ни выпуклость, ни какая-либо гладкость — здесь важно то, что Х, ф'О и функции 7(х), д,(х)', 4 = 1,..., в, определены, и конечны на Хо. Д о к а з а т е л, ь е т в о.
Н е о б х о д и м о с т ь.. П«усть (х„Л*).е.Хо х Ио— седловая точка. Тогда условие (6) представляет собой правое неравейство (5). Остается получить, условия (7). Для, этого перепишем левое неравенство (5) с учетом, конкретного вида.(3), функции Лагранжа: ,Г'(х,)+ Т: Л,д,(х,) <7(х,),+ ~.- Л;:д,(х.) ~Л ЕЛ,. Отсюда имеем 2,'(Л,".' — Л!)д!(х„) >.0 ЧЛ ЕИ, (9), '=1. Покажем, что х, е Х. Возьмем точку Л =(Л.„..., Л:,), где Лз = Л;. + 1 при некотором у„1' <.у' < т, и Л„. = Л,,*. при всех остальных 4 = 1,..., г (44 ~ т'). Из определения (4) множества И и из того, что Л* е Л„следует,.что выбранная точка Л Е Ио. Из (9) при таком Л получим:( — 1«)д;(х,,)! ! О', т. е.
д)(х,) < 0 при всех У = 1,..., гп. Далее, пУсть Л =(Л„...«Л«,),— точка с кооРдинатами Лт = Л,*. + д.(хи) при некотором тй гп+ 1 < у < г, и Л! = Л,". при всех 4 = 1,..., г, 4 ф т'. Ясно, что Л Е Ио. ПоэтомУ из (9) имеем — )д1(х„)~о'> О, т. е. дз(х ) =0 пРи всех т, = пъ+ 1,..., г. Таким образом,, доказано, что х, е Х,. Возьмем, точку Л =(Л„..., Л,) с координатами Лз =О.при некотором,уо 1 < ~' < гп, и Л! = Л,*. при всех остальных 4 = 1,..., г, й ф у'.
Такая точка принадлежит И„поэтому ив, (9)' получим 0 < Л,*.дз(х.). Но Л,;. > О, дз(х.) < < 0 при д', = 1«...«гя, поэтому последнее неравенство возможно лишь при Л,*,дз(х,) =0:, 4' = 1,...,гп, Все соотношения (6), (7) получены. 4 Э. ТЕОРЕМА КУНА — 'ТАККЕРА.
ДВОЙСТВЕННАЯ ЗАДАЧА 219 До с тат оч н о от ь. Пусть для некоторой точки (х., Л*)ЕХохИ, выполнены соотношения (6), (7). Покажем, что тогда «(х„, Л') — седловая точка. Из (61 следует правое неравенство (5). Остается доказать левое неравенство (5). По условию (7) х. е Х, т. е. д,.(х.) < О, 4 = 1,..., гп, д!(х.) =О, 4 = т + 1,..., г. Тогда (Л;. — Л,.)д!(х.) = 0 (10) при всех 4 = гп + 1,..., г и всех тех 1, 1 < 4 < гп, для которых д,.(х,) = О. Если д !'х,) < 0 при некотором 1, 1 < 4 < гп, то из равенства (Г) следует, что Л;. =О.
11оэтому (Л,* — Л!)д (х )= — Л,:д (х ) >Одля всех Л! >0«1 <4 <гп, для которых д!«(и„) < О. Складывая яолучейные неравенства «с '(10), будем иметь 2',,(Л,* — Л,)д!(х,).>'О,для всех Л ЕИо. Отсюда 2,' Л,д,(х,) < 2 Л,*.д,.(х,) при 1=! 1=1 всех Л е И . Добавляя,к обеим частям этого неравенства 7(х ), придем к о, неравенству (8), представляющему собой левое неравенство (5), П Если сделать«дополнительные предполож«ения о выпуклости и гладкости задачи (1), (2), то лемму '1 можно переформулировать в следующей так называемой дифференциальной форме.
,Л е,м м а '2. Пусть,(1),,(2) представляет собой задачу выпуклого программирования и функции Дх), д,(х),..., д (х) дифференцируемь1 в точке х„е Х,. Тогда дфля того чтобы точ1оа (х., Л') е Хо х И 'была се- ловой точкой функции. Лагранжа,,необходимо и достаточно, чтобы (С,(х„, Л"), х — х„') = (7',(х,)+ ~, 'Л,*д«!(х,), х — х„) >~ 0 Чх Е Х„(11) «=! Л,',д„(х.')=О, 4 =1,, гп, х, Е Х (12) Д о:к а з а т е.л ь,ств о. При сделанных предположениях. функция Лагран- жа (3) выпукла и,дифференцируема в точке .х„е Хо при каждом Л е И.
Поэтому условие (6) согласно теореме 2.3 равносильно условию (11). Усло- вия (7) и (12) совпадают, П Теперь выясним', как связаны между«собой седловая точка функции Ла- гранжа и!решение задачи (1),,(2). Т е о р е м а 1. Пистщ(х,„Л')ое Х хИ вЂ” седловая точка функции Ла- гранжа. Тогда х„е Х„7",=Т,(х„Л*)=Г(х), т. е. х. является решением задачи (1), (2). * Д о к а з а т е л!ь с !г в о.
Из условия (7) имеем х, н Х и Ь (х., Л ) = Г'(х,). Тогда неравенство (6) перепишется в виде ,?(х,) < Х.(х, Л") = У(х) + '1 Л,""дг(х), х Е Хо. (1'3) «=! 'В частности, (13) верно и для всех хЕХ.,Но 2', Л,*д,(х)<0 при хЕХ, так как тисда д!(х):«О и Л,*>0 при (='1,..., «и и д,(х)=0 цри а=та+1«..., г. Поэтому из,(13) следует, что 7(х„)<Х (х, Л*)<7(х) при всех х Е, т, е. х,еХ,. П Заметим, что теорема 1, как и лемма 1,,доказаны без каких-либоюграни- чений на функции 7'(х), д,,!(х), ( = 1,,..., в, и на множество Х;.в частности, никакие предположения о выпуклости, сделанные ныше при формулировке задачи (1), (2), мы пока не использовали.
2. Возникает вопрос: во всякой ли задаче вида !(1), (2) функция Лагранжа имеет седловую точку? Ответ здесь, конечно,.отрицательный: если в зада- 220 Гк 4, ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА $ 9. ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 221 че (1), (2) Х„= И, то, как следует из теоремы 1, функция Лагранжа такой задачи не может иметь седловую точку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
