Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 32
Текст из файла (страница 32)
Поясним это на простых примерах. П р и м е р 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. Основные леммы о регуляризации В методах регулярпзации, которые будут описаны ниже, важную роль играют следующие две леммы. Для формулировки этих лемм нам понадобится понятие р-регулярной последовательности.
О п р е де л е н и е 1. Минимизирующая последовательность ',и,', задачи (1.1) называется регулярной в метрике р или, короче, р-регулярно!1, если: 1) последовательность (и„) р-компактна, т. е. из нее можно выбрать хотя бы одну подпоследовательность, р-сходящуюся к некоторой точке из (/; 2) (и») сходится ко множеству (/, в метрике р. Л е м м а 1. Пусть 1) (/ — множес?пво с заданной на нел! метрикой р; функция /(и) определена и р-полунепрерьтвна снизу на (/, /„=1п1/(и) ) — со, многкество гl (/, = (и е= (/: / (и) = /„) непусто; 2) функция й(и) определена на мнозкеслше (/: — (/ и является р-гтабилизап?ором задачи минимизации У (и) на (/; 3) последовательность !и») такова, щпо и» е= (/а, /(и„) «=.,/„+()», /с= 1, 2, ..., (1) й(и»)(й,+у», я=!, 2 (2) где й = (п( й (и), ()» ) О, й = 1, 2, ..., !'пп ()» = О, оа » сч нир, у»; (+ ° ..
»-~ 173 Тогда последовательность (и») минимизирует функцию /(и) на (/, р-регулярна и !пп р(и», (/а) =О, (/а=(/а П(/,. (3) » со Если, кроме того, й(и) р-полунгпрерывна снизу на (/а и 1! гп у» = О, то 1!п1 й(и„)=й„, 11гп р(и„, (/о,)=-0, (4) » со » со где (/оооо(и: и ~(/а, й(и) = й„) — множество й-нормальных решений. Доказательство, С учетом того, что У(и»)зь/о из неравенства (1) сразу получаем !пп l(и») =/о, т. е. (и,) — минимизирующая последовательность. Далее, из (2) следует, что й(и») «й, +зцр !у»' ,=С<со, у=1, 2, ..., »~! т.
е. (и»,' я йс= (и: и я(/а, й(и) «С). По определению р-стабилизатора множество йс р-компактно. Поэтому последовательность (и,) р-компактна. Пусть о„— произвольная точка, являющаяся р-пределом какой-либо подпоследовательности (и„„',. Покажем, что оо еп(/й. Пользуясь тем, что /(и) р-полунепрерывна снизу и о„е- =йс ~ =(/, из неравенства (1) прн й=н„- оо получим /„« к.=. / (о») «! пп / (и»о) « l,. Это значит, что,/ (о„) = У», т. е. о с о,„~ !/„. В то же время о, в== йс с йп. Следовательно, о. г=(/а=(/и П(/,. Тем самым доказано, что любая точна, являющаяся р-пределом какой-либо подпоследовательностн 1си»1 принадлежит (/от. Отсюда уже нетрудно получить соотношение (3). В самом деле, из пеотрицательности расстояния следует 1пп р (и», (/ас) --: О.
Пусть ! пп р(и», (/1с) =11гп р (и», (/по). ». со » со о со В силу р-компактности множества йс и включения (и»„! еи йс можем считать, что (и„) р-сходится к некоторой точке о . Тогда нз р-непрерывности функции р(и, (/3) (см. 4 1,3) имеем )пп р(и», 1/а) =р(о„(/(с). Но по о со доказанному оо вп Уа, так что ! пп р (ию (/а) = р (о„ » со (/сс) =О. Это значит, что !пп р(ию (/а) существует и равен нулю. Тем самым, р-регулярность (и») н равенство (3) доказаны. 179 Пусть теперь !пп у,=О и функция й(и) р-полунепрерывна снизу на уа. Заметим, что тогда множество сг, » непусто †э следует из теоремы 3.1. Покажем справедливость соотношений (4).
Пользуясь тем, что о, ~ Уа, из неравенства (2) при и = я„-+.;. получим й,„ ( й (о„) ( ( 11п1 Й (ил ) = 1пп й (и, ) ( й„ + 11ш уь = й„. Зто знасо А о» чит, что !! п1 й (и, ) = й (о„) = й„, т. е. о„~ У„„. Таким с о» образом, любая точка, являющаяся р-пределом какой-либо подпоследовательности (иь), принадлежиг множеству У„„. Рассуждая так же, как при доказательстве равенства (3), отсюда имеем !пп р(и„У„») =О. Наконец, покажем, что 1пп й(и,) = й,, Из (2) следует Ь со !(гп й (и,) ( йо. Пусть !пп й (и,) = 1)ш й (ил„), В силу Ь со ь: 'с о» р-компактности Йс и включения (ило) ~ йс можем считать, что (и„,' р-сходится к некоторой точке о„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
