Ф.П. Васильев - Методы оптимизации (1125241), страница 55
Текст из файла (страница 55)
Поскольку р(и, Х) = !п[ ]и — и[ — расстояние от точки ы до множества яеХ Х, то из определения 1 следует, что р(и, Х) = [и — Р (и)] < ~и — и! |Уп е Х, |Уы н Е", $4. ПРОЕКЦИЯ ТОЧКИ НА МНОЖЕСТВО 183 Если и ИХ, то, очевидно, всегда Рх(ы)=ы. Однако проекция на множество существует ие всегда. Например, если Х = (и Н Е": [и[ < 1) — открытый единичный шар в Е", то ни одна точка ы гр Х не будет иметь проекции на это множество. Однако если множество Х замкнуто, то любая точка ы н Е" имеет проекцию на Х вЂ” это было доказано в следствии 1 к теореме 2.1.3. Проекция точки на множество может определяться неоднозначно (рис. 4.6). Однако, как показывает следующая теорема, для выпуклых множеств такая ситуация невозможна (рис.
4.7). Те о ре ма 1, Пусть Х вЂ” выпуклое замкнутое множество из Е". Тогда: 1) всякая точка и е Е" имеет, и притом единственную, проекцию на это множество; 2) для того чтобы точка ю и Х была проекцией точки ы на множество Х, необходимо и достаточно выполнения неравенства (см. рис, 4.7) При этом если Х вЂ” аффинное .множество (см. пример 1.4), то вме- сто (1) можно писать Д о к а з а т е л ь с т в о.
Рассмотрим функцию д(п) = [и — тз[я переменной о е Е" при произвольной фиксированной и а Е". Поскольку д(п) сильно выпукла на Е", то по теореме 3.1 эта функция достигает своей нижней грани на Х в единственной точке ю Е Х, Это означает, что ]и — и!з ) ]ю — и[з или ~п — ы[>]ю — и[ при всех и НХ, причем равенство здесь возможно только при и = ю. Остается принять Р (ы) = ю. Докажем второе утверждение теоремы.
Согласно теореме 2.3 для того, чтобы функция д(п) достигала минимума на Х в точке ю, необходимо и достаточно, чтобы (д'(ю), и — ю) = 2(ю — и, о — ю) > О при всех и а Х, что равносильно неравенству (1), Наконец, пусть Х = (и н Е": Аи = Ь) — аффинное множество. Поскольку это множество выпукло и замкнуто, то неравенство (1) сохраняет силу и здесь.
Аффинное множество обладает следующим замечательным свойством: если в, и Е Х, о ~ п„то и 2ио — и Е Х, что пРовеРЯетсЯ непосРедственно. Поэтому еслй здесь взять по — — Р (и) = ю н Х, то 2ю — и е Х при любом Гл, 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА (3) (Р (и) — и, Р (и) — 'Р (~)) >0 Сложим эти два неравенства.
Имеем Рис. 4.9 Рис. 4.8 2' аз(а!, а,) = 6! — (а!, и), г = 1,..., тть, !'= ! (5) выборе и е Х. Подставим в (1) вместо и точку 2ю — и. Получим (ю — и, 24е— — и — ш) = (и» вЂ” и, и! — и) > 0 при всех и е Х. Сравнивая полученное неравенство с (1), приходим к равенству (2). П Покажем, что оператор проектирования на выпуклое множество обладает сжимающим свойством. Те о р е м а 2.
Если Х вЂ” выпуклое замкнутое множество из Е", то Рх(и) — Рх(и М < ~и — и~ !Уи, и Е Е". До к а з а т е л ь с т в о. Из неравенства (1) имеем (Р (и) — и, Рх(и) — 'Р (М) >О. Поменяв ролями точки и и и в последнем неравенстве, получим (Рх(и) — и — 'Рх(и) + и, Рх(и) — 'Рх(и)) > 0 Отсюда следует Рх(™)-Рх(и)1'< (Р ( )-'Рх(и), и — и) !У, ЕЕ" (4) Применим к правой части (4) неравенство Коши — Буняковского Р (и) — Рх(и)Р< |Р (и) — Р (и)~ ~и — и! и, и е Е".
разделив на ~Рх(и) — Рх(и)~ ФО, получим требуемое неравенство (3), Если !Рх(и) — 'Рх(и)~ = О, то (3) очевидно. П Теорема 3. Пусть Х вЂ” выпуклое замкнутое множество из Е", пусть 'Р (М) = (и Е Х; Вх е М, что и = Р (х)) — множество значений оператора проектирования на множестве М СЕ". Если М вЂ” компактное множество, то Рх(М) также компактно. Доказательство.
Возьмем ЧхеМ. Так как 1п1 1и — х~'= ~Р (х)— еех — х~в, то, применяя к сильно выпуклой функции д(и) = ~и — х~' неравенство (3.3), получим: ~и — Р (х)Г < !Р(и) — !Р(Рх(х)) < !Р(и) = )и — х)в или ! и — Рх(хИ < ~и — х~ !Ух е М, !1и а Х. Отсюда, фиксируя и Е Х имеем: 'Р (хй < ~и( + ~и — х~ < 2(и( + (х! < 2)и( + вцр )х) Чх е М.
Ограниченность лем множества Р (и) доказана. Докажем замкнутость Р (М). Возьмем произвольну!о последовательность (х,) е Р (М), (х„) - х. По определению множества Рх(М) найдется точка иь ЕМ, такая, что хь ='Р (иь), !с = 1, 2,... Из ограниченности М следует ограниченность (и,). Применяя теорему Больцано — Вейерштрасса, можем считать, что (и ) — и .
Так как М замкнуто, то и, е М. 11о теореме 2 оператор проектирования непрерывен, поэтому (х„='Р (и„)) — ! х =Рх(иь). Это значит, что х ЕР (М), т. е. множество Рх(М) замкнуто. Следовательно, 'Р (М) компактное множество. Теорема 3 доказана. П 2. Приведем примеры множеств, проекция на которые может быть выписана явно. $4. ПРОЕКЦИЯ ТОЧКИ НА МНОЖЕСТВО 185 П р и м е р 1.
Пусть Х = Я(иь, В) =(и ЕЕ": 1и — ис~ < Я) — шар радиуса В > 0 с центром в точке и . Из геометрических соображении (рис. 4.8) ясно, что проекцией точки и ф Х является точка !е =и + В(и — и )/~и — и ). ,.;.1--;.. -:1-',:;.:: Для строгого доказательства этого факта достаточно проверить выполнение неравенства (1). Имеем (и — и, и — и!) = (В/~и — ис~ — 1)((и — и, и — и ) — Я~и — и /) > О, так как ~и — ис! > В, а (и — и„и — и ) < /и — и / )и — и ~ < ~и — и /Я в силу неравенства Коши — Буняковского дпя всех и е Х. Пример 2. Пусть Х =Г=(и е Е": (с,и) = у) — гиперплоскость; здесь с е Е", с ф О, Т = сопв1.
Пользуясь геометрическими соображениями (рис. 4.9), проекцию точки и ф Х на Х будем искать в виде !е = и + ас. Определяя число а из условия и! е Х, имеем ю = и + (Т вЂ” (с, и) )с//с/в. Поскольку (ю — и, и — и!) =(Т вЂ” (с, и))с/~с~~ ° (с, и — и) =0 при всех и е Х, то согласно теореме 1 найденная точка !е представляет собой проекцию точки и на Х. Пример 3. Пусть Х =(и еЕ": (а!, и) = 6!, 4 =1,..., гп) — аффинное множество; здесь а! е Е", 5! = сопв1, 4 = 1,..., гп. Можем считать, что векторы а„..., а линейно независимы и тп < и (если гп = и, то Х будет состоять ив однойточки). Проекцию точки и на множество Х будем искать в виде я=и+ 2, аза, (5) ,=! Из требования ш е Х имеем систему линейных алгебраических уравнений для определения коэффициентов а„..., !х„.
Определителем этой системы является определитель Грама 189; 192; 353], который дпя линейно независи- 187 186 Гл. 4. ЭЛЕМЕНТЫ ВЪ|ПУКЛОГО АНАЛИЗА ш = и + ( у — (с; и))с/!с!з а~~:'т „ .г и,=Рх(и.— сх)"(и,)) У»х >О, (7) мых а„..., а будет отличным от нуля. Поэтому искомые сх„..., гт,„существуют и однозначно определяются из системы (6). Для точки ш из (5) будем иметь ю l (ш — и, и — ш) = ~ пу(ач и — и) — ~ с»,('), с» (а„ау)) =0 »'=1 для всех и е Х. Следовательно, по теореме 1' найденная из (5), (6) точка ш будет проекцией точки: и на мно|кество Х. Если ввести матрицу А, строками которой' являются век~оры а», з = 1,..., пь, то точку (5) можно записать в виде ш = и — Ат(АА») '(Аи — Ь).
Предлагаем читателю провести проверку того, что такая точка ш принадлежит Х, т. е. Аш = Ь, и выполняется условие (1) (см. пример 9.3). П р и м е р 4. Пусть Х = (и е Е"; (с, и) < Т) — замкнутое полупространство, определяемое гиперплоскостью (с, и) = Т. Пусть и ф'Х, т. е. (с, и) > у. Как и в примере 2, попробуем представить проекцию точки и на Х в виде Имеем (ш — и, и — ш) = ( у — (с, и))с/!с~ '((с, и) — у). > 0 при всех е е Х, Следовательно; точка ш — искомая проекция.
Пример 5. Пусть Х =(и=(и',..., и") е Е"; ст» < и" <)у„з =1,... ..., и) — п-мерный параллелепипед, где стыди ст, < )3! — заданные числа, з = 1,..., п. Пусть и ф Х. Положим ш =(ш',..., ш"), где т с»„и' < а», Тогда (ш' — и')(е! — тп') > 0' для всех е'„с»» < е' < ))„з=!',..., п. Отсюда, суммируя по ( от 1 до и, получаем (ш — иее — ш) > 0 для всех и е Х.
Следо- вательно, построенная точка ш является проекцией точки и на множество Х. Пример 6. Пусть Х=Е„"=(и=(и!,...,и")ЕЕ": и!>О, з=1,... ..., п) — неотрицательный~ ортант. пространства Е". Легко проверить, что проекцией точки и на Х является точка и" =((и')",..., (и")+), где (и))+ = = |пах(О; и'), з = 1,..., п. 3. Критерий оптимальности, сформулированный ранее в теореме 2.3, с помощью оператора проектирования может быть переформулирован следу- ющим образом. Теорема 4. Пусть Х вЂ” выпуклое замкнутое множество, Մ— множество точек минимума функции 7"(х) на Х. Если и, е Х„и 7'(х) дифференцируема в точке и„, то необходимо выполняется равенство Если, кроме того, Лх) выпукла на Х, то всякая точка и„удовлетворяюи(ая уравнению (7), принадлехсит Х,.
Д,о к а з а т е л ь с т в о. Согласно теореме ! равенство (7) эквивалентно неравенству (и„— (и,— гху(и)), и — и ) >0 Чп е Х, откуда имеем ст ()" (и ), ив $4. ПРОЕКЦИЯ ТОЧКИ НА МНОЖЕСТВО =Р ( — У'( )), >О, Упражнения 1.:Найти проеицию точки и е е" на множество Х = (е С Еещ(а!, е) < Ь, (ех, и) < Ь ). — и,) >'0 !уе е Х. Так как ст > О, отсюда получим неравенство (у'(и,), ив — и„) > 0 при всех и е Х. Таким образом, условия (7) и (2.5) эквивалентны, Отсюда и из теоремы 2.3 следует утверждение теоремы 3. Г) Таким образом, если.ввести отображение А из Е" в Е" по формуле то условие (7) перепишется в виде и„= Аи„т. е, и, — неподвижная точка отображения А.
Ниже мы увидим, что при некоторых условиях на функцию )'(х) отображение будет сжимающим и,для определения точки и, могут быть использованы свойства сжимающих отображений 189; 393]. 2. Найти проекци!о тачки и Е Е" на множество Х='(о.=(е',...,е"); »»! <и» <Р; »=1») (зДесь и,. < Рп.ЦРичем возможна, что и» = Р», или о. = — оо, или Рь —— со пРи некотоРых», Ь' Й), 8.:Выяснить геаметричеокий смв|сл равенства (2). 4. Будут ли верными неравенства (1) или равенство (2), если.Х вЂ” невыпуклое множество? б. Охарактсризовать все множества Х из Е", для которых существует точна и К Х такая, что Рх'(и) = е,для,всех е е Х.
*'6. Для того чтобы точка ю Е Х:была проекцией точки и нв,вмпуклае множество Х, необходимо и достаточна, чтобы (е — и, е- ю) ) 0 при всех е е Х„Доказать. Выяснить геометрический смысл атоса условия. 7. Доказать, что для любого замкнутого мне»кества Х имеет место неравенство )(ив — 'РУ(и)! — |е — Рх(е)|| < )и — е! дла всех,и, е Е Т (СР, с леммой 2.1.2). а.'Пусть Х выпуклое.
замкнутое мно»нество из Ее. Доказать, что тогда )е — Рх(е)| < (е — о, е —,Рх(е)) Уе е Х, Уи е Е", )е — Рх(п)! 4|е — Рх(е)! < (е — и! еее х, мое!е" 9. Пусть у(е) = |Ае — Ь|т, где А — матрица порядка та.х и, Ь е Ею (см. пример 2.4). Доказать, что Х,= пеле: у(и)=!п11(е)=Д фта. ( Указание: взять проекцию точки Ь на множество Х =(е еЕ~; е = Ае, ее Е") и показат~, что 1(е) = !Ам -,Р .'(Ь)!в+ |Ь вЂ” Р . (Ь)|з, Д = |Ь -Рх(Ь)1'; доказать земкнутасть Х, 1О. Убедиться, чта если Х = Л вЂ” подпространство из Е", то условие (2) можно заменить равенствам (ю — е, д) = 0 УЕ Е Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
