Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 45
Текст из файла (страница 45)
4.7) Оо — и, о — ю) ) О 4г'г ~ Г. При этом ес.ли П вЂ” аффинное множество (см. пример 1.4), то влгесто (1) можно писать (й — и, о — иО = О 47'о ~ П. (2) Доказательств о. Рассмотрим функцию у(о) = !о — и)4 переменной о4НЕ" при произвольной фиксированной ичнЕ". Поскольку д(о) сильно выпукла на Е, то по теореме 3.1 эта функция достигает своей нижней грани на У в единственной точке ю 4н 4л'. Это означает, что !о — и!' > !ю — и!' или !о — и! ~ !ю — и! при всех огн У, причем равенство здесь возможно только при и = и.
Остается принять .Уо(и)= ю. 1ИО элкмкнты ВыпуклОГО АнАлизА Докажем второе утвергггдение теоремы. Согласно теореме 2.3 для того, чтобы функция д(о) достигала минимума на П в точке пг, необходимо и достаточно, чтобы <д'(го), о — го> =2<ю — и, о — го> ~ О при всех аж П, что равносильно неравенству (1). Наконец, пусть Ег=(игнЕ": Аи = б) — аффинное множество. Поскольку это множество выпукло п замкнуто, то неравенство (1) сохраняет силу п здесь. Лффинное множество обладает следующим замечательным свойством: если о, о, ж У (от-о,), то и 2о, — о ~ Ег, что проверяется непосредственно. Поэтому если здесь взять о, =Ус(и) = ю ж Ег, то 2го — и ~ П при любом выборе ож К Подставим в (1) вместо о точку 2го — о. Получим <го — и, 2го — о — го> = <го — и, ю — о> ~ О при всех огн К Сравнивая полученное неравенство с (1), приходим к равенству (2).
Покажем, что оператор проектирования на выпуклое миогкество обладает сжимающим свойством. Теорема 2. Если Ег — выпуклое замкнутое тэножество из Е", то ! Уь (и) — Уо (о) ( ( (( и — г ( 7и, о е= Е". (3) Д о к а з а т е л ь с т в о. Из неравенства (1) имеем <Уо (и) — и, Уо ( о) — Ув (и) > > О. Поменяв ролями точки и и о в последнем неравенстве, получим <Уе ( о) — о, Уе (и) — Уо (о) > > О. Сложим эти два неравенства. Имеем <Уе(.)- гг-У.(.)+., Уе(о)-Уе(у) > ~ О. Отсюда следует ) У~(и) — У~(о) (е( <У~(и) — Уо(о), и — о> ( ~К(УО(и) — Уо(о)( !и — о! гвгг, ос= Е". Разделив на !Уг (и) — Уе(о)! чАО, получим требуемое неравенство (3).
Коли !Уг (и) — Уи (о) ! = О, то (3) очевидно. 2. Приведем примеры множеств, проекция на которые может быть выписана явно. Пример 1. Пусть Ег=Я(ио Л)=(ижЕ: !и — и,~ ~Л)— гпар радиуса Л ~ О с центром в точке нь Из геометрических сообраягений (рис. 4.8) ясно, что проекцией точки ггФ П является точна = и, + Л(п — ~,)Л вЂ” гг,).
Для строгого доказательства этого факта достаточно проверить выполнение неравенства (1). Имеем <го — и, о — го> =(Л/!и — и,! — 1) (<и — и„о — и,>— — Л(гг — и,!) > «О, ПРОЕКЦИЯ ТОЧКп НА МНОЖЕСТВО 191 так как 1и — и,! >В, а <и — ив и — и,> < ~и — и,~ !и — и'1 < < 1и — и,!В в силу неравенства Коши — Буняковского для всех и ы Г/. Пример 2. Пусть У=Г=(иыЕ": <с, и> =() — гиперплоскость; здесь сыЕ, сФ О, ( = сопз1. Пользуясь геометрическими соображениями (рпс. 4.9), проекцию точки иФ (/ на У ( Рзс.
4.8 Ряс. 4.9 (4) для определения коэффициентов иь ..., и . Определителем этой системы является определитель Грама [54, 93, 164], который для линейно независимых аь ..., а будет отличным от нуля. Поэтому искомые яь ..., а существуют и однозначно определяются из системы (5). Для точки и из (4) будем иметь тп 7В ! я$ (ц~ — и,и — ю) = ~сс;(а;, Р— и) — ~я;~ ~аз(аьаз)) =О 1=г 1=1 9=1 будем искать в виде и = и+ас. Определяя число я из условия йи (/, имеем и~ = и+(( — <с, и>)с/~СР.
Поскольку <и — и, о — и» =(( — <с, и>)/~сР <с, и — и> =О при всех иы У, то согласно теореме 1 найденная точка и представляет собой проекцию точки и на </. Пример 3. Пусть (/= (иыЕ": <аь и> =Ь', ~ = 1, ..., т)— аффинное мноя1ество; здесь а;ыЕ", Ь'=сопзь (1=1, ..., т).
Можем считать, что векторы а„..., а„линейно независимы и т < п (если т = п, то У будет состоять из одной точки). Проекцию точки и на множество У будем искать в виде и=и+ ~',аа;. 1<т Из требования и ы (/ имеем систему линейных алгебраических уравнений т ~ а; (аь а;) = У вЂ” (аь и>, 1 = 1,..., т, (5) 1=г 192 элементы Выпут»лого АНАлизА [Гл. 4 для всех о «(»'. Следовательно, по теореме 1 найденная из (4), (5) точка ш будет проекцией точки и на мпоя ество 5».
Если ввести матрицу А, строками которой являются векторы а, (» = 1, ... ..., и»), то точку (4) можно записать в виде и» = и Ат(ААт)»( 4и б) Предлагаем читателю провести проверку того, что такая точка ш принадлежит 6», т. е. Аш = б, и выполняется условие (1). Пример 4. Пусть П=(и«Е": <с, и>< "() — замкнутое полупространство, определяемое гиперплоскостью (с, и) = (. Пусть иФ Г, т. е. <с, и> ) (. Как и в примере 2, попробуем представить проекцию точки и на У в виде ш = и+(( — <с, и))с/!с»»'. Имеем (и: — и, о — и» =(( — (с, и))»с! '((с, о) — ()~ 0 при всех о«ь». Следовательно, точка ш — искомая проекция. Пример 5. Пусть 6»=(и=(и', ..., и")«Е": а»<й<рь 1=1, ..., и) — и-мерный параллелепипед, где а», 'р» (а»('р»)— заданные числа, »=1, ..., и.
Пусть и«» 6». Положим ш =(ш', ... ..., ш'), где » и аи и»(аи ин р», и») р», и', а»(и»(()и » = 1, ..., и. Тогда (ш» — и') (о' — ш») > 0 для всех о' (а» ( о' ~ ~'рь 1 = 1, ... ..., и). Отсюда, суммируя по 1 от 1 до и, получаем <ш — и, ив — ш) ~ 0 для всех о«Г Следовательно, построенная точка ш является проекцией точки и на множество ь».
Пример 6. Пусть 6» = Е+ =(и =(и',..., и"): и»)0, » = = 1, ., п) — неотрицательный октант пространства Е". Легко проверить, что проекцией точки и на У явчяется точка и+ = ((и')+, ..., (и")+), где (и»)+ = пъах(0; и») (» = 1, ..., и). 3. Критерий оптимальности, сформулированный в теореме 2.3, с помощью оператора проектирования мон'ет быть переформулирован следующим образом. Т е о р е м а 3.
Пусть <»' — выпуклое множество, » (и) «С»((»), Пе — множество точек минимума у»ункиии г (и) на 5». Если ие ен»те, то необходимо выполняется равенство и„=а.о(и — аг" (ие)) »»а)0. (6) Если, кроме того, г(и) выпукла на 6», то всякая точка ие, удовлетворяющая уравнению (6), принадлежит 6»е. Доказательство. Согласно теореме 1 равенство (6) эквивалентно неравенству (и — (и — аГ (и )), о — и„) ) 0 (о»и «П), откуда имеем а(Х' (и ), о — и ) > 0 (о «Г). Поскольку а) О, то отсюда получим неравенство (л'(ие), о — ие)))0 прн з ь) отдвлимость вьпп|клых множвств 193 всех о»в с»". Таким образом, условия (6) и (2.5) эквивалентны. Отсюда и из теоремы 2.3 следует утверждение теоремы 3.
Таким образом, если ввести отображение А из Е" в К" по формуле Аи=Уи(и — а»»'(и))» а)0» то условие (6) перепишется в виде и = Аи, т. е. и — неподвижная точка отображения А. Ниже мы увидим, что прн некоторых условиях на функцию У(и) отображение будет сжимающим и для определения точки ии могут быть использованы свойства ся»имающих отображений [54, 179).
У яр аж веккя. 1. Найти проекцию точки и»вЕ" ва множество У (и»вЕи. (и|, и) < Ь!, (а» и) < Ь») 2. Найти проекцию точки и»в Е" ка множество У = (и = (и', ..., и"): с» < и» < ()», $ = 1, ..., и) (здесь и» <))», причем возможно, что и» = ()ь вли о» = — »»и, вли Зь = ао орк некоторых й у, Ь). 3. Выяснить геометрический смысл равенства (2). 4. Будут лк верными неравенства (1) клк равенства (2), если У вЂ” вевыпуклое мкожестзо7 5. Охарактеркзовать все множества У кз Е", для которых существует точка и ф У такая, что Уи(и) = и для всех и ж У. 6.
Для того чтобы точка ю ж У была проекцией точки и ва выпуклое мпожество У, необходимо к достаточно, чтобы <и — и, и — ю» О при всех и ж У. Доказать. Выяснить геометрический смысл этого условия. 7. Доказать, что для любого замкяутого множества У имеет место яеравекство ))и — Уи(и)) — )и — йи(и))) < )и — и( для всех и, и »в У (ср. с леммой 2.1.2).
8. Пусть У вЂ” выпуклое заыккутое множество из Е". Доказать, что тогда ) и — й»п(и) )зк (и — и,и — Ро(и))»»и»и У, Уи»и Е", ) и — Уг» (и) )з+ ~ и — Уп (и) !з ~ ) и — и ) Уи я У, Уи»в Еи. 9. Пусть 2(и) = )Аи — Ь)', где А — матрица порядка т Хп, Ь»иЕ"' (см. пример 2.4). Доказать, что Уи ~и»й Еи' у (и) ш1 у (и) = уи ~ чЫЗ' ли Указание: взять проекцию точю| Ь ка множество У= (и»вЕи: и = Аи, и»вЕ") к показать, что Х(и) = (Аи — Ь.и(Ь))»+ )Ь вЂ” Уи(Ь))», У = ) Ь вЂ” й. (Ь) )з; заыквутость У см.
в лемме 9,3. 3 5. Отделимость выпуклых множеств 1. В теории экстремальных задач важную роль играют творе|мы, называемые теоремами отделилости. Основное содержание этих теорем сводится к тому, что для некоторых двух множеств А и В утверждается существование гиперплоскости такой, что множество А находится в одном из открытых или аамкиутых полупространств, определяемых этой гиперплоскостью, а множе- ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА ~гл, г ство  — в другом открытом или замкнутом полупространстве (см. пример 1.3), т. е. гиперплоскости, которая отделяет эти два множества.
Определение 1. Пусть А и  — два множества из Е". Говорят, что гиперплоскость <с, и> =Т с нормальным вектором сФО отделяет (разделяет) множества А и В, если <с, а> >Т при всех аж А и <с, Ь> < ( при всех Ь ыВ, или, иначе говоря, выполняются неравенства зпр (с, Ь) ( у < 1п1 (с, а).
Ьеа гнл (2) Коли зпр(с,Ь)((п1 (с,а), то говорят, что множества А н В ыев вал сильно отделены, Коли <с, Ь> « с, а> при всех ага А, Ь жВ, то говорят о строгом отделении этих множеств, Если выполнено (1), причем существуют такие точки а, я А, Ь, ы В, что <с, Ь„> < « с, а,>, то говорят, что множества А, В собственно отделимы. Понятие собственной отделимости введено для того, чтобы исключить из (1) вырожденный случай, когда оба множества А, В лежат в разделяющей гиперплоскости и, возможно, даже имеют общие относительно внутренние точки. Заметим, что в определение 1 множества А и В входят несколько несимметрично.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
