Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 31
Текст из файла (страница 31)
Пользуясь теоремами вложения из книги [204] показать, что шаР [и(з): , 'и (з); м„,<)г <со~ из Им~х (6) компактен в метРнке Тггл+г Н'" (6) при всех яг)0 (обозначения см. а 4 !.!). Опираясь на этот факт, предложить стабилизатор для задачи минимизации функций на множествах (г иэ Нм (6) в метрике Н™ (6). [73 6. Доказать. что если Яг(и) и 1)а(и) — р-стабилизаторы !слабые стабилизаторы) с одной и той же областью определения г/а, то ь) (и)ь игьгг(и)+ааг)з(и), ест~в, иг —.-.О, аз+из) О также является р-стабилизатором [слабым стабилизатором!.
$ 3. Нормальное решение Остановимся еще на одном аспекте задач минимизации. В тех случаях, когда множество [/ точек минимума функции /(и) на (/ состоит более чем из одной точки, можно поставить задачу об отыскании наилучшей в некотором смысле точки этого множества. Например, может возникнуть задача об определении точки и, е- :[/„ближайшей к некоторой фиксированной точке й в некоторой метрике р„т. е, р,(и„й) = гп1р,(и, и). ггыи„ В более общем виде подобную задачу можно сформулировать так: на множестве !/о ы [/ задана функция Р(и), причем [/й = [/о П(/„~ ([) и требуется найти такую точку и еи (/а, в которой [) (и) достигает своей нижней грани на (/а. Определение 1, Точку и„е=(/„, назовем нормальным решением задачи (1.1) гга функции [з (и) или, короче, ьа-норлгальным решением задачи (1.1), если [п1 Й(и) = И (и,). ио В задачах оптимального планирования функция [г(и) может выражать собой стоимость затрат на организационные и технологические перестройки при переходе от существующего состояния производства к его новому состоянию, соответствующему плану и.
Тогда среди всех оптимальных планов и еи [/„естественно выбрать тот план иа, для которого стоимость затрат Р(и„) минимальна. Таким образом, в данном случае наилучший оптимальный план представляет собой !1-нормальное решение задачи (1.!) !10, 171. Следует подчеркнуть, что задача определения ь)-нормального решения 2 (и) -~ [п1; и ~ [/а, (1) весьма осложняется тем, что множество (/а задано неявно, и оно лишь в редких случаях может быть точно и конструктивно описано. 1(ак было замечено выше, задача описания множества [/а особенно сложна в том случае„ 174 когда исходная задача (1.1) некорректна в требуемой метрике.
Рассмотрим еще один аспект задачи (1), связанный с явлением неустойчивости множеста Уй при неточном задании функции. А именно, пусть вместо точного значения функции ((и) известны лишь его приближения (ь (и), й= 1, 2, ..., и пусть !пп (У(и) — У„(и)) =0 при каждом а со и ~ (/. Тогда для отыскания 11-нормального решения задачи (1.1) можно попытаться нанти множества У$ = =(ш пей У, /ь(и)=(п1/„(п)=/Д и точки и„е-=(/3 из и условия Р(иэ)оо(п111(и), Ь=1, 2, ..., а затем в каче- и," стае приближения к 11-нормальному решению взять точку ил с достаточно большим номером й. При этом неизбежно возникнет вопрос: будет ли последовательность (и„) сходиться ко множеству 11-нормальных решений в требуемой метрике? Оказывается, ответ на этот вопрос в общем случае отрицательный, поскольку предыдущие действия могут привести к большим погрешностям в определении ь)-нормального решения.
Поясним это на простых примерах. П р и м е р 1. Пусть требуется минимизировать функцию У(и) =!аи — Ь!' иа множестве У= Е' прн условии, что величины а и Ь заданы с погрешностями. Пусть точные значения а = Ь = О, так что У (и) = Π— = /„= !п! з' (и), Я\ (7„= Е'. Если 12 (и) = и', то ()-нормальным решением этой задачи является единственная точка ио =О. Предположим, что величины а, Ь известны лишь приближенно и прн вычислениях с некоторым числом десятичных знаков задаются как а„, Ьы так что вместо точной функции / (и) мы будем иметь дело с ее приближениями /с,(и) = !а„и — Ь„!', й=1, 2, ... Пусть 1пп алоо 1(тЬь=О, т.
е. точные знаСс со Сс со чения а=Ь=О могут быть получены с любой наперед заданной точностью. Так как а„, Ьм вообще говоря, отличны от нуля, то множество У~ точек минимума /,(и) на У состоит из единственной точки иь=Ьэ)а„, й=!, 2,... Нетрудно видеть, что величина иы являющаяся отношением малых чисел, может принимать любые значения.
Следовательно, как бы точно ни задавались величины аы Ьм безнадежно пытаться использовать и„ в качестве приближения к 12-нормальному решению и =0 в метрике Е'. 175 Этот пример показывает, что и в более общей задаче линейной алгебры Аи = Ь, сводящейся к минимизации функции / (и) = ! Аи — Ь ", при поиске»1-нормального решения с»»(и) =! и!' могут наблюдаться аналогичные явления н екорректности из-за погрешностей в задании матрицы А и вектора Ь [17!.
П р и м е р 2. Пусть требуется найти»1-нормальное решение задачи минимизации функции з'(и) г х+у на множестве У = (и = (х, у): х ) О, у ) О, 2-= х+ у ( 3) при »1 (и) = ! и = х'+ у'. Очевидно, (п1((и)=з',=2, У =(и=(х, у): х+у= =- 2, х)0, у)0). Так как функция У(и) непрерывна и множество У компактно, то задача минимизации l(и) на (/ корректно поставлена в метрике Е'. Точка и„=(1, !) является единственным Й-нормальным решением этой задачи, причем Р (и„) = 2. Предположим, что функция У (и) задана неточно и нам известны лишь ее приближения /»(и) =а„х+Ь,у, где !ппа»= 1пп Ь„=1.
Так как, вообще говоря, а» ч~ Ь», то минимум )»(и) на У будет достигаться либо в точке и»=(2, 0) (при а»(Ь,), либо в точке и, = = (О, 2) (при а») Ь»), т. е. множество У» точек минимума при а»~Ь» состоит из единственной точки и». Ясно, что последовательность (и») не сходится к 11-нормальному решению и» = (О, 0), и кроме того, Р (и») = 4, у = 1, 2,..., так что !!гп»1(и») =4 Ф»1(и») =2.
Таким образом, как »-~ бы мы ни уменьшали погрешность задания величин а, Ь, попытки использовать (и») в качестве приближения к и„=(0, 0) обречены на неудачу. Приведенные примеры показывают, что при. сколь угодно малых погрешностях в задании функции l(и) множества Щ = (и: и е- =У, /» (и) =)п! У» (а)) могут отлии чаться от (l„ столь значительно, что использование точек иы определяемых условием Р (и„) = !п!»1 (и), в качестве а»' приближения к Р-нормальному решению может привести к большим погрешностям. Это означает, что задача определения Й-нормальных решений относится к классу некорректно поставленных задач, и для ее решения требуются специальные методы. Оказывается, методы регулярнзации, которые будут изложены в последующих параграфах, позволяют решать и такую задачу, !76 В заключение остановимся на условиях, гарантирующих существование й-нормального решения задачи (1.1). Теорема 1.
Пусть функция й(и) являегпся р-стабилизатором задачи (1.1) и пусть функции /(и), Р (и) ргголунепрерывны снизу на множестве (/а. Тогда существует хотя бы одно й-нормальное решение задачи (1.1). Доказательство. По определению стабилизатора множество (/а = (/а () (/в непусто. Возьмем какую-либо точку ов я(/а и составим множество йс=(и: и я(/*„, й(и)(С), где С=й(о„). Очевидно, йсче ~д, так как, например, о, ен йс. Покажем, что Рс р-компактно. С этой целью возьмем любую последовательность (и„) ~ Рс. Так как йс = йс, то 1иь) ен йс.
Но множество йс р-компактно по определению р-стабилизатора, поэтому ич (и„) можно выбрать подпоследовательность (иь,), р-сходящуюся к некоторой точке о ен йс. Покажем, что о ен Рс. Включение ива Рс означает, что и, ~(/а, т. е. /(иь)=/„, Й=!, 2, . С учетом р-полунепрерывности снизу /(и) на (/а отсюда при /а=я„- оо имеем lв (/(о) (1!ш /(иа„) =- =* /в, т. е. / (о) = /в. Таким образом, о ен (/„. В то же время включение о я Рс означает, что о я(/а и Р(о) = ( С.
Следовательно, о ~ йс. Тем самым р-компактность Рс доказана. Так как функция й(и) р-полунепрерывна снизу на йс, то из теоремы 1.3.1 тогда следует, что й (и) достигает своей нижней грани на йс хотя бы в одной точке и„~ ~ Рс. Однако, очевидно, й„=!п1 й (и) = !п1 й (и) = й (и„), са а~ т. е. и„является й-нормальным решением задачи (1.1).
Аналогичная теорема может быть сформулирована с использованием слабого стабилизатора задачи (1.1). Теорема 2. Пусть в задаче (1.1) множество (/ принадлежит банахову пространству В и функция й(и) является слабым стабилизатором этой задачи. Пусть, кроме того, функиии /(и), й (и) слабо полунгпрерывны снизу на (/а. Тогда существует хотя бы одно й-нормальное решение задачи (1.1).
Доказательство опирается на теорему 1.3.2 и проводится так же, как теорема 1. У и р а ж н е н и я. 1. Дайте геометрическую иллюстрацию задач из примеров 1, 2. 2. Пусть требуегся минимизировать функцию / (и)-=(от+ Ьу+с)а на плоскости Е', пусть коэффициенты а, Ь, с известны неточно, Будет 177 ли корректна в метрике Еа задача нахождения й-нормального решения, если взять й (и) =х'+уа? 3, Найти й-нормальное решение и, задачи минимизации функции / (и)=(х — 1]'+(О у — 1)а при и=(х, у) ш У= Е', считая, что й (и) =х'+ у-". Показать, что!и» вЂ” и, 1-» оп при Ь вЂ” »со, где и» представляет собой й-нормальное рещение задачи минимизации приближенной функции .1» (и) = , 'х — 1,»-(-( п»у — 1 (а на Е', где и» вЂ” > 0 прн Ь вЂ” ~ со.
4. Найти й-нормальное решение следующей задачи линейного программирования: минимизировать функцию У (и) = — с,х+с,у на мно. жестве (? =(и=(х, у): омх+и„у=Ь„омх+и„у=Ьм х = О, у - О), где векгор с=(с,, с») и матрица А= (аи) известны неточно, а й (и) = = х'+у'. Будет ли задача нахождения й-нормального решения корректной в метрике Ех? 5. Найти й-нормальное решение задачи минимизации фуниции У(и)=х'(1, и) при условиях »=и(1), 0 =1(1, х(0)=0, и(1) ~з ! ш Е» [О, 1), ( и (О ! = 1 почти всюду нз (О, 1(, если й (и)=~ иа(?) Ш. о Будет ли задача определения й-иормалшшго решения корректной в метрике С[0, 1(? Еа(0, 1)? $ 4. Основные леммы о регуляризации В методах регулярпзации, которые будут описаны ниже, важную роль играют следующие две леммы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
