Ф.П. Васильев - Методы оптимизации (1125241), страница 43
Текст из файла (страница 43)
Доказать, что тогда совместна одна и только одна иэ систем: 6 1. ВЫПУКЛЫЕ МНОЖЕСТВА 149 ГЛАВА 4 Элементы выпуклого анализа 9 1. Выпуклые множества Прежде чем переходить к изложению численных методов решения задач, более сложных, чем задачи линейного программирования, остановимся на элементах выпуклого анализа— области математики, в которой изучаются свойства выпуклых множеств и выпуклых функций, и которая играет фундаментальную раль в теории и методах решения экстремальных задач [5; 14; 151 34; 48; 49; 54; 61; 83; 84; 106; !33; 186; 191; 204; 209; 225; 233; 264; 265; 278; 286; 295; 297; 314; 3!5; 358; 364; 366; 374; 446; 449; 471; 472; 499; 5111 543; 584; 587; 603-605; 613; 6!7; 636; 670; 683; 689; 735; 747; 767; 774; 785; 795; 798; 8141.
1. Начнем с рассмотрения конкретных примеров выпуклых множеств. Сначала напомним Определение 1. Множество Х называется выпуклым, если для любых и, е е Х точка и = и+ а(и — е) = аи+(1 — а)е принадлежит Х при всех а, 0 < а ( 1. Иначе говоря, множество Х выпук- — < ло, если отрезок [е, и) = — (и,: и = па(и — е), О < а 1), соединяющий любые две точкй и, е из Х целиком лежит в Х (рис. 4.1). Все пространство Е", очевидно, образует выпуклое множество. Пустое множество и множество, состоя- Рис.
4.1 щее из одной точки, удобно считать выпуклыми, Тогда из определения 1 непосредственно следует, что пересечение любого числа выпуклых множеств является выпуклым множеством. Приведем другие примеры выпуклых множеств. Пример 1. Шар Я(ео, В) = (и; и Е Е", [и — ео) < В) (1) радиуса В > 0 с центром в точке и является выпуклым множеством. В самом деле, если и, е е 8(и, В), то, пользуясь неравенством треугольника, имеем [аи + (1 — а)е — е [ = [а(и — и ) + (1 — а )(е — и )[ < < а[и — и [+(1 — а)[е — е [< аВ+(1 — ст)В =В, т. е. и = аи+(1 — а)ее Е(ео, В) для всех а е[0, 1). ь ч П р и м е р 2. Напомним, что гиаерплоскостыо в Е называется множество Г=Г(с, Т) =(и: июЕ, (с, и) = у), (2) где с = (с„ ..., с„) ф 0 в вектор из Е", Т вЂ” действительное число.
Это множество всегда непусто; если, например, с,. ~ О, то точка ио с координатами и' = .у/с>,иа =0 (7' = [,...,п, у' ф з) удовлетворяет равенству (с,и ) = Т, т. е, Ь! ' ;(т ' :, 4., м1, е е Г. Если е — какая-либо точка из Г, т. е. (с, и ) = Т, то гиперплоскость Г можно представить в виде Г = Г(с, и ) = (и: и й Е", (с, и — и ) = О). Напоминаем, что два вектора а, Ь й Е" называются ортогональными, если (а, Ь) =О. Предыдущее представление для Г означает, что гиперплоскость состоит из тех и только тех точек и, для которых вектор и — и ортогонален вектору с. Вектор с называют нормальным вектором гиперплоскости Г. Возьмем произвольные точки и, е е Г, т. е, (с, и) = (с, е) = у. Тогда (с, аи+ + (1 — а)е) = а(с, и) + (1 — а)(с, е) = у при всех а й [О, 1).
Следовательно, à — выпуклое множество. П р и м е р 3. Пусть Г = (и: (с, и) = 7) — некоторая гиперплоскость, Тогда множества Г" = [и; (с,и) ) у), Г =(и; (с,и) < у) называются открььтыми полупространствами, а множества Г =(и:(с,и)~ у), Г =(и:(с,и)(Т) называются замкнутыми полупространствами. Нетрудно видеть, что Г+, Г, Г, à — выпуклые множества. Например, если и, е ~ Г", то (с, аи+ +(1 — а)е) = а(с, и)+(1 — а)(с, е) ) аТ+(1 — а) у = у для всех сг й[0, Ц. Пример 4.
Прямая и луч в Е" (см. определение в $2.1) — выпуклые множества. Пример 5. Важным примером выпуклого множества являются аффинные множества (или линейные многообразия). Определение 2. Множество М из Е' называется аффинг!ым, если аи+(1 — а)е 6 М при всех и, ее М, а я[к, т. е. прямая, проходящая через любые две точки и, е е М, целиком лежит в М. Все пространство Е" является аффинным множеством. Пустое множество и множество, состоящее из одной точки, удобно считать аффинными. Любое подпространство пространства Е" представляет собой аффинное множество.
Множество М = Х + е, получаемое сдвигом подпространства Х на произвольный фиксированныи вектор и, также является аффинным. Верно и обратное: всякое аффинное множество М может быть получено сдвигом некоторого подпространства Х на некоторый вектор е . В самом деле, возьмем произвольную точку е Е М и положим Х = М вЂ” е, Ясно, что Х вЂ” аффинное множество, причем 06 Х„Тогда для каждого и е Х имеем аи = аи + (1 — а) 0 е Х при всех а Е К. Кроме того, если и, е е Х,, то (— и + е)/2 = и/2 + (1 — 1/2) е Е Х и, следовательно, и + е = 2((и + е)/2) й Х .
аким образом, сумма двух векторов из Х и произведение вектора из Х, на любое число принадлежат Х, т. е. Х, — подпространство. Убедимся, что подпространство Х = М вЂ” и не зависит от выбора точки ео е М. В самом деле, пусть Х,! = М вЂ” и„где и, е М.
Возьмем любую точку и Е Х . Поскольку и, — е й Х, то и+ (и, — е ) й Х и, следовательно, и й Х— — (и, — и ) =(Х + и ) — и, = М вЂ” и = Х,. Это значит, что Х с. Х !, Обратное включение Х ! С Х, доказывается совершенно так же. Следовательно, Х, ! = Х,. Таким образом, всякое аффинное множество М из Е" представимо в виде М=Х, +ее, (3) где Х вЂ” подпространство, однозначно определяемое множеством М, ив произвольная точка из М, Подпространство из этого представления называют параллельным аффинному множеству М.
$ Е ВЫПУКЛЫЕ МНОЖЕСТВА 151 Г50 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Опираясь на полученное представление (3), можно дать алгебраическое описание аффинных множеств на Е". Поскольку всякое подпространство Ь из Е представимо в виде Ь =(и ЕЕ": Аи=О)=(и ЕЕ": (а!, и)=0, 4= = 1,..., тп), где А — некоторая матрица размера гп х п, а! — 4-я строка матрицы А (например, в качестве векторов а„4 = 1,..., тп, можно взять базис ортогонального дополнения к Ь в Е"). Отсюда и из (3) следует, что всякое аффинное множество из Е может быть задано в виде М=(и ЕЕ": Аи =О) + из= (и Е Е": и= из+и, Аи =О) = = (и Е Е: А(и — из) = О) = (и Е .Е': Аи = Ь) = = (и Е Е"! (а!, и) = Ь!, 4 = 1,..., гп), (4) где Ь = А и =(Ь',..., Ь ).
Нетрудно проверить, что верно и обратное: всякое множество вида (4) является аффинным. В самом деле, если и, и е М, т, е. Аи = Ь, Аи = Ь, то А(аи+(1 — а)и) = с!Аи+(1 — а)Аи = Ь или, иначе, аи+ (1 — с!)и Е М при всех а е И. Таким образом, множества вида (4) и только они являются аффинными.
Согласно теореме Кронекера — Капелли 1192; 351; 353] множество (4) непусто тогда и только тогда, когда матрица А и расширенная матрица В = (А, Ь) имеют один и тот же ранг. Если гапйА < гапдВ (например, А =О, Ь ~0), то М=!о. Если А =О, Ь =О, то М= Е". Рассмотрим случай А ~ О, гапйА = гапйВ = т. Тогда множество (4) состоит из тех и только тех точек, которые представимы в виде [192; 351; 353) и =и + 2,' г,.и!, (5) а=! где 'и — какое-либо частное решение неоднородной системы линейных алгебраических уравнений Аи = Ь, а и„ ...,и„ „ — линейно независимые решения однородной'системы Аи = 0; г„ ..., г ,, — действительные числа. Векторы и„ ...,и„ , образуют базис подпространства Ь = (и Е Е": А и = О) = ( и Е Е: и = ~,' 1! и!, Ф! Е И), !=! так что йш Ь вЂ” размерность Ь и равна и — т.
С помощью введенного подпространства Ь равенство (5) можно переписать в виде М = из + Ь вЂ” мы снова пришли к представлению (3). Размерность аффинного множества М по определению принимается равной размерности подпространства Ь, параллельного М. Таким образом, размерность йш М аффинного множества (4) равна и — г, где т = гапйА = = гапдВ. Аффинное множество размерности р часто называют гиперплоскостью размерности р. В частности, если в (4), (5) т = и, то Ь = (0) и М =(и ) состоят из одной точки и йшЬ = йш М =О.
Если т = и — 1, то М, = (и Е Е": и = и + Фи„л Е И) — прямая (см. пример 4). Далее, гиперплоскость (2) также является аффинным множеством: в этом случае в (4) нужно принять А = с, Ь = у. Поскольку с ~ О, то гапяА = гапд(А, Ь) = 1 и, следовательно, гиперплоскость имеет размерность п — 1. Согласно (5) тол- ! гда Г = М„, = (и Е Е"! и = из+ 2 1!и!, 1! Е И)„где и„..., и„, — базис (= ! параллельного подпространства Ь, = (и е Е"; (с, и) =О). Как видим, вектор с ортогонален к Ь„ , и является базисом ортогонального дополнения к Ь„ , до Е", а векторы и„ ...,и „ с образуют базис в Е".
Заметим, что пересечение любого числа аффинных множеств само является аффинным множеством и, следовательно, представимо в виде (4). О п р е д е л е н и е 3. Пересечение всех аффинных множеств, содержащих множество Х из Е", называется аффинной оболочкой множества Х и обозначается через ай Х; подпространство Ь, параллельное ай Х, называется несущим подпространством множества Х и обозначается через 1.!п Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
