Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 91
Текст из файла (страница 91)
Если же укаванные исходные данные известны лишь приближенно, то метод штрафных функций попевка регуляриаовать [6, 22, 84, 86, 87, 177, 329, 343]. Рааличные прикладные и теоретические аспекты метода штрафных функций исследованы в [6, 8, И, 12, 19, 21, 109, 1И, 122, 129, 144, 148, 159, 173, 174, 177, 240, 306, 307, 314, 330, 338]. Уп р аж н ей ия. 1. Применить метод штрафных функций к аадачам а) 1(и) ха+ у'-+ш1; и ш У = (и = (х, у) шЕт: у(и) = — х — у+ +1(0) или игыУ=(и=(х, у) евЕт: у(и) =,— х — у+1 0); б) 1(и) =ау-~ш(; иш У= (и=(х, у) епЕ'.
х'+уа<25) или иав ш У = (и = (т у) ш Ег. хэ + ут = 25] в) 1(и) = х'+ у'+ а'-~ ш1; и еи У = (и = (х, у, х) ш Е', х + у + х + + 1(0). 2. Применить метод штрафных функций к аадачам иэ примеров 2.2.2 и 2.2.4. 384 МЕГОДЫ МИНИМИЗАЦИИ тВРНКПИИ МНОГИХ ПЕРЕМЕННЫХ (ГЛ. б 3, Пусть У(и) = р '", а множество (У = (и ш Е': 0 < и < 1) задано либо ограничениями Ет(и) = — и < О. дт(и) = и — 1 < О, либо Е(и) = )и! + + (и — 1) — 1=0, либо Е(и) е "()и(+ )и — 1! — 1) О.
Выяснить, в каких случаях задача У(и) -»)в1, итм (У, имеет согласованную или сильно согласованную постановку на Е'. 4. Пусть (Рр(и)) — штрафная функция некоторого множества (У. Пусть функция р(с) определена при с ) О, чт(0) = О, причем ф(с] -»О при с-»0, П)-т-ар при с- оо. Покааать, что тогда (ф(рр(и))) является штрафной ункцией множества (У. 5. Применить метод (3), (6), (8) к задаче У(и) = ис — и-»ш( и и ря ев (У = (и ш Е'т д(и) = и < 0), взяв в качестве штрафной функции Р(и) = (шах(0; и))с.
Получить точную оценку погрешности, сравнить ее с оценками из теоремы 5. 6. Пусть множество (У задано либо ограничениязш Ю(и) = и — 1(0, Ю(и) = — и — 1 (О, либо Е(и) = е " (из — 1) ~(0, либо Е(и) = иэ — 1 <О. Выяснить, какие из этих ограничений являются корректными на Е' нли Пр — — (и тв Е'т — 1 < и < 1). 7. пусть УУ = (игле": х(и) <0), где а(и) — непрерывная функция на Е". Докааать, что для того, чтобы множество П было ограниченным и ограничение д(и) < 0 было корректным на Е", необходимо и достаточно, чтобы ьшожество (Ур = (и тв Есч Е(и) < б) было ограниченным хотя бы при одном 6 ) О.
8. Пусть (Ур — выпуклое замкнутое множество из Е", функция Е(и) выпукла н полунепрерывна снизу на Пь и пусть множество М(С) = (ива рм Срт Е(и) < С) непусто и ограничено при некотором С. Доказать, что тогда ограничение Е(и) < 0 корректно на (Ур (см. теорему 4.2.17). 9. Рассмотреть задачу: У(и) =и-+(п(, итя тУ=(ишЕт: Е(и) и'+ + е(и) < 0), е ~ О. Доказать, что здесь выполняется неравенство (36) с М = 1/э, 7 = 1. Пользуясь леммой 5 и теоремой 9, установить существование седловой точки Лагранжа.
Выполняются ли адесь условия теорем 4.9.2, 4.9.57 10. Применить метод штрафных функций к аадаче (42), получив оценки скорости сходимости метода и сравнить их с оценками из теорем 5, 6. 11. Применить метод штрафных функций к задаче: У(и) = хс+ + (1 — ху) р -»сп(, и ш (У = (и = (х, р) тм Ет а(и) = х — а = 0), исследовать его сходимость при различных значениях параметра а. 12. Доказать, что множество С = (и ее Е": гт(и) = <ат, и) — Ь' = О, С = 1, ..., р), где ат, ..., а,— линейно неаависимые векторы из Е", Ь' ел В, является корректным на Е" и неравенство (36) выполняется с 7 = 1, М = = рбАг(АА ) Ч, А — матрица размера г)С и, строками которой являются векторы а„..., а,. Указание: воспользоваться результатами примера 4.4.3.
13. Пусть задача (44) удовлетворяет условиям теоремы 4.9,2, причем и(Е(У». Доказать, что тогда (С»=(иш(сэ: Ф(и) =Ф»ф где Ф(и) =)п + )' шах О, — ', Ф» (в( Ф(и). 1 Ес (и)) У (и) — У (и) ~ Ес (и)~ Пр $ сб. Метод блрьерных функций з. Идеи метода штрафных функций могут быть использонлиы для построения методов решения задачи У(и)- ш(; итя(У, (4) позволяющих получить такую минимизирующую последовательность (и„)см (У, каждый член которой будет лежать вне некото- метод БАРьеРных ФунКПИИ рого заданного «запрещенного» подмножества (<= П.
В качестве «запрещенного» мнол«ества т может служить, например, граница Гр У множества П нли какая-либо часть гранины. Дело в том, что прп применении того или иного метода решения задачи (1) прн Пт«Е" может случиться, что каждое получаемое приближение и, будет принадлежать Гр П. Однако если структура грани цы множества слишком сложна, то реализация такого метода может потребовать большого объема вычислительной работы и, кроме того, сходимость метода может оказаться очень медленной. В таких случаях можно попробовать как-то построить «барьер» вблпзи всей границы (= Гр П нли какой-либо ее части ц (или какого-либо другого заданного подмножества (~ П), который исключал бы возможность попадания очередного приближения и, на т.
Определение 1. Пусть ц — некоторое подмножество множества К Функцию В(и) пазовом барьером или барьерной функцией подмножества т, если В(и) определена, конечна и неотрицательна во всех точках и«= П'1"(, причем НшВ(Р„) = со для всех последовательностей (и,) «в й(, которые сходятся к какой-либо точке и1и'(. Заметим, что в определении 1 подразумевается, что Ю(ть Ф О. Это значит, что если ( = Гр П, то ш$ П = «1'1"( т'= »».
Заметим также, что в точках и1н "( барьерная функция В(и) не определена (можно принять В(и) =, и 1л 1). Пользуясь теми же конструкциями, которые использовались при построении штрафных функций, нетрудно выписать барьерные функции для множеств (, задаваемых ограничениями типа равенств илн неравенств. Например, если (=(и~нЕ": ишь, д(и)=0), где д(и) непрерывна на П, Ю"(т-о, то в качестве барьерной функции здесь можно взять В(и) = ~д(и) ~ ', или В(»»)=!д(и)! ', или В(и)=шах( — 1п~у(и)1; О).
Кслп же '(= (и ~ Е: и ш П, д(и) < О), где П'1 ( Ф 6, у (и) непрерывна на П, то можно принять В(и) =(д(и) )-» (р ) О), или В(и) = ()па(и) $, и «а Ы1 и т. п. Перейдем к описанию метода барьерных функций для решения задачи (1), предполагая, что подмножество ('— = П и некоторая его барьерная функция уже заданы. Введем функции Г»(и)=»'(и)+ а,В(и), и н П~'(, й.= 1, 2, ..., (2) где (а») — положительная последовательность, сходящаяся к нулю. Величины (а,) из (2) называются барьерными коэффициентами. Расс»1отрим последовательность задач Р„(и)- ш1; иш П1(, й= 1, 2, ...
(З) Обозначим РА* — †!Б1 ЕА(и) ()« = 1, 2, ...). Будем предполагать, и'7 386 метОды минимизации Функции многих пнгемвнных ~гл. ь что в исходной задаче (1) Ув = 1п11(и)) — сс. Так как Р„(и)=- >т(и) при всех ия Р'(, то Рд«)~Х«) — оо. Тогда условия и»аУ',у, Рд(ид)(Р», + ед, Й= 1, 2,...
(4) определяют последовательность (и,), где ед) О, 1пп ед — — 0; если д окажется, что Рд(ид) = Рд„то в (4) допускается е»=0. Поскольку, как обычно, мы подразумеваем, что функция У(и) конечна во всех точках и ~ У, то согласно определению 1 для любой последовательности (и„)ж Р"(, (о,) — о ~в ( справедливо равенство 11ш Рд (о„) = сс при кан«дом фиксированном Й = = 1, 2, ... Таким образом, функция Р„(и) неограниченно возрастает вблизи у. Поэтому следует ожидать, что при фиксированном Й функция Р„(и) вблизи у не может принимать значения, близкие к Рдд и точка ид, определяемая условиями (4), не будет расположена на слишком близком расстоянии от (.
В то же время благодаря тому, что барьерные коэффициенты (а„) — О, не исключается возможность того, что с увеличением номера Й точки и„постепенно «преодолевая барьер», будут приближаться к (. Для приближенного решения задачи (3) при фиксированном Й и определения точки и„удовлетворяющей условиям (4), могут быть использованы различные методы минимизации. В частности, если у =Грей и У~"(= 1п(б'чьЗ, то для решения задачи (3) может быть применен, например, градиентный метод (см. е 1): Р ид, гд — — ид„— а„рд (ид,), ид« = — ид г=0,1, Поскольку ид, ~ шт У, то при достаточно малых а, > 0 и точка ид„т, также будет принадлежать 1пт У, и мы избавлены от неудобств, связанных с учетом границы У,— нужно лишь на каждой итерации следить за соблюдением включения ид ж (пт У, а при его нарушении уменыпать длину шага а„.
Правда, для этого величину а„, быть может, придется брать слишком малой, и сходимость градиентного метода, взамен~но, замедлится, но это уже будет «платой» за выполнение условия и»ы (пт У. Дальнейшее изложение не зависит от того, с помощью какого конкретного метода минимизации будет найдена точка и„ удовлетворяющая условиям (4). Поэтому мы здесь можем ограничиться предположением, что имеется достаточно удобный метод определения точки и, из (4). Метод барьерных функций описан. Отметим, что в литературе этот метод иногда называют методом внутренних штрафов (или методом внутренней точки), а метод штрафных функций из $14 — методом внешних штрафов (или методом внешней метод ВАРьеРных Функций 387 е 151 точки) [307).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
