XIV Аттетков и др. Методы оптимизации (1081420), страница 15
Текст из файла (страница 15)
Для выпуклой комбинации с к = 2 слагаемыми утверждение теоремы верно (оно равносильно определению выпуклого множества). Пусть утверждение теоремы верно для любой выпуклой комбинации, содержащсй а СЛаГаЕМЫХ. ВЫбЕрЕМ В Е ЭЛЕМЕНТЫ Х1, ..., Хк, Хкт1 и произвольные неотрицательные числа а1, ..., аы а1, у1, сумма которь1х равна единице. Отметим, что если аь+1 = 1, то все остальные числа а,, равны нулю и выпуклая комбинация рассматриваемых элементов совпадает с х~+1, так что утверждение теоремы в этом случае тривиально и его справедливость очевидна. ПУсть аь е1(1. Положим Л = 1 — аеа1 и 11, = — ', г = 1, й. Тогда 11, > О, г = 1, Л, и Поэтому, согласно предположению, у = 191 х1 + ... + ф,хя Е Е.
Отсюда заключаем, что а1Х +... +авХ +а111Х Ь и-~-1 =Л(Д, '1+...+9,.х")+(1 — Л) '" = = Лу+ (1 — Л)х~ +~ е Е. Таким образом, произвольная выпуклая комбинация элементов множества Е, содержащая 1+1 слагаемых, принадлежит Е. Согласно принципу математической индукции, любая выпуклая комбинация элементов множества Е принадлежит Е. ~ Теорема 3.2. Пересечение любого числа выпуклых множеств является выпуклым множеством. 1ОО з. луииимизлция выпуклых функций Пусть А — - некоторое семейство выпуклых множеств в линейном пространстве,С.
Рассмотрим множество Пусть х1 и хз принадлежат Е. Тогда они принадлежат любому множеству Р е А. Поскольку по условию множество Р выпукло, для любого Л е (О, 1) элемент Лх1+ (1 — Л)хэ принадлежит Р. А так как Р Е А выбрано произвольно, то Лх'+ (1 — Л)хэ е ( 1 Р = Е. Значит, множество Е выпукло. > Пример 3.4.
Рассмотрим в К" множество Е элементов х = (хм ..., х„), координаты которых удовлетворяют системе неравенств анх1+и1эхз+... +а1„х„< вм а21Х1 + аэз хэ + .. ° + О2пхи < 62, (3.1) а„нт1+ вп12хв+... + а~~,хв ~ (Ьпг Множество Е является выпуклым. Чтобы доказать это утверждение, изменим представление множества. Введем векторы а, = (а,ы ..., а,„). Тогда с помощью стандартного скалярного произведения в Ы' систему неравенств (3.1) можно записать следующим образом: (х, а,) < б„г' = 1, а. Другими словами, множество Е представляет собой пересечение т полупространств. Поскольку любое полупространство является выпуклым множеством, то и множество Е выпукло.
ф Множество .Е с К', заданное системой неравенств (3.1), а также любое конечное пересечение полупространств в евклидовом пространстве будем называть выпуклым мноеоеранным множеставом. 1О1 3. Ь Выпуклые множества Выпуклую комбинацию ст1ж~ +... + стажа элементов линейного пространства назовем стпрозо выпуклой комбинацией, если все ее коэффициенты положительны. В частности, выпуклая комбинация Лж' + (1 — Л)аз строго выпукла, если Л Е (О, 1).
Элемент ж Е Е называют крайней точкой множества Е С ь". (или его вершиной), если этот элемент не может быть представлен в виде строго выпуклой комбинации двух различных элементов из Е. Иначе говоря, если х = Лж~+ (1 — Л)х~, где жт, язз е Е, Л е (О, .1), то жт =;вз = а. Етжи выпуклое множество не имеет крайних точек, то его называют строго выпуклым мнозтсестпв ом. Пример 3.5. У отрезка ~а~,.в~1 б ь" крайними точками являются элементы х и з, и других крайних точек у отрезка нет. В Кз у выпуклого многоугольника крайними точками являются его вершины.
У круга Е С лс,'-', заданного уравнением хт + хз < 1, множество крайних точек представляет собой 2 2 окРУжность Язт + Яз з— — 1. ф Никакая внутренняя точка множества Е С Н" не может быть крайней точкой этого множества. Действительно, если ао б Š— внутренняя точка Е, то существует окрестность* о" = ~х Е лсв: (х — х~! < е), целиком принадлежащая Е. Значит, множеству Е принадлежат элементы а =-:во+со и и =- а — са, где а .. произвольный вектор, для которого ~а~ < 1. Очевидно, что аб = О,осх' +О,баз.
Все линейное пространство —. выпуклое множество. Но, как следует из доказанного, .в этом множестве нет крайних точек. Крайних точек также не имеет аффинное многообразие. Выпуклой оболочкой произвольного подмножества Е линейного пространства ь". называют пересечение всех выпуклых множеств в ь", которые содержат в себе множество Е. *Здесь н далее ~н~ обозначает стандартную норму в кчк элемента ж. 102 з. л!инимизлция выпуклых функций Теорема 3.3.
Выпуклая оболочка множества Е совпадает с множеством всех выпуклых комбинаций элементов множества Е. ~ Покажем, что множество Е всех выпуклых комбинаций элементов множества Е является выпуклым. Выберем в Е произвольные элементы у' и у и рассмотрим их выпуклую комбинац ю у=ау!+(1 — о)у~., Е [О., Ц. Пос о~~~у у" уз ринадлежат Е, их можно представить как выпуклые комбинации элементов множества Е: ь, у'= ~! !!„хо, и=1.,2, где ь., ро)0, 1=1,2, 1=1,й!, '! !!0=1, 1=1,2. ! =-! Подставим эти представления в выражение у = оу! + (1 — а)уз: /С1 й~ у = ~ ор.
х! +~(1 — а)н хэви. В правой части равенства линейная комбинация элементов хо, г = 1, 2, у' = 1, 1!„принадлежащих множеству Е, является выпуклой комбинацией, так как все коэффициенты линейной комбинации неотрицательны, а их сумма равна единице: а!!! +~ (1 — о)!зз, = !=! !=! ь1 ь! =о~~ р!;+(1 — а)Яузу=о 1+(1 — с!) 1=1. Следовательно, элемент у можно представить в виде выпуклой комбинации элементов множества Е, а потому он будет принадлежать Е.
В силу того что элементы у!, .уз и число о Е (О, 1] выбирались произвольно, множество Е выпукло. 1О3 3.!. Выпуклые множества Выпуклую оболочку конечного множества Е С Б'.", содержащего пу+ 1 различных точек х', называют выпуклым мноеоеранником. Если и1, = п, и элементы х'., !' = 1, и+1,. не принадлежат какой-либо гиперплоскости, то выпуклую оболочку множества Е = 1х, ..., хп 1 ) называют симплексом, а точки х' вершинами симплекса.
Отметим, что условие, согласно которому элементы х', .! = 1, п+1, не принадлежат какой-либо гиперплоскости, равносильно линейной независимости векторов х! — х ", 1 = 2, и+1. Согласно теореме 3.3, любую точку симплекса можно представить в виде выпуклой комбинации его вершин. Отметим, что такое представление единственно.
Действительно, если х, ..., х"" вершины симплекса и имеют место предста- вления х=а!х +озх +...+аье!х 1 2 ь-~-! х = Ах +!ггх +... +Ке1х то, вычитая из первого равенства второе, получаем уух + угх +...+ уьеух =О, 1 2 Ь-~-1 4, ! = 1, п,+1, удовлетворяют ра- где коэффициенты у, = о,— венствам и-!-! и-1- ! ~ у, = ~> о, — ~ У1, = 1 — 1 = О. 1=1 Пусть выпуклое множество Р включает в себя Е. Тогда, согласно условию выпуклости, множество Р содержит любую выпуклую комбинацию своих элементов, в частности элементов множества .Е.
Следовательно, множество Г включает в себя множество Е. Таким образом, множество .Е является подмножеством пересечения всех выпуклых множеств, содержащих в себе Е. Но поскольку множество Е само является выпуклым множеством, содержащим Е, .то оно совпадает с указанным пересечением. ° 1О4 3. 81ИНИМИЗггНИЯ ВЫПУКггЫХ ФУЕ)КЦИЙ Предположим, что один из коэффициентов у„например у„т1, тг отличен от нуля. Тогда 71~.1 —— — ", у, и г=1 1 2 к+1 ъх + 72х + " + зь«1 х = 71(х' — х~"')+...+ у (х" — х~«~) =О. (3.2) Так как уь «1 ~ О, то и один из коэффициентов 7„1 = 1, и, отличен от нуля. Значит, в силу равенства (3.2) элементы Х' — Х"+', 1 = 1, Пг ЛИНЕЙНО ЗаВИСИМЫ. ОтСЮДа ЗаКЛЮЧаЕМ, ЧтО существует вектор а, ортогональный всем этим векторам, т.е.
(а, х' — х""1) =О, 1=1, пг или (а, х') = (а, ха~ ), 1 = 1, о. Положим с= (а, х" «1). ТогДа все элементы х', 1 = 1г в+1г УДовлетворяют уравнению (а, х) = с, а значит, принадлежат одной гиперплоскости. Но это противоречит предположению, согласно которому эти элементы являются вершинами симплекса. Пример 3.6. В Рт« симплексом является отрезок (одномернь1й симплекс), в )и треугольник (двумерный симплекс), в тетраэдр (трехмерный симплекс).
Теорема Зей (тпеорема Каратпеодори*). Любую точку х выпуклой оболочки Й произвольного множества Е С )й можно представить выпуклой комбинацией элементов из Ь', количество слагаемых в которой не превышает п+ 1. ~ Каждую точку х Е 11 можно представить в виде выпуклой комбинации Л1х1+... + )г х~ элементов х' Е Е, 1' = 1, ш. Мы можем считать, что число т, ". это наименьшее число слагаемых в выпуклой комбинации элементов множества Я, равной заданному элементу х.
Если гв < и+1, то утверждение теоремы верно. Поэтому предположим, что га > и+ 1. Тогда векторы х' — х1, 1 = 2, ш, линейно зависимы, поскольку их *К. Каратеодйри (1873 — 1980) немецкий математик. 105 3.1. Выпуклые множества количество превышает размерность линейного пространства. Следовательно, верно равенство ги ,'г р (жг — ш') = 0 г.=.2 (3.3) ги и 1г!гв! = О, ~! 12! = О. (ЗА) г=! Поскольку сумма всех коэффициентов рг равна нулю, а среди них есть коэффициенты, отличные от нуля., то р„, > 0 хотя бы для одного номера 1.
Введем параметр а Е К и с учетом равенств !3.4) запишем т т т т ш = ~ Л,т' = ~~ Л,ж' — о~~ !2,ж' = ~(Л, — а!2,)ж'. 13.5) г=1 г=1 г=-1 г=-1 При этом и и и (Лг — о!2,) = ~~ Л, — с!~~ р, =1 — 0=1. г=1 г=1 г=! Подберем такое значение параметра а, при котором линейная комбинация с коэффициентами Л; — 11р, будет выпуклой, а хотя бы один из коэффициентов будет равен нулю. Для этого достаточно выбрать а равным наименьшему отношения> Л,1111; среди тех, для которых р! > О. Обозначим номер выбранного отношения через аз т.е. полагаем сг = Ла,1!гы Тогда Л; — 1111.; > О, 1 = 1, пь Действительно, если для фиксированного номера ! имеем 1гг ~ (О, то !псле Л; — с1Р; положительно как разность положительного и неположительного чисел.