Ф.П. Васильев - Методы оптимизации (1125241), страница 45
Текст из файла (страница 45)
Но соХ по своему определению принадлежит всем выпунлым множествам, содержащим Х, и поэтому со Х С Иг. Сравнивая с ранее доказанным включением Иг с со Х, заключаем, что со Х = И'. Если Х— выпуклое множество, то с учетом теоремы 5 имеем Х = И' = со Х. Теорема 6 доказана. П Заметим, что выпуклая оболочка двух точен на плоскости представляет собой отрезок, выпухлая оболочка трех точен, не лежащих на одной прямой, — треугольник, В общем случае выпуклая оболочка конечного числа точек на плоскости образует выпуклый многоугольник, а в пространстве — выпуклый мпогограннин. Определение 9. Выпуклая оболочка множества точек ио,и>,...,и„, из Я" таких, что система векторов (ис — ио, ! = 1,, т) линейно независима, называется симплексом, натянутым на эти точки, и обозначается через Я„, = Я (ио,и>,..., и„,). Точки ио, и>,, и,„ называются вершинами симплекса.
В случае т = О, 1, 2, 3 симплекс представляет собой соответственно точку, отрезок, треу- гольнин, тетраэдр. Согласно теореме 6 симплекс Я представим в виде ч и Я =(и>и= д асис,ас>О>=о,,пь ~ а>=11. >=о =о По теореме 6 любая точка выпуклой оболочки множества Х является выпунлой комбинаци. ей нонечного, но, быть может, довольно большого числа точен из Х. Замечательно, однано, то, что в Е" для получения множества со Х достаточно ограничиться рассмотрением выпунлых номбинаций не более чем и+! точек из Х.
Точнее, верна Теорема 7 (Каратеодори). Пусть Х вЂ” произеольное иепустое миожестео из Б". Тогда любая точка и 6 со Х представимо е виде гьтуклой комбинации ие более чем и+ 1 точек из Х. Доказательство, Согласно теореме 6 любая точка и 6 соХ представима в виде и= = о! и, -1-...
+ а и, где ис е Х, ас > О, ! = 1, .. ч и>, а +... + а = 1. Пусть т > и + 1 и все ас > О (если а =О, то число гп может быть уменьшена). В и+1.мерном пространстве рассмотрим векторы бс = (ис, 1), ! = 1,, т. Поскольку т > и+ 1, то эти векторы линейно зависимы, т, е, существуют числа т>,...> т, не все равные нулю и такие, что т>я! + ... ... ц у и = О. Это равенство эквивалентно следующим двум равенствам: „,и,+„.цтти„=О, „>+...+т„=О.
Тогда точка и представима другими выпуклыми комбинациями тех же точек и„..., и П> т (ас-ст)и!= д,' ос и! — л,' т! и! =и. В самом деле, здесь ас >О и, следовательно, ас- стс > О, >=! * ' ' ;=! ' * с=! >ч ч> п !' =1,..., т при всех достаточно малых С и, нроме топь Я (ас — Стс)= ]'' ас С с' 'У> =1. с=! >=1 >=! Поскольку не все тс равны нулю, но т! +...
+ Ты = О, то среди (тс) найдутся положительные. 1бб 15? Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 8 1. ВЫПУКЛЫЕ МНОЖЕСТВА Пусть а,у, ! = ш!и ага! '. Положим ! = а,у, '. При таком выборе ! все а! — 17! Останутся неотрицательными, причем а, — !Т, = О. Это значит, что точку и удалось представить в виде выпуклой комбинации меньшего числа точек и>, .. и и, >, и, „ >, ..
им . Ясно, что последова- тельно применяя описанный прием далее, число точек, участвующих в выпуклой комбинации, можно уменьшить до и+!. !З Теорема 8. Если Х вЂ” замкнутое ограниченное множество из Е", тосе Х замк- нуто и ограначгно, Д о к а з а т е л ь с т в о. По условию существует число Л > 0 такое, чта ~и( < Л для всех и Е Х, т. е. Х с Е(0, Л) — шар радиуса Л с центром в тачке О. Но шар — выпуклое мно- жество. Согласно определению 8 тогда соХ Е 3(0 Л), так что !и) ( Л для всех и Е соХ.
Ограниченность соХ доказана, Докажем замкнутость со Х. Пусть и — предельная точка со Х, (ий) Е со Х н !!ш ий — — и. й ю Согласна теоРеме 7 сУществУют точкИ иы Е Х, числа ай! > О, « = 1,,, и п+ 1, ай! +... ... + ад и „! —— 1 такие, что ий — — ай ! ий! +... + а>и+ ! ид „+ !. Заметим, что !ий ) ( Л, 0 < < аы (1 при всех « = 1,., и и+ 1 н всех й = 1, 2,... Пользуясь теоремой Бальцано — Вей- ерштрасса, сначала из (ий!), (ай!) выберем подпоследовательности (ий !), (ай ), сходяй, ! й, ! Щиеса соответственно к некотоРым и>, а !1 'затем из (ий з), (а з ) — поДпоследовательности (и!.
з) иэ, (айз) — «ах и т. д., наконец, (ий и+!) — «ии+>, ~ай и+!)-«аи „!. Тогда из «- ! и-!. ! ий = )' ай ий ч,ий «ЕХ,ай !~)О,«=1,.,оп+1, г ай ! — — 1,предельнымпе. Реходом пРи йи+ ! — «оа палУчим и = Л,' а иг, а! > О, ~; а! = 1, где и! Е Х, « = 1, .. и и+ 1, «=! ' «=! в силу замкнутости Х. Следовательно, па теореме 6 и 6соХ, что н требовалось. !З Заметим, что требование ограниченности множества Х в теореме 8 существенно: Напзоимер, множество х = (и = (х У) е ез: х > 0 У = игх) замкнУто, но сох = (и = (х У) е е: х > > 0,0 < у < и'х) О ((О, 0)) незамкнуто.
Если Х вЂ” выпуклое, замкнутое множество из Е", то соХ будет замкнутым н без требования ограниченности Х, поскольку в этом случае в силу теорем 5, 6 соХ = Х = Х = соХ. Те о рема 9. Пусть А — произвольное непустог мложгство аз Е". Тогда зцр(с, а) = ЗцР(с, а) = ЗцР (с, а) = ЗцР (с, а) «УсЕЕи изх «ег иеси А Доказательство. Поскольку А с Х, то зцр(с, а) < ыр(с, а). С другой стороны, для л любого ОЕА существуют ай Е А, (ой)-«а. Поэтому из (с ай) < зцр(с а) при й -«со получим А (с, а) < зцр(с, а) для всех ае А.
Следовательно, ьцр(с, о) < зцр(с, а), так чта зцр(с«а) =зцр(с, а), А л А л А Ото>ода же имеем зцр = зцр(с, а). Далее, так как А с со А, та зцр(с, а) < зцр(с, а). С другой сил Л «ил стороны, для любого а 6 со А согласно теореме 6 найдутся а! Е А, а! >О, « = 1, .. и и, а>+... ... + а, =! такие, что а= 2 с«! а! Поэтому г=! (со) = Л,' а«(с, а!) ( ~; с«! зцр(со) =зцр(с а) г=! «=! ег л для каждого а е со А. Следовательно, зцр(с, а) < зцр(с, и), так что зцр(с, а) = зцр(с, а). !3 сил А сил А 4. Приведем условия существования внутренней точки выпуклого множества.
Те арена 10. Пусть Х вЂ” нспустог выпуклое множество аз Е", Длл того чтобы 1и! Х ~ >Э, необходимо и доплаточно, чтобы д!т Х = и. Доказательство. Необходимость. Пусть 1п1 Х у >3>. Тогда для любой вну. тренней точки и множества Х существует г-окрестность О(и, г) = (и: |и — и) < г), также принадлежащая Х. Отсюда вытекает, что минимальным аффинным множеством, содержащим множество Х и, следовательно, шар О(и, г), является все пространство Е". Это значит, что аЛ Х = Е", д!ш Х = и. Достаточность. Пусть й!шХ=и, Тогда аКХ =Еи и найдутся точки и„, и>, ..и иве Е Х таКИЕ, Чта ВЕКТОРЫ и! — иа, ..
и ии — иа — ЛИНЕЙНО НЕВЗВИСИМЫ. НатЯНЕМ На Этн ТОЧКИ симплекс и Согласно теореме 5 Еи с Х, а по тдореме 6 Еи выпукло. Рассмотрим систему линейных алгебраических уравнений г.' .(; — о)*! = — иа (6) >=! Матрица этой системы А =(и, -ио, .. и ии-ио), столбцами которой являются линейно независимые векторы и; — иа, ! = 1, ..
и и, имеет размеры и х и и невырождена. Поэтому система (6) Дла каждого и 6 Еи имеет н пРитом единственное Решение х= х(и) =(х>(и),., их„(и)). Из известных формул Крамера (!92, 353) видно, что функции х (и) непрерывно (и даже линейно) зависят от и. и Опираясь на это свойство решений системы (6), покажем, что любая точка ю = 2 а«иг «=О симплекса Еи прн а! > О, « = О, ., и и является внутренней точкой Еи, В самом деле, для такой и и и точки ю имеем ю — ио —— ~.' ««,и! — 2; а>ио — — 2, а>(и! — ио). СРавнение с (6) показывает, что ч=а >=О ч=а с« =х (ю), « =1, ..
и и, В силу непрерывности х (и) тогда х (и) > О, « = 1,, и для всех и Е и еО(ю, г)=(и: !ы — ю|<г), где г >Π— достаточно малое числа. ФУнкциЯ ха(и)=1 — Л' х (и) «=! также непРеРывна, пРичем хо(ю) =! — т а! = аа > О. ВзЯв г > 0 достаточно малым, можем считать, что то(и) > 0 для всех и е О(ю, г). Таким образом, для каждой точки и Е О(ю, г) в силу (6) имеем представление и = ив+ и и х>(и)(и!-ио) = Л,' х (и)ыг, где х>(и) >О, 2, х (и) = 1. Это означает, что О(ю, г) С Еи, «=! «=О «-О Следовательно, ю Е1п1 Зи, Отсюда и из включения Еи с Х следует, что О(ю, г) с Х, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
