В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 12
Текст из файла (страница 12)
Составить функцию Лагранжа: ж(*,)) - Х),~,(х). «-о (0|раничение х«вА в функцию Лагранжа не включается.) 2. Выписать необходимые условия минимума! а) принций минимума ш(пЯ'(х, Х) =2'(х, Х); х~а л б) условие дополняющей нежесткости 34(х) О, (=1, ..., т; 68 в) условие неотрпцательностп ).,>О, 8=0, 1, ..., и.
3. Найти критические точки, т. е. допустимые точки, удовлетворяюшие условиям и. 2. При этом бывает полезно рассмотреть отдельно случаи т, = 0 и Л, Ф О. Во втором случае можно положить Х, равным единице пли любой другой положительной константе, Если выполняется условие Слейтера, т, е. существует точка х ~з яА, для которой ~,(х) (О, 1= — 1, ..., т, то Х,ФО. 4. Если критическая точка найдена при Х,чьО, то она является решением задачи. Если она найдена при )., = О, то требуется дополнительное рассмотрение того, доставляет она минимум или нет. Правило решения выписано в соответствии с принципом Лагранжа. Соотношение а) показывает, что необходимые условия минимума функционала в задаче с ограничениями являются необходимыми условиями минимума функции Лагранжа, в которую включены все ограничения, кроме ограничения типа включения.
Условия б) и в) являются обычными условиями дополняющей нежесткости и неотрицательности, присущими принципу Лагранжа в задачах с неравенствами (см. $2). 4.1.3. Теорема Куна — Таккера. Т е о и е и а. 1. Пусть Х вЂ” линейное пространство, ~ь.' Х- й, 1 О, 1, ..., т,— выпуклые функции на Х, А — выпуклое подмножество Х. Тогда, если х является решением задачи выпуклого программирования, то найдется ненулевой вектор множителей Лагранжа ). (),„Х„..., Х ) какой, что выполняются: а) принцип минимума для функции Лагранжа ш(п 2'(х, ),) = 2'(х, ).); б) условие дополняющей нежесткости Х4(х) =О, 1 1, ..., тп; в) условие неотрицательности Х>О, 1 0,1,...,т.
2. Если Х, чь О, то условия а) — в) достаточны для тоео, чтобы допустимая точка х была решением задачи. 3. Для того чтобы Х, чьО, достаточно выполнен(гя уе ловия Слейтера, т. е. существования точки х взА, для которой ~,(х) ( О, ~ ° 1...,, т (АТФ, с. 52). 4Л.4. Задачи без ограничений. Выпуклой задачей без ограничений называется слелуюшая задача: ~(х) - 1п1. (з) Здесь ~: Х вЂ”  — собственная выпуклая функция, отображаюшая некоторое линейное пространство Х в расширенную прямую. Т е о р е и а (аналог теоремы Ферма). Для того чтобы точка х доставляла в задаче (з) абсолютный минимум, необходимо и достаточно, чтобы выполнялось соотношение 0 я д~(х). < Необходимость.
х я аЬз т1п з =~ ~(х) — ~(х) ~ ~ 0 = <О, х — х > =~- 0 вз о~(х). Достаточность, О~д~(х) =~ ~(х) — ~(х) ~ <О, х— — х> 0.=~- х~ аЬзш1пз. ~> 4.2. Теория двойственности. 4.2Л. Двойственность экстремальных задач. В предыдущем параграфе говорилось о том, что выпуклые объекты допускают возможность двойного описания, В частности, это относится и к выпуклому программированию. Основной принцип построения двойственной задачи состоит в следующем. Пусть нам дана задача минимизации ~(х) — пй, х в- =Х, (з) где Х вЂ” некоторое линейное пространство, а (: Х- В— функция на Х. Ее включают в класс подобных задач, зависяшпх от некоторого параметра (который мы обозначим через у), пробегающего другое линейное пространство У. Иначе говоря, рассматривают серию задач Е(х, у)- 1п1, хвзХ, (з(у)) где Г: ХХ У- В, Е(х, 0) =~(х).
Функцию Р называют возмущением ~, а серию (з(у))— возмущением (з). Разумеется, возмушения можно выбпрать самыми разными путями и в зависимости от зтого будут получаться различные двойственные задачи. Стараются подобрать возмущение так, чтобы функция Р была выпуклой. Численное значение задачи (з(у)) обозначают через Яу) и называют Б-функцией серии (з(у))„ 7о Лемма $. Пусть функция (х, у)~- Е(х, у) выпукла на произведении линейных пространств Х и У. Тогда Б-функция йу) 1пгГ(х, у) также выпукла на У, 4 Это — простое следствие определений; см. АТФ, с.
264. 1> Предположим теперь, что функция Я замкнута в-нуле, т. е. Я**(0) Я(0). Это предположение, разумеется, выполнено не всегда, но очень часто можно опереться на следующий результат. Л е м м а 2. Пусть Х вЂ” нормированное пространство, ~:Х- В. а) Для того чтобы собственная выпуклая функция была замкнутой в некоторой точке, достаточно, чтобы она была непрерывной в этой точке. б) Для того чтобы выпуклая функция была непрерывной во внутренней части своей эффективной области, достаточно, чтобы она была конечной в некоторой точке области и ограничена сверху в некоторой окрестности этой точки (АТФ, с. 219).
Итак, пусть Я выпукла и замкнута в нуле. Вычислим сопряженную функцию Я*, предполагая, что Х и У— нормированные пространства, а Х~, У~ — их сопряженные. Имеем ях (у*) = яир ((у*, у) — я (у)) яир((ух, у) — М Е(х, у)) Р Р яир яир ((у*, у) — Р (х, у)) = яир ((у*, у) — Р (х, у)) = з х (хан вот = яир((0, х) + (ув, у) — Р(х, у)) =Р" (О, у*). (х,д) бет Отсюда Я (0) = Ю~*. (0) = яир ( — Р* (О, ух)). у ~ф Таким образом, численное значение (з) оказывается равным численному значению следуюшей задачи: ср(у*) — яир, (зх) Ф(х*, у*) = — Е*(х*, у*) — яир, (з*(х~)) ~(у*) =Ф(О, у ).
)(х) = Р(х, О), <р(у"')- яир, у*~ У*, (з*) где фу~) — Р*(0, у*). (з*) называют двойственной к (з) по отношению к возмушению (з(у)). Мы пришли к следуюшей схеме: (з) )(х) — 1пт; (з(у)) Е(х, у) — 1пг; Если Я выпукла и замкнута в нуле, то значения прямой и двойственной задач совпадают, Зачастую двойственная задача проше исходной, а иногда у двойственной сушествует решение, в то время как у прямой решенин нет. Далее мы применяем описанный метод к обшей задаче выпуклого программирования. Равенства ЯО) = Б(0) = Я**(0) основывают обычно ка теореме Фенхеля — Моро, о которой говорилось в и. 3.2 1. 4.2.2.
Теорема двойственности для задач выпуклого программирования. Пусть Х и У вЂ” нормированные пространства, 7'„Х- В, 1=0, 1, ..., и,— выпуклые функции на Х, Л вЂ” линейный непрерывный оператор из Х в У, А с=Х вЂ” выпуклое множество, Ьв- =У, а,вз В, 1=1, ... ° ., и. Задачу ~о(х) 1п1; ~~(х) ~ао г 1, ..., и, Лх Ь, хеА, (з) включим в семейство задач ~,(х) - 1п1; (з(а, т))) 7,(х)+а,~ а„г= 1, ..., и, Лх+г) = Ь, ха: А. С емейство (з(а, ~))) является возмущением задачи з — з(0, 0). Положим ),(х), если 7',(х) + а,(а„Лх+ Ч = Ь, хе-=А, Г(х,'а, Ч) = + оо в остальных случаях, Тогда з(а, ц) можно записать в виде злементарной за- дачи (з(а, т~)) ~=:. Р(х; а, г)) - 1п1 (по х вз Х).
Численное значение з(а, т)), т. е. 1п17,(х), при указанных ограничениях обозначим через Я, Я: В"'Х У- В, и будем называть Я-функцией: Я(а, т)) ЫГ(х; а, ~)). х Ле м ма 1. При сделанных выше допущениях функция Р(х; а, ~)), определяемая равенством (1), выпукла на ХХВ'"Х У (ЛТФ, с. 264), Отсюда и из леммы 1 предыдущего пункта следует выпуклость Я-функции семейства (з(ад)), 72 Л е и и а 2. Сопряженная функЦия к Б-функции семейства (з(а, т))) имеет вид — 1п1 ~ ~о (х) +,~~ХгДг(х) — а,)+ (т)'"гЛх — Ъ) хЯА~ г 1 Хнз К+, яФ (~ г)з) < Теорема сразу вытекает из сказанного в предыдушем пункте, а также лемм 1 и 2.
~> 4.3. Линейное программирование. Важным классом выпуклых задач являются задачи линейного программированиц в которых ишутся экстремумы линейных функционалов при ограничениях типа равенств и неравенств, задаваемых также линейными функционалами: <с, х>- зцр(1п1); Ах ='Ъ (Ах-"Ы, х~О, (з) 73 < По определению, яа (Х, т~") = зцр 1'(Х, а) -~- (т)*, т)) — Ы Р (х; а, т))) = (а,гз '1 х вм зцр (<Х,а) + <т)*, т)) — Е(х1а, т))) га гг,х) — зцр (<Х, а) + (1)*, т)) — )ь(х)) = аг<аг 1а(хг ххА,Ах+гг=Ь гп зцр — (, (х) — 2~1,(уг(х) — а,) — (т~~гЛх — Ъ), Х нз К:, хгзА 1 + Оо, ХФн+, что и требовалось. ~> Ч аким образом, в соответствии с общим правилом и.
4.2,1 получаем двойственную задачу гр(Х, т)*) =1ц1;с(х, т)*, 1, Х)- зцр, Х>0, т)*~ Уа, хгЗА где Х (Х„..., Х ), .У (х, т)*, 1, Х) = ~,(х) + ~ Р~,(5,(х)— г — а,) + <т)*, Лх — Ъ >. Теорема дв о йс твенности. Если Яфункция семейства (з(а, т))) непрерывна в точке (О, 0), то для ЛЮбЫХ (а, т)) Я1М(г1ОП15) я (а, т)) = зар ((Х, а) + (т)а, т)) + гр (Х, т~")). к~о,ггэяг* где хеэ В", сей", Ье-=Й'", А — матрица со столбцами а', ..., а", а'~В", неравенства понимаются как координатные.
Теория задач типа (з) разработана детально и глубоко. О теоремах существования и двойственности для (з) см. АТФ, с. 269 — 275. Основным методом решения задач линейного программирования является симплекс-метод. Теория линейного программирования изложена в книгах 16, 7, 11, 14) и др. В задачнике 112) имеется большое количество задач по линейному программированию. 4.4. Выпуклый анализ и теория экстремальных задач. 4.41. Необходимые условия первого порядка в задаче с неравенствами. Рассмотрим задачу Дх) - 1пг; ~,(х) а:О, 1 1, ..., тп, Г(х) =О, (з) где ~л, Я-В, 1 0,1,..., т, Г:%- У; 'У~С(Х), Х и У вЂ” нормированные пространства. Функция Лагранжа этой задачи имеет вид; 2' (х, Х) = ~ я,~; (х) + (у~, Г (х)), Х = (а, у*) еи В~ ~' Х У*, МО Т е о р е и а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
