В.М. Алексеев, В.М. Тихомиров, С.В. Фомин - Оптимальное управление (1979) (1155777), страница 43
Текст из файла (страница 43)
Предложение. Для того чтобы в теореме ц. 3.2.1 Х, Ф О, достаточно добавить к ее условиям, что 1ш Р' (х) =)' и сущесвтует элемент Ь Е Кег Р' (х), для которого <[1(х), Ь> <О, 1=1, ..., и. Дополнительные допущения, о которых здесь говорится, будем называть условиями усиленной регулярности задачи (1). В формулировке доказанного нами принципа Лагранжа участвует важное (н вдобавок единственное, помимо требований гладкости н банахавости) условие замкнутости образа 1ш Р' (х». Необходимо отметить, что без условий такого типа принцип Лагранжа может оказаться неве ным. режде всего при отказе ат требований сюръективности оператора ЛЕЯ(Х, )') (Х и У вЂ” банахавы пространства) формула (КегЛ)~-=1тпЛ" может оказаться неверной, точнее, может оказаться, что 1ш Л' есть собственное надпространство (Кег Л)х. Например, если Х=У= =1„х=(х,„..., х„, ...)~/„Лх=(х„х /2,..., х /и,...), то КегЛ=(0) и, значит, (КегЛ)к=1„в то время как 1ш Л =1ш Л' ~ 1, (скажем, элемент у=(1, 1/2,..., 1/и,...
) Яба принадлежит 1„но решения уравнения Лх=у, очевидно, не существует).-Теперь мы можем уже привести пример задачи, для которой принцип Лагранжа неверен. П р н м е р. Пусть Х н )г — банаховы пространства и оператор Л Е .У(Х, )') таков, что Кег Ле = (О), а 1т Л' есть собственное подпространство (Кег Л)с. Выбрав х' ~ (Кег Л)~-'~,1т Л', рассмотрим задачу <х', х> (п(; Лх=О. Для этой задачи принцип Лагранжа неверен. Действительно, х=О является точкой минимума, и если бы нашлись )ьа и у'Е)г' такие, что У„(0, р', 1е) ~Ь~=О, тЬ 6Х ее де <х', Ь>+ <у», ЛЬ> О, ч'Ь6Х, то )ье О(ибо иначех*Е!тЛ'), а значит, Л р'=О=; у'=О. Упражнение' ). Пусть Е=)г (а, г=(г„..., г„,. )~)а, Лг=(г„га/2, ..., г„/и, ...), у(!гпЛ, Х=цхЕ, г(г)=г(м, г)=а, г'(г)=Р(а, г)=Лг+аау.
Покажите, что дпя аадачн )(к) — ьгп(; гт (г) =О принцип Лагранжа.неверен. й З.З", Принцип Лагранжа и двойственность в задачах выпуклого программировании 3.3.1, Теорема Куна — Таккера (субдифференциальная форма). Принцип Лагранжа для задач выпуклого программирования (теорема Куна — Таккера) был уже доказан в п. 1.3.3. В этом пункте дается «субдифференциальная форма» этой теоремы и проясняются связи с другими понятиями выпуклого анализа. Пусть Х и)г — банаховы пространства, Л: Х- )г — линейный непрерывный оператор, (г: Х вЂ” К, 1=0, 1, ..., т— выпуклые функции, а=(а„..., а„)ЕЙ'", ЬЕУ, А — выпуклое множество в Х.
Рассмотрим следующую задачу выпуклого программирования: (е(х)- (п1; )г(х)(аг, 1=1, ..., т, Лх=Ь, х~А. (Ь) Множество (х ~ Лх = Ь) обозначим через В. Функцией Лагранжа задачи (Ь) является функция .Ы"(х, у', Ь, Ье) = =- Ье)'е (х) + ~~~~ ~), ((, (х) — а,) + <у', Лх — Ь>. ») Предложено студентом 4 курса В. В, Успенским. Предложение. Луста х — точка абсолютного минимума в задаче (б). Тогда х — точка абсолютного минимума в элементарной задаче 1(х) = щах(~,(х) — ~,(х), 1,(х) — а„..., 1' (х) — а )+ +б(А()В)(х)-+1п1, (Ь') где б(А П В) — индикаторная функция множества А П В.
Действительно, если существует элемент х, для которого ((х) (О, то это означает, во-первых, что хрА, хЕ В(вэЛх=б) во-вторых, что )',(х) ~ а„' 1= 1, ..., т (т. е. что х — допустимый элемент в задаче), н, в-третьих, что ~е(х) < 1,(х) вопреки условию. ° Теорема (субдифференциальная форма теоремы Куна — Таккера). Лусть в (б) функции' ~о 1=0, 1, ..., т, непрерывны в точке хЕ А О В, доставляюи)ей абсолютный минимум в задаче. Тогда найдутся числа Х;)О такие, что ~Х;=1, ХД~(х)=О, 1)1, и с=о элемент х'Едб (А П В) (х), для которых ° О б ~,' Х; д~с (х) +х'.
' (1) Доказательс-тво. Согласно предложению х доставляет абсолютный минимум в элементарной задаче (б'). По теореме 1 п. 3.1.1 О Е д~ (х). Функция у(х) = =гпахД,(х) — ~,(х), ~,(х) — а„.. „1„(х) — а„) выпукла и непрерывна в точке хЕА П В (т. е. принадлежащей дою 6(А (1 В) и, значит, по теореме Моро — Рокафеллара (и. 2.6.4) дг(х) = дд'(х)+дб(А() В)(х). Наконец, по теореме Дубовицкого — Милютина (п. 2.6 4) дд(х) = = сопч(дгц (х) 0... 0д7с,(х)), где Е~ — те н только те индексы, для которых 7с (х) = д(х). Таким образом, существуют два элемента $'Еду(х) и х=Едб(А П В)(х), для которых $'+х'= О, $'Есопч(д~ч(х) 0...
0д5,(х)) ча 5* = Я 5 = Х Х; х,", х),. Е дРс, (х), Х ~с, = 1, ) ) О. Осталось положить Х, = О, Е( (Е„..., 1,). Я 262 Упражнение. Пусть В=(х(Лх=ь). Докажите, что если хеЕВ, то дд(В) (хе)=(КегЛ)х. Следствие 1 (прннцип Лагранжа для задач и выпуклого программирования,с ог р аничениями типа равенств и неравенств). Пусть в условиях теоремы А = Х и образ Х при отображении Л замкнут в !'.
Тогда найдутся такие множители Лагранжа ).оба, або ", у'Е!", что )ьг~)0, !)О, ХД(х)=0, 1:!, ш(п.У(х, у*, )., Хо) =,Я'(х, у, Х, Х,). (2) к Действительно, если 1шЛ есть собственное подпространство в 1', то можно положить г.г = ке = О, у' Е (!ш Л)~-. Если жеЛ вЂ” сюръектнвный оператор„то дбВ (х) =(КегЛ)ь= =1шЛ'. Тогда, согласно (1), ОЕд„.у'(х, у*, г., )о)= = ~~р ~);д(г(х)+1шЛ', и, значит, по определению субг=о дифференциала -~ (х> у ~ )ь, )ье) 2'(», у', а, Ло) — (О х — х))Оеа еа.зг(х у', Х. )ь,)~).2'(х, у*, )., Х,), Ух. ° 3.3.2. Метод возмущений и теорема двойственности, В предыдущем пункте задачу выпуклого програьанирования (Ь) мы рассматривали как одну индивидуальную задачу.
Со многих точек зрения оказывается естественным и плодотворным рассмотрение целых семейств задач подобного рода. Фиксирован (г, Л, ао А и Ь, включим задачу (а) в семейство ),(х) — (п1; )г(х)+а; (аг, 1= 1, ...„т, Лх+т)=Ь, хЕА. (6(а, т))). (Разумеется, можно было бы просто объявить аг и Ь переменными параметрами семейства, но, введя параметры аео т) так, как указано выше, мы получаем более красйвые формулы.) Совокупность задач ((6(а, т())) назовем возмуи(гнием задачи (1) =-(Ь(0, 0)). Мы уже видели в п.
3.3.1, что задача (6) сводится к элементарной. Сейчас мы проделаем то же самое для семейства 3 (а, т)), однако несколько цо-другому. А именно, аев обозначим ( г, (х), если г; (х)+а, (а„Лх+!)=Ь, х ч А, г(х; а, г!) = +ос, в остальных случаях. (1) Тогда семейство (5(а, т))) можно записать в виде элементарной задачи 1(х; а, Ч)- !п( (по х~Х). (2) В дальнейшем, говоря о задаче (в(а, и)), мы не будем различать ее исходную формулировку от (2). Значение этой задацн, т. е. 1п1~„, прн указанных ограничениях является функцией от а= (сс„..., се„) и и, которую мы обозначим через 3, Я: К хУ' К и иногда будем называть $-функцией: 3 (а, и) = !и! Г'(х; ы, Ч) = !и! 1~(х). (3) х хел, Г,.
оо +а~ к ае лх+ч=ь Лемма. Лусть Р(х, г) — выпуклая функция на произведении линейных пространств Х и Е. Тогда функция 5 (г) = 1п1 Р (х, г) х выпукла на х. Доказательство. Пусть (г;, Г)Еер!5, 1=1, 2 и Лб<О, 11. Тогда Я(г,)(1„1=1, 2, и для любого е >О существуют (х„г,) такие, что Р(х;„г,) < г';+е,( ° 1, 2. Отсюда в силу выпуклости Р Р (Лх, + (1 — Л) х„Лг, + (1 — Л) г,) ( а~ЛР (хо г,) 1-(! — Л) Р(х„г,) ( Л(С,+з)+(! — Л)(Г,-!-в) = Л Г, + (1 — Л) Г, + а. Ввиду произвольности е > О Р (Лхг+ (1 — Л) х„Лг;+(1 — Л) г,) ( ( Л Гг+ (1 — Л) Г~ ~ Я (Лг, + (1 — Л) г,) ( (ЛГ,-(-(1 — Л) 1,=О(Лг,+(! — Л) гы Л(,+(1 — Л) 1,) Е ЕР! Я.
ф Предложение 1. Пусть Х и У вЂ” линейные пространства, А т Х вЂ” выпуклое множество, Л: Х вЂ” У вЂ” линейное отобраскение. Если функции 1,; Х вЂ” Ф, 1= О, 1, ..., т, выпуклы, то функция 1(х; а, 1!), определяемая равенством (1), выпукла на Хх К"'х У. дав Доказательство. Множества М, = — ((х, а, т), 1) )(х, 1) ~ер1 Ц, М; = ((х, а, т), 1) 11< (х) + ат . а, ), МА — — ((х, а, т<, 1)) х~А), Ма = ((х, а, т<, 1) ! Лх+ т1 = Ц выпуклы в Х х й" х 'г" х 11. Действительно (нарушая иногда для удобства порядок сомножителей): М, = ер1 (,х Й" х)", МА — — А Х К Х 1'Х й, Ма=Л '(Ь) Х К"'х й, где Л: (х, у) + т-т Лх+у — линейное отображение нз Хху в г' н М< —— =аер111< — а<)ХЙ"-'ХУХЙ, где о: (х, 1) э(х, — Г) симметрия в Ххй.
Отсюда видно, что все зтн множества выпуклы, н остается заметнть, что ер11= П М<ПМАПМл ° <та Следствие 1. Б4унк«ия задачи (й(сс, т))) выпукла на К Хт. В й 2.6 мы уже видели, что выпуклость позволяет сопоставлять различным объектам (функцням, множествам) двойственные объекты в сопряженном пространстве. То же самое справедливо н для задач выпуклого программирования.
Далее мы будем предполагать, что Х н У' — локально выпуклые пространства, Х' н 'г' — нх сопряженные, Х=(Х,... к )б й ' Определение 1. Семейство экстремальных задач у(хе;Х, т)') — зцр(по)<ЕЙ ",т)'ЕУ'). (й'(х')) где ( — 1) д(х', к, т1') =1'(х', к. т)')- преобразование Юнга — Фенхеля (и. 2.6.3) функции (х, а, т1) т-+1(х, а, т<), определяемой равенством (1), называется двойственным к семейству й(а, т))еэ(2). Задача й' = з'(О) называется дво<тсптвекной к задаче 6 =а(0, О) (относительно семейства возмущений й(а, т))). Значение задачи й'(х') обозначим Х(х') = зцр у(х', )т, т)'). <л, ч ) Поскольку функция ~' выпукла, противоположная ей функция у вогнута. Двойственные задачи можно было бы называть задачами вогнутого программирования, но мы предпочитаем обойтись без нового термина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
