Ф.П. Васильев - Методы оптимизации (1125241), страница 65
Текст из файла (страница 65)
Полученное противоречие доказывает, что А и В =Я. Итак, А и  — выпуклые множества, А П В = О. По теореме 5.2 тогда существует гиперплоскость ~с, а) = у с нормальным вектором с = (Л; Л!, «' е е Х„Л „„..., Л,) е Е' «! !", с фО, отделяющая множества А и В, а такжеА и В=(Ь=(Ь»;Ь!,«нХ,;Ь „...,Ь): Ь <О;Ь!<0,«ЕХ.,Ь =О,..., Ь, =01.
Это значит, что (с! Ь)=Лад»+~ Л!Ь+ х, 'Л Ь,< у<(с,а)=Л а+2„Л.а!+ 2; Л а. (16) ! «г ! = пз.!- ! '«А при всех он А, Ь я В. Разделив (16) почленно на Ьз < О, где д' = 0 или у' ~ Х„ и устремляя затем Ъ, — — оо при фиксированных остальных Ь!, а, получим Л, > 0 при д' = 0 или Чу Е 1,. Далее полагая в (16) а = (~'(х,), х — х,), а!=(д'(х,),х — х,), «ЕХ„и»=т+1,...,з, где хат!Х, Ь=ОеВ, будем иметь Л»(Х(х), х — х)+ Х, Л,(д(х), х — х )+ 2; Л,(д(х), х — х) > 0 Ухе г! Х. !«1 а=п»! Отсюда, доопределив Л! = 0 при» !» 1„1 <»' < т, получим (Л,Х'(х„) + 2 , 'Л!д,'(х.), х — х„) > 0 Чх б г! Х».
!=! Совершая в этом неравенстве предельные переходы с учетом того, что Х, с Х, = г!Х (теорема 1.13), придем к неравенству (5). Справедливость условий (4), (6) вытекает из определения множества 1, и построения Л = (Л„ ..., Л,). Теорема 1 доказана. П Другое доказательство теоремы 1, а также теорем 2.3.1, 2.3.2, не использующее теоремы отделимости и теорию неявных функции, будет приведено ниже в $5.16 с помощью штрафных функций при несколько более жестких требованиях на дифференциальные свойства функций 1(х), д!(х), « = 1,..., т. Различные доказательства, обобщения и модификации правила множителей Лагранжа см., например, в [5-7; 14; 15; 24; 34; 44; 106; 209; 225; 233; 234; 278; 279; 286; 297; 314; 347; 358; 366; 386; 434; 465; 502; 587; 602; 604; 605; 613; 617; 660; 670; 673; 683; 724; 759; 816].
Замечание 2. Если в конусе Лагранжа Л(е) точки ее Х существуют наборы Л = (Л„..., Л,) с Л, = О, то в условиях (7) — (9) целевая функция «исчезает» и эти условия превращаются в некоторую специфическую характеристику множества (2) в точке е.
Как и в главе 2, выделим класс задач на экстремум функции /(х) на множестве (2), у которых любой элемент Л конуса Л(е) имеет координату Л» ~ О. 216 б 3. ОБОСНОВАНИЕ ПРАВИЛА МНОЖИТЕЛЕЙ ЛАГРАНЖА 217 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА О п р е д е л е н и е 1. Точку е множества (2) назовем нормальной точ кой этого множества, если система (ЯЛ!д!'(о) х — о) >О Чх о.Хо, Л д(е)=0, э =1,..., т, ( ) Л = (Л„..., Л ) ~0, Л, >,..., Л„> О, относительно переменных Л не имеет решения. Система (17) получена из систем (7)-(9) и (7), (8), (10) при Л, = О. Поэтому рассуждениями от противного нетрудно доказать, что в нормальной точке е множества Х все точки Л из конуса Лагранжа Гь(е) имеют координату Лс фО. По аналогии с Э 2.4 можно сформулировать условие Мангасариана— Фрамовица, гарантирующее нормальность точки о из множества (2).
А именно, пусть в (2) множество Х, имеет непустую внутренность и е е я 1п( Х„ векторы д„ „,'(е),..., д,'(о) линейно независимы, и существует вектор й Е Е", для которого (д,.'(е), й) =О, з = т + 1,..., в, (ду(е), й) < 0 Чз' Е 7(е), где Г(е) множество номеров активных ограничений точки е. При о е !и! Х неравенство (ьх(е, Л ), х — е) > 0 Чх Е Х, эквивалентно равенству й,(е, Л) =О, и доказательство нормальности точки о при выполнении перечисленных условий проводится та>оке, как в Э 2.4.
Если в (2) ограничения типа равенств отсутствуют (тп = г), то условие Мангасариана — Фрамовица можно модифицировать следующим образом: существует вектор й е Л такой, что Это >О, что е+ той ЕХе, (д,'(е), й) <О, Чз ~ Х(е). (18) Покажем, что при выполнении условия (18) точка е нормальна. Допустим противное; пусть условие (18) выполнено, но система (17) при т = в имеет хотя бы одно решение Л. В неравенстве (2, Л«ду(е), х — е) > 0 =! ЧхЕ Х, положим х=о+(ой. С учетом (18) получим: 0<(2„Л,.ду(е), (о«1) = «=! Л,(дУ(о), й) < О, что возможно только при Л =О. Однако Л =0 не «ет! ! может быть решением системы (17) при тп = з. Полученное противоречие доказывает, что е — нормальная точка множества (2). Приведем еще одно достаточное условие нормальности точки е из множества (2) при тп = г.
Пусть существует точка х е Х, для которой дг(х) < О, з = 1,..., гп. Это условие в литературе принято называть условием Слейтера. Если выполнено условие Слейтера и, кроме того Х, — выпуклое множество и функции дг(х), з =1,..., т, выпуклы на Х„то, оказывается, выполняется условие (18). В самом деле, положим с( = х — е. Тогда точка х =е+ (й Е Х, при й = !о = 1. Кроме того, из выпуклости функций д,. (х) на Х и теоремы 2 2 следует, что 0 > д (х) = д (х)-д (е) > (ду(о), х — е) ='(д,.'(е), с(~ Чз' Е Х(о). Как видим, условие (]8) выполнено.
Следовательно, е — нормальная точка множества (2) при гп = в. Кратко скажем, что понятие анормальной точки для множеств (2) можно ввести точно также, как в 5 2.4 (определение 2.4.5); тогда в конусе Лагранжа Л(о) существует точка Л с координатой Ля =О, конус Л(е) (.) (О) неострый. Нетрудно привести примеры задач, когда в конусе Лагранжа все наборы Л имеют координату Л,=О. Пример 1. Задача: 7(х)«х — х- !и1, хеХ=(хеХо. д(х)=х'<0), где Хо = (х е Е '.
0 < х < а), а > 0 (возможно, а=+со). Тогда Х = (0) = Х„ 7", = О, функции Лагранжа х.(х, Л ) = — Л х+ Л х', х Е Хо, Л > О. Система (7)- (9) имеет вид: (-Лс+ 2Ле)(х — е) >0 Чх Е Х„, Лез = О, ез < О, Л=(Л,Л)~0, Л >О, Л >О. Отсюда видно, что е = О.
Тогда первое неравенство этой системы дает; — Лсх > 0 Чх Е [О, а], что возмо>кно только при — Ло >О. С другой стороны Л, > О. Следовательно, Л,=О, и конус Л(0) =[Л =(О, Л): Л >О). Упражнения 1. С помошмо пуозвилз множителей Легрзьокз исследовать задачи нз экстремум, если: з) 1(м)=х +У +з, Х =(м=(х У з) Е Хо, х+Уяз=1!<1; > Ц), Хо — — (м=(х У х) ЕЬ': х Д>О), или Хо — — (и =(х, У, з) Е Ьз; х >О, У ~) О), или Хо- Ь+! б) у(м) =и!п(х+ у) — з!пи — з!и у, Х =(м=(х«у) е Хо'.
в+ у д 2я), Хо — — (м=(х, у) е Ь': х > О) или Хо — — Вз, 2. Нвйти решения задач; в) 7(м)«2х з+4хзу з!п(, меХ=(м=(ху)ел~.' х>О,У>О,х у ( Ц; б) у(м) =в+у !х ~«~- !п(, не Х =(м=(х у з) е Ьз; х >О, у >О, з>0, х !у+в !в ( Ц. 3. Найти точки экстРемУма фУнкцни >(и) =/и — о), где о=(с!, оз) Е Яз — заданнаЯ точка, з нв множествах х! —— (не ь',: х" +У д Ц, хз — — (и ее,: х +У" > Ц, хз-— (и е е«: х +У = Ц. У к з з в н и е: изобрззить нз плоскости ЕЗ множества Х н линии уровня функции 7(м).
9 9. Теорема Куна — Танкера. Двойственная задача 1. Перейдем к рассмотрению условий оптимальности для задач выпуклого программирования. Под выпуклым программированием понимается раздел теории экстремальных задач, в котором изучаются задачи минимизации [или максимизации] выпуклых [вогнутых] функций на выпуклых множествах.
В частности, задача ,7(х)- ш(, хеХ (1) Х=ТхеХо; д(х)<0, з=1,...,гп; д(х)=0, з=тп+1,...,в), (2) исследованная в Э 8, превращается в задачу выпуклого программирования, если Х, — выпуклое множество, функции 7" (х), д, (х),..., д (х) выпуклы на Хо, а д,(х) = (а„х) — Ь>, з' = та+ 1,..., г — линейные функции с известными а! е Я", Ь! е И (теорема 2.11).
Такую задачу кратко принято называть выпуклой задачей. Ряд характерных свойств выпуклых задач были отмечены выше (см., например, теоремы 2.1, 2.3, 2.12, 6.4). Важное место в теории выпуклого программирования занимает теорема о седловой точке функции Лагранжа, известная в литературе под названием теоремы Куна — Таккера. Эта теорема дает необходимое и достаточное условие оптимальности в задаче (1), (2), т. е.
условие принадлежности той 218 Гк 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО' АНАЛИЗА или иной точки множеству Х, =(х Е Х: «(х) = 1п1 «(ю) — «)„Д!ля, ф р у ю ох лировки теоремы Куна — Таккера введем функцию Ь(х, Л) =«(х)+ 2; Лгдг(х), (,3)' 1=! называемую в отличие от (8,3) нормальной функцией Лагранжа зада- чи (1), (2), где х е Хо, а переменные Л. =(Л„..., Лг), принадлежат мно- жеству Л =(Л=(Л.„...,Л,)ЕГ: Л,>О,,...,Л >О).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
