Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 55
Текст из файла (страница 55)
Поскольку это множество выпукло и замкнуто, то неравенство (1) сохраняет силу и здесь. Аффинное множество обладает следующим замечательным свойством; если е, и еХ, и ~ и, то и 2е,— е Е Х, что проверяется непосредственно. Поэтому еслй здесь взять е = Р (и) = ю е Х, то 2ю — е е Х при любом 185 б 4. НРоекция точки ИА множество 184 Гк 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА (3) ', ч.з! рз (Рх(е) — е,Р (и) — РхЯ) > 0 Сложим эти два неравенства. Имеем Рис. 4.9 Рис.
4.8 (6) выборе е Е Х. Подставим в (1) вместо е точку 2ю — е. Получим (ю — и, 2ю— — е — ю) = (ю — и, ю — е) > 0 при всех е Е Х. Сравнивая полученное неравенство с (1), приходим к равенству (2). П Покажем, что оператор проектирования на выпуклое множество обладает сжимающим свойством. Т е о р е м а 2. Если Х вЂ” выпуклое замкнутое множество из Е", то !Рх(и) Рх(е)! <. !и — е! 'и»е, е Е Е".
Д о к а з а т е л ь с т в о. Из неравенства (1) имеем (Р,(и) — и, Рх(е) — РхМ) ) ~О. Поменяв ролями точки и и е в последнем неравенстве, получим (Рх(и) и Рх(е)+ е Рх(") Рх(и)) > 0 Отсюда следует (Рх(и) — Рх(е)!л < (Рх(и) — Рх(е), и — е) !»и, е Е Е". (4) Применим к правой части (4) неравенство Коши — Буняковского !Рх(и) Рх(")! < !Рх(и) Рх(")! ' !и "! Разделив на !Р (и) — Рх(е)! ~0, получим требуемое неравенство (3).
Если !Рх(и) — Рх(е)! =О, то (3) очевидно. П Теорема 3. Пусть Х вЂ” выпуклое замкнутое множество из Е", пусть 'Р (М) = (и Е Х: Вх Е М, что и ='Р (х)) — множество значений оператора проектирования на множестве М с Е". Если М вЂ” компактное множество, то 'Р (М) также компактно. Д о к а з а т е л ь с т в о.
Возьмем Чх Е М. Так как 1п1 !е — х!' = !Р (х)— исх — х!', то, применяя к сильно выпуклой функции д(е) = !е — х!' неравенство (3.3), полУчим: !е — Рх(х)!л < !Р(е) — !Р(Р,(х)) < !Р(е) = /е — х!з или ! !!-— е — Р (х)! < /е — х! Чх Е М, Че Е Х. Отсюда, фиксируя е Е Х имеем: Р,(х)! < !е/+ !е — х! < 2!е!+ !х! < 2!е/+ зпр !х! Чх е М.
Ограниченность и им множества 'Р (е) доказана. Докажем замкнутость Р (М). Возьмем произвольную последовательность (х„) Е Р (М), (х„) — х. По определению множества Р (М) найдется точка иь Е М, такая, что хл — — 'Р,(и„), »с =1, 2,... Из ограниченности М следует ограниченность (и,). Применяя теорему Больцано — Вейерштрасса, можем считать, что (и„) — е . Так как М замкнуто, то и е М. 11о теореме 2 оператор проектирования непрерывен, поэтому х„=Рх(и,)) — ! х =Рт(иь).
Это значит, что х ЕРх(М), т. е. множество (М) замкнуто. Следовательно, Рх(М) компактное множество. Теорема 3 доказана. П 2. Приведем примеры множеств, проекция на которые может быть выписана явно. Пример !. Пусть Х = Я(ес, Л) =(и Е Е"; !и — и ! <Л~~- — шар радиуса Л > 0 с центром в точке и,. Из геометрических соображении (рис. 4 8) ясно, что проекцией точки и ф Х является точка ю = ил+ Л(и — и,)» !и — ис!. Для строгого доказательства этого факта достаточно проверить выполнение неравенства (1).
Имеем (ю — и, е — ю) = (Л» !и — е ! — 1)((и — и, е — и ) — Л !и — е„!) ~ )О, так как !и — и„! > Л, а (и — ес, е — иь) < !и — ис! !е — ис! < !и — ис!Л в силу неравенства Коши — Буняковского для всех е Е Х. П р и м е р 2. Пусть Х = Г = (и е Е": (с, и) = у) — гиперплоскость; здесь с е Е", с у'= О, » = сопз1. Пользуясь геометрическими соображениями (рис. 4.9), проекцию точки и ф Х на Х будем искать в виде ю = и+ сис. Определяя число !х из условия ю Е Х, имеем ю = и + (» — (с, и))с»'!с!з. Поскольку (ю — и, е — ю) =(-» — (с, и))с/!с!' (с, е — ю) =0 при всех е Е Х, то согласно теореме 1 найденная точка ю представляет собой проекцию точки и наХ.
Пример 3, Пусть Х =(и ЕЕ": (аи, и) = б', г' =1,..., гп» вЂ” аффинное множество; здесь а! е Е", б' = сопз1, 4 = 1,..., гп. Можем считать, что векторы а„..., а линеино независимы и т < и (если гп = и, то Х будет состоять из однойточки). Проекцию точки и на множество Х будем искать в виде ю = и+ Я си»а». (5) »=! Из требования ю Е Х имеем систему линейных алгебраических уравнений аз(а,, а») = б' — (а!, и), 4 = 1,..., тп, !' = 1 для определения коэффициентов !х,..., !х . Определителем этой системы является определитель Грама (89; 192; 353], который для линейно независи- 186 Гл. 4; ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 1, 8 4.
ПРОЕИЩЯ ТОЧКИ НА МНОЖЕСТВО 187 мых а„..., а„будет отличным от нуля. Поэтому искомые сс„..., ст,„существуют и однозначно определяются из системы (6). Для точки ю из (5) будем иметь (ю — и, и — ю) = 2 с!у(ау, е — и) — 2, сг, ( 2, а,(аэ, ау)) = 0 !',= ! '=! !'=! для всех е е Х. Следовательно, по теореме 1' найденная из (5), (6) точка ю будет проекцией точки, и на множество Х. Если ввести матрицу А, строками которой являются векторы а!, э = 1,..., тп, то точку (5) можно записать в виде ю=и — Ат(ААт) '(Аи — Ь).
Предлагаем читателю провести проверку того, что такая точка ю принадлежит Х, т. е. Аю = Ь, и выполняется условие (1) (см. пример 9.3). П р и м е р 4. Пусть Х =(и ЕЕ: (с, и) < Т) — замкнутое полупространство, определяемое гиперплоскостью (с, и) = у. Пусть и (с Х, т. е. (с, и) > у.
Как и в примере 2, попробуем представить проекцию точки и на Х в виде ю = и+ ( у — (с; и))с//с(э Имеем (ю — и, е — ю) = ( у — (с, и))с?с(с) '((с, е) — у) > 0 при всех е е Х, Следовательно, точка ю — искомая проекция. Пример 5. Пусть Х = (и =(и!,..., и") е Е"! сг! < и! < Д, э = 1,... ..., и) — п-мерный, параллелепипед, где аэ, )у„сх! < )э! — заданные числа, э = 1,..., и. Пусть и !Р Х, Положим ю = (ю!,..., юе), где сз,, и! <ою ю! = 1)„и! >Д, Тогда (ю' — и!)(и' — ю!) > 0'для всех е', а! < е! < (эо т,=1:,..., п.
Отсюда, суммируя по з от 1 до и, получаем (ю — иге — ю) > 0 для всех и е Х. Следо- вательно, построенная точка ю является проекцией точки и на множество Х. Пример 6. Пусть Х =Ее=(и=(и',...,и")еЕ"! и'>О, з=1,... ..., и) — неотрицательный ортант, пространства Е". Легко проверить, что проекцией точки и на Х является точка и+ = ((и')+,..., (и")~), где (и))+ = = снах(0; и'), э =1,, п. 3. Критерий оптимальности, сформулированный ранее в теореме 2.3, с помощью оператора проектирования может быть переформулирован следу- ющим образом. Т е о р е м а 4. Пусть Х вЂ” выпуклое замкнутое множество, Х.— множество точек минимума функции 7(а) на Х.
Если и, е Х, и 7(ю) диффвренцируема в точке и„то необходимо выполняется равенство' и„=Рх(и, — сх('(и„)) !У!х > 0 (7) Если, кроме того, 7'(чв) выпукла на Х, то всякая точка и„удовлетворяюн(ая уравнению (7)', принадлежит Х,. Д,оказ ательство. Согласно теореме 1 равенство (7) эквивалентно неравенству (и,— (и,— сэу"'(и,)), и — и,) > 0 Уи Е Х, откуда имеем сг(7'(и.), ив — и„) >'0 !Уе е Х.
Так как сх > О, отсюда получим неравенство (г'(и„), и— — и,) >О при всех и е Х. Таким образом, условия (7) и (2.5) эквивалентны. Отсюда и нз теоремы.2.3 следует утверждение теоремы 3. П Таким образом, если ввести отображение А из Е в Е" по формуле Аи = 'Р (и — стус(и)), (с > О, то условие (7) перепишется в виде и, = Аи„т.
е. и. — неподвижная точка отображения А, Йиже мы увидим, что при некоторых условиях на функцию 7(х) отображение будет сжимающим и,для определения точки и, могут быть использованы свойства сжимающих отображений [89; 393]. Упражнении 1. Найти проекцию точки и е Е" на множество Х=(иЕЕ"; (а!,и)(Ь'!, (ет,и)<Ь ). 2. Найти проекцию точки и е Е" на множества Х=(и.=(и!,...,и"); ей (и1 <р!, ! =1,...,и) (здесь и! ( Дэ, причем возможно, что сч = рг, или а. = -оо, или рь —— оо при некоторых й й Ь); 8.
Выяснить геометричесний смысл равенства (2). 4. Будут ли верными неравенство (1) или равенство (2), если Х вЂ” невыпуклое множество? 8. Охарактеризовать все множества Х из Е", для которых супсествует точка и (4 Х такая, что Рх(й) = е.для.всех е Е Х, '8. Для того чтобы точка же Х:была проекцией точки и нв выпуклое множество Х, необходимо и достаточно, чтобы (е-и, е-ю) > О при всех е Е Х.?Доказать. Выяснить геометрический смысл этого условия.
7. Доказать, что для любого замкнутого множества Х имеет место неравенство !(и— -'РДи)( — !е — Рх(е)() < (и — е! для всех и, е е.Х (Ср, с леммой 2.1.2). 8.'Пусть Х выпуклое.замкнутое мно!кество из Ж". Доказать, что тогда (е Рх(и)( < (е — и, е 'Рх(и)) !?е Е Х Уи Е Е (е Р (и)(з+,(и Р (иЯэ((е и(з Уеех мие!е" 9.
Пусть 7(и) = (Аи — Ь(э, где А —.матрица порядка то х и, Ь с Е"' (см, пример 2,4), Доказать, что х = (и ее": 7(и) =?а17(и) = т" ~ ~'Я. Указание: взять проекцию точки Ь на множество Х =(е ЕЕ: е=Аи, и ЕЕ") и показать, что 1(и) =,!Аи —,Рх(Ь)(~ 4 (Ь вЂ” Рх(Ь)1(, 7„= (Ь -Рх(Ь)('; доказать замкнУтость Х, 19. Убедиться, что если Х = Š— надпространство иэ Е", то условие (2) можно заменить равенством (, — и, д) = О Уд Е Ь. (8) н. пользуясь (8), доказать, что оператор Р проектирования на подпростваанство ъ с е" является линейным, самосопряженным оператором и, кроме того,((Р!( = 1, Р ='Р. 189 188 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА тв х Рис. 4.11 Рис.
4.10 зпр(с, 6) < Т < !п1 (с, а) ьсг с Рис, 4,13 Рис. 4.12 (с,х) > у 1ГхЕХ, Т>(с,у), (с,х)>Т Чхбг1Х. (2) ч Рис. 4.14 Рис. 4.!5 ф 5. Отделимость выпуклых множес 1. В теории экстремальных задач важную роль играют теоремы, называемые теоремами отделимости. Основное содержание этих теорем сводится к тому, что для некоторых двух множеств А а В утверждается существование гиперплоскости такой, что множество А находится в одном из открытых или замкнутых полупространств, определяемых этой гиперплоскостью, а множество  — в другом открытом или замкнутом полупространстве (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
