Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 62
Текст из файла (страница 62)
Упражнения. 1. Сформулировать аналоги теорем Куна — Таккера для задача максимизации: у(и) -с зар (а сн И), где множество И определено посредством (2). Указание: рассмотреть задачу: 1(и) = — у(а)- ш1 (аж П) я воспользоваться теоремамн 2, 4, о. 2. С помощью теорем Куна — Таккера исследовать аадачу: 1(а) = = ~~ ~ид — а,.(-+!П1 (Кж()),тдЕ (д=(ижЕа: (и((Ц НЛН (Г=(иСНЕад д=д в'+... + я" = О), нлп П = Еа; аь ..., а„— заданные числа.
3. Прнменддть теорему Куна — Таккера к задаче квадратичного проградинроваяня: 1(и) = (и')г+ ... + я(в")г-~ш1 (аж 0), где Гд= =(ишЕа: в'+...+и"=Ц, клк ад=(вднЕ": в'+...+а" (Ц, нля И = (и ш Е": — 1 С а'+ ... + и" ( Ц, нлн П является пересечением предыдущих множеств с Е™„. 4. Решить аадачп геометрнческого программкрованяя: ад -аг а) У(х)=сх +сх -~-ш1 пря х>0, где сд>0, ад>0 — заданные чясла; у) =х У+2ху+за 1У г-~ш1 пря х>0, у>0.
) У(х У г) = 4х 'У 'г '+ ху+4хг+ 2уг-д.ш1 пря х > О у > О г>0; г) у(х,у)=у-ддв(прях>О,У>О,хду д+х 1упг .-1. У э) ТЕОРЕМА КУНА — ТАНКЕРА, ДВОЙСТВЕННАЯ ЗАДАЧА 259 д) у(х, у, з)=х+у 'е»»а-е(п( при х>0, у>0, з>0, х 'у+ +х — '»<1. 5. Выяснить, существуют ли седловые точки функции Лагранжа в задачах из примеров и упражнений к 4 2.2, к гл. 3, к з 4.8; найти эти точки. 1 6.
Доказать, что выпуилая квадратичная функция Х(и) = 2 (Си и) + +<а, и> либо достигает своей нижней грани на Е, либо не ограничена спнзу. 7. Сформулировать и доказать аналог леммы 2 с использованием субградиента. Сформулировать субдифференциальные аналоги теорем 2, 4, 5. 8. Пусть в задачах (43), (44) ПФ Е», Л Ф 8. Доказать, что тогда в этих задачах существуют такие решения й»н Ь»е, Ле»е Л", что в правых частях равенств р," (Аи — Ь)» = 0 (» = 1, ..., т), и» (а+ Атр*+ Ат 1»а)» = = 0 (» = 1, ..., е) (см. теорему 8) один из сомножителей отличен от нуля.
9. Пусть Па — выпуклое множество из Е", функции у»(и), ..., у,„(и) выпуклы на Пь у»(и) =<а», и> — Ь» (» = т + 1, ., е). Доказать, что если система неравенств у»(и) < 0 (» = 1, ..., т), у»(и) = 0 (» = т -Ь 1, ..., в) не имеет решения на бм то существуют числа Л» > О, ..., Л > О, Л».ь... Ла токио, что Л»у» (и) + ... + Л»у» (и) ~> 0 при всех и се Ь»а. У к а з а н и е: построить множества, аналогичные множествам А и В из доказательства теоремы 2, и применить к ним теорему отделимости 5.2. 10.
Пользуясь теоремой 3 (Фаркаша), докааать, что для несовместности системы линейных неравенств <е», и> < )»» (» = О, 1, ..., т) необходимо и достаточно, чтобы существовали такие числа Ла>0, Л, >О, ... ..., Л, >О, что Лаеа+Л,е,+...+Л е,„=О, Лара+Л»р»+...+Л„,р, <О (ср. с теоремами 5.9, 5АО) [321).
11. Доказать, что два непустых многогранных множества А = (и ш Е»ч <е», и><»»», »=О, 1, ..., Ь) п В=(ишЕ» <е», и)<)»», »=)»+1, ..., т), не имеющие общих точек, сильно отделимы. А Указание: рассмотреть гиперплоскость (с, и)=Т, где а =,~, Л»е», »=е е 7 = ~' Л»)»», числа Ла, . ° ., Л взяты нз упражнения 10. »=а 12. Доказать, что если система линейных неравенств (еа, и) < О, (е», и) =- О, ..., (е, и) < 0 несовместна, то существуют такие числа Л» > О,..., Л > О, что еа = — ).»е, — ... — Лхеае У к а з а н и е: воспользоваться теоремой 3 (»Раркаша). 13. Пусть система <еа, и> < ра, <е», и><)»» (» = 1, ..., т) несовместна, а подсистема <е», и> < )»» (» = 1, ..., т) совместна.
Доказать, что тогда существуют числа Л» > О, ..., Л,т 0 такие, что еа = — Л»е» вЂ” ... — Л е, р,+ Л,и, + ... + Л 1 <О [21). Указание: в пространстве переменных (и, »)»ЕЕ +» рассмотреть систему (еа, и) — »р, < О, (е», и) — »)»» < 0 (» =1, ..., т), (О, и) — » < 0 и воспользоваться утверждением из упражнения 12. Глава 5 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Выше в гл.
3 был рассмотрен симплекс-метод для решения задач линейного программпрования. Перейдем к изложению других методов минимизации функций конечного числа переменных, не предполагая линейности рассматриваемых задач. В настоящему времени разработано и исследовано большое число методов минимизации функций многих переменных. й!ы ниже остановимся лишь на некоторых наиболее известных и часто используемых на практике методах минимизации.
Будет дано краткое описание каждого из рассматриваемых методов, исследованы вопросы сходнмости, обсуждены некоторые вычислительные аспекты этих методов. При этом мы ограничимся рассмотрением лишь одного — двух основных вариантов иэчагаемых методов, чтобы ознакомить читателя с основами атих методов, полагая, что знание основ методов облегчит читателю изучение литературы, позволит ему беэ особого труда понять суть того нли иного метода и выбрать подходящий вариант метода или самому рааработать более удобные его модификации, лучше приспособленные для решения интересующего читателя класса аадач. В конце главы будут высказаны некоторые общие замечания по методам минимизации.
Иэ обширной литературы, посвященной методам минимизации функций конечного числа переменных и их приложениям, мы можем здесь упомянуть лишь весьма незначительную ее часть [3, 4, 7, 8, 10 — 13, 15, 16, 19 — 23, 25 — 27, 29, 30, 35, 38, 40 — 42, 44, 46 — 49, 52 — 58, 71, 72, 76. 78, 79, 81 — 89, 94, 96, 103, 106, 107, 109 †1, 115, 116, 119, 122, 123, 126, 127, 129 †1, 139 †1, 143 †1, 162, 163, 165 †1, 173, 174, 176 †1, 180, 183, 190, 191, 194, 196, 198, 200 — 203, 207 †2, 213 †2, 221, 224, 225, 227 †2, 234, 235, 237, 238, 240 †2, 245, 247, 248, 250, 254 †2, 261, 262, 265 †2, 269 †2, 274, 276 †2, 282, 284, 287, 288, 291 †2, 296 †2, 301, 302, 306, 307, 313, 314, 316, 318, 320 †3, 329 †3, 343).
й 1. Градиентный метод 1. Будем рассматривать задачу з(и)- 1п1; иш с!в = Е", (1) предполагая, что функция у(и) непрерывно днфференцнруема на Е", т. е. з(и)шС'(Е"). Согласно определению 2.2.1 дпфференцнруемой функции э'(и+ Ь) — з'(и)= <У'(и), Ь>+о(Ь; и), (2) гглднентнтяи метОд 261 3 О где Иш о(Ь; и)(Ь( ' =О. Если 1'(и)чьО, то при достаточно ма1м- о лых !Ь! главная часть приращения (2) будет определяться дифференциалом функции Ы(и)= <1'(и), Ь>.
Справедливо неравенство Коши — Буняковского — У'(и)! (Ь! ( <1'(и), Ь> ( (1'(и) ( (Ь(, причем если 1'(и)чьО, то правое неравенство превращается в равенство только при Ь=а1'(и), а левое неравенство — только при 1' (и) чь О, где а = сопз1 ) О. Отсюда ясно, что при 1' (и) чь 0 направление наибыстрейшего возрастания функции 1(и) в точке и совпадает с направлением градиента 1'(и), а направление наибыстрейшего убывания — с направлением антиградиента ( — 1'(и) ).
Это замечательное свойство градиента лежит в основе ряда итерационных методов минимизации функций. Одним из таких методов является градиентный метод, к описанию которого мы переходим. Этот метод, как и все итерационные методы, предполагает выбор начального приближения — некоторой точки и,. Общих правил выбора точки и, в градиентном методе, как, впрочем, и в других методах, к сожалению, нет. В тех случаях, когда из геометрических, физических или каких-либо других соображений может быть получена априорная информация об области расположения точки (или точек) минимума, то начальное приближение и, стараются выбрать поближе к этой области.
Будем считать, что некоторая начальная точка и, уже выбрана. Тогда градиентный метод заключается в построении последовательности (и,) по правилу и,э,=и„— а„1'(и,), а„)0, Ь=О, 1, ... (3) Число а„из (3) часто называют длиной шага или просто шагом градиентного метода. Если 1'(ил)чьО, то шаг а,) 0 можно выбрать так, чтобы 1(и,+,)(1(и„). В самом деле, из равенства (2) имеем 1 (ил+ з) — 1 (ил) = ал ~ — ( Г (ил) (' + о (ал) а„'] ( 0 при всех достаточно малых а,) О. Если 1'(и„)=0, то и„— стационарная точка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
