Доказать что множество выпукло

1.6. Выпуклые множества на плоскости и в пространстве.

Определение 1. Множество А R n называется выпуклым, если с любыми своими двумя точками А оно содержит целиком отрезоких соединяющий:

А А. (1)

Пусть два вектора на плоскостих О у и пусть точка лежит на отрезке. Тогда векторколинеарен вектору, направлен в одну сторону с ним и не превосходит его по длине. Эти условия могут быть записаны в виде равенства:

, (2)

где

Векторное равенство (2) равносильно системе:

(3)

Система (3) может быть преобразована в равносильную систему:

(4)

где ОбозначимТогда (4) примет вид:

(5)

В векторном виде система (5) примет вид:

где (6)

Определение 2. Выпуклой (линейной) комбинацией векторов называется выражение вида:

где все и

Равенство (6) показывает, что каждая точка отрезкаявляется выпуклой комбинацией векторов

Теорема 1. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Доказательство. Пусть — любое семейство выпуклых множеств. ПустьА – их пересечение:

Покажем, что множество А – выпукло. Пусть Тогдадля каждого, посколькуА – пересечение всех . Так как— выпукло, то вместе с точкамионо содержит и соединяющий их отрезок:

для всех А_i.

Но, отсюда, очевидно, следует, что каждая точка отрезка (а значит и сам отрезок) принадлежит пересечению множеств, то есть множествуА. Итак, А – выпуклое множество. Что и требовалось доказать.

Определение 3. Выпуклой оболочкой множества называется такое выпуклое множество, что:

,

— выпукло .

Лемма 1. Выпуклая оболочка множества А совпадает с пересечением всех выпуклых множеств, содержащих А.

Доказательство. Пусть В₀ – пересечение всех выпуклых множеств, содержащих А. Тогда очевидно В₀, содержит А. С другой стороны по теореме 1 множество В₀ само выпукло. Отсюда следует, что В₀= VA, поскольку выполнены свойства 1) и 2).

Лемма 2. Отрезок является выпуклой оболочкой своих концов.

Доказательство. Пусть , то есть множествоА состоит из двух элементов . Отрезокявляется выпуклым множеством и содержитА. С другой стороны каждое выпуклое множество В, содержащее А, содержит по определению выпуклости и весь отрезок . Тем самым показано, чточ т.д.

Лемма 3. Если выпуклое множество содержит векторы, то оно содержит и любую их выпуклую комбинацию:

где

Доказательство. Докажем это по индукции. Для двух точек утверждение леммы практически было доказано выше, поскольку множество выпуклых комбинацийсовпадает с отрезкоми, следовательно, содержится вВ. Пусть утверждение справедливо для всех . Покажем, что оно будет также справедливым и для.

Пусть где

и .

где По предположению индукцииТак какито. Лемма доказана.

Теорема 2. Выпуклая оболочка VA множества АR n совпадает с множеством всех выпуклых комбинаций, состоящих из конечного числа векторов множества А.

Доказательство: Пусть В₀ – множество всех таких комбинаций векторов множества А. Как следует из леммы 3 множество В₀ содержится в любом выпуклом множестве В, содержащем А. Осталось показать, что само В₀ – выпукло.

Пусть— два вектора множества В₀. Тогда ,,,.

Пусть — гдеиДостаточно показать, что, то есть что векторсам является выпуклой комбинацией векторов изА_0. Но это верно, поскольку:

— выпуклая комбинация векторов — так какич.т.д.

Отметим, что треугольник и пирамида являются выпуклыми оболочками своих вершин, и, следовательно, каждая их точка является выпуклой комбинацией векторов-вершин.

Определение. Выпуклая оболочка точки в— мерном линейном пространственазывается симплексом.

Предполагается, что точки лежат в общем положении, то есть не содержатся ни в какой гиперплоскости.

Рассмотрим некоторую точку Возможны следующие случаи расположения точкиотносительно множества В.

Первый случай. На каждой прямой l , проходящей через , можно найти отрезок, лежащий целиком вВ и содержащий внутри себя:

. (7)

Второй случай. Существует содержащая прямая, на которой не существует отрезка, удовлетворяющего (7).

Если то ясно, что свойством (7) не обладает ни один отрезок. Если для некоторых прямых проходящих через точкуотрезок удовлетворяющий (7), существует, а для других прямых нет, тоназывается граничной точкой множестваВ. Вблизи граничной точки лежат как точки множества В, так и точки ему не принадлежащие.

Третий случай.

Определение. Пусть точка и ни для одной прямойl содержащей , не существует отрезка, удовлетворяющего (7). В этом случаеназывается угловой точкой множества В.

Другими словами любой отрезок, содержащий угловую точку внутри себя, обязательно «высовывается» из множестваВ.

Условие 2) Из (7) можно заменить в предыдущих рассуждениях на условие: , — то есть можно считать, без ограничения общности, что точкаявляется серединой отрезка, действительно, если существует отрезок, содержащийвнутри себя, то существует в нем меньший отрезок, для которого точкаявляется серединой.

Определение. Множество называется замкнутым, если оно содержит все свои граничные точки.

Значение угловых точек для описания выпуклого множества в дает следующая теорема, которую мы приводим без доказательства.

Теорема 3. Замкнутое выпуклое множество является выпуклой оболочкой своих угловых точек.

Доказать что множество выпукло

Задачи Выпуклый анализ (примеры)

Пример 1. Доказать выпуклость множества .

Пусть , т. е. , . Тогда для любого имеем

. Следовательно, , , т. е. множество X выпукло.

Пример 2. Найти минимальное число A, при котором множество выпукло.

Как видно из рис. , при A= -31/27 множество X будет выпукло.

Пример 3. Доказать, что множество является выпуклым конусом. Изобразить этот конус.

Очевидно, что множество X — конус. Докажем, что X выпуклый конус. Действительно, для любых имеем (неравенство Коши-Буняковского и неравенство между средним арифметическим и средним геометрическим).

Т. е. . Таким образом, X — выпуклый конус.

Сечением конуса плоскостью является круг . Если , то получаем конус .

Пример 4. Записать уравнение гиперплоскости, отделяющей точку от множества , которое задается системой уравнений

Очевидно, что среди неравенств, задающих множество X, третье неравенство в точке не выполняется. Поэтому в качестве разделяющей (не строго) гиперплоскости можно взять гиперплоскость .

Пример 5. Записать уравнение гиперплоскости, опорной к множеству

Функция является строго выпуклой, т. к. матрица вторых производных , а, значит, множество X выпукло. Тогда опорной гиперплоскостью к множеству X в точке Является, очевидно, касательная плоскость к границе множества X в точке , т. е. . Имеем и .

Пример 6. Записать уравнение гиперплоскости, разделяющей выпуклые множества , .

Ясно, что множества и пересекаются (касаются) в единственной точке . Поэтому разделяющей гиперплоскостью будет касательная прямая к графику функции в точке , т. е. прямая .

линейная-алгебра — Доказать, что множество выпуклое

Доказать, что множество, задаваемое системой, является выпуклым.

задан 9 Апр ’15 0:22

Это следует из того, что пересечение выпуклых множеств выпукло. В первом условии — внутренняя часть эллипса. Во втором — угол (открытый). В третьем — неравенство имеет вид $%xy\ge2$%. Это две внутренние части гиперболы, они тоже выпуклые.

@falcao а как это можно строго доказать?

@Intense: какой именно из фактов Вас интересует? Дело в том, что здесь всё достаточно стандартно, и на что-то, наверное, можно сослаться. Скажем, выпуклость полуплоскости или круга, а также внутренности эллипса — это факты общеизвестные. Для случая гиперболы, наверное, аналитическое доказательство можно было бы привести.

@falcao хотелось бы узнать, как аналитически/строго доказывается, что целиком это множество выпуклое

@Intense: целиком это не надо доказывать! Дело в том, что множеством решений системы является пересечение трёх множеств, а пересечение выпуклых множеств выпукло, что сразу следует из определения. Поэтому выпуклость достаточно установить для каждой из фигур в отдельности, что намного проще.

@falcao я нашел, что если взять две точки $%x_1$% и $%x_2$% из этого множества, то отрезок будет $%x = \alpha x_1+(1-\alpha)x_2; \alpha = [0;1]$%, но я не понимаю как проверить, что если подставить это в условие, неравенства будут верными, т.е выполняться

@Intense: я понимаю, что Вы хотите доказать, и это можно обсудить, но только на примере гиперболы. Для круга это геометрически очевидно, а эллипс получается сжатием, для которого отрезки переходят в отрезки, и свойство выпуклости сохраняется.

@falcao хорошо, может быть, вы тогда подскажете, как подставлять то, что я писал выше в нер-во $%Re(z)*Im(z) \geq 2$%, чтобы доказать, что оно выполняется?

1 ответ

Из первого условия следует, что все рассматриваемые $%z$% принадлежат правой полуплоскости, то есть $%x > 0$%. Докажем, что множество $%M=\<(x,y)\mid xy\ge2, x > 0\>$% выпукло.

Рассмотрим две точки $%(x_i,y_i)$% из $%M$%. Составим их выпуклую линейную комбинацию. Тогда $%xy=(\alpha x_1+(1-\alpha)x_2)(\alpha y_1+(1-\alpha)y_2)\ge(\alpha x_1+(1-\alpha)x_2)(2\alpha/x_1+2(1-\alpha)x_2)$%, что равно $%2\alpha^2+2(1-\alpha)^2+2\alpha(1-\alpha)(x_1/x_2+x_2/x_1)\ge2(\alpha^2+(1-\alpha)^2+2\alpha(1-\alpha))=2$% с учётом неравенства о среднем.

Выпуклые множества и выпуклые функции

Для дальнейшего изучения норм и неравенств нам нужен целый ряд фактов и построений геометрического характера, связанных с понятием выпуклости.

Пусть V — произвольное линейное пространство над полем вещественных чисел. Геометрические построения обычно используют точки, прямые, отрезки и т. д.

В этой связи будем считать, что точки отождествляются с векторами — при этом точка, определенная нулевым вектором, не имеет какого-либо особого геометрического смысла. Каждая упорядоченная пара точек а, Ъ естественным образом определяет вектор Ь — а.

Если L — линейное подпространство пространства V и а — точка пространства V, то множество А = а + L называется плоскостью, проходящей через точку а. Подпространство L называется направляющим подпространством данной плоскости. Легко видеть, что L совпадает с множеством разностей векторов, принадлежащих А, и поэтому определяется по А однозначно. Под размерностью плоскости понимается размерность ее направляющего подпространства.

Утверждение 6.5.1. Пересечение произвольного числа плоскостей является либо пустым множеством, либо плоскостью, для которой направляющее подпространство есть пересечение направляющих подпространств заданных плоскостей.

Пусть М — произвольное непустое множество точек. Пересечение всех плоскостей, содержащих М, называется аффинной оболочкой множества М и является наименьшей плоскостью, в которую вложено множество М. Линейная комбинация векторов называется аффинной или барицентрической комбинацией, если все ее коэффициенты вещественны и их сумма равна 1.

Утверждение 6.5.2. Аффинная оболочка множества М совпадает с множеством всевозможных барицентрических комбинаций конечных систем векторов, принадлежащих множеству М.

Доказательство. Пусть А — аффинная оболочка множества АГ. Если а. а_п G М, то А можно представить в виде А = = а + L, где L — направляющее подпространство плоскости А.

lim = а, О, 1 г оо 1 1

Нам нужно доказать, что а Е К_п. Предположим, что для какого-то i координатная последовательность при к оо не стремится к бесконечности и, значит, обладает ограниченной подпоследовательностью. Для определенности пусть г = п. Тогда можно выделить сходящуюся подпоследовательность а_п а_п и имеет место равенство lim У’ ot^ai = а — а_па_п. Очевидно, 1^00 2—1

а_п 0 и, по индуктивному предположению, а — а_па_п Е К_п— => => а Е К_п. Теперь рассмотрим случай, когда каждая координатная последовательность стремится к бесконечности. Тогда

По индуктивному предположению, — aj е K_n-i Q Кп- Таким образом, для каждого j оба вектора aj и — aj принадлежат К_п => множество К_п является конечномерным подпространством и поэтому замкнуто. ?

Вещественная функция /(ж), определенная на выпуклом множестве М, называется выпуклой, если для любых точек a, b е М и любой их выпуклой комбинации выполняется неравенство

/(сш + /ЗЬ) a/(a) + /3f(b), а, (3^0, а+ /3 = 1.

Из определения вытекает, что для любых точек а. а_п е V и любой их выпуклой комбинации выполняется неравенство

a 1. ,а_п О, сц = 1.

Функция /(ж) называется вогнутой, если функция ф(х) := •= —f(x) выпукла.

Утверждение 6.5.5. Пусть М С IR — выпуклое множество, вещественная функция f(x) дважды дифференцируема в любой его точке и вторая производная неотрицательна, т. е. f»(x) 0 для всех х G М. Тогда функция ф(х) выпукла на

множестве jI.

Доказательство. Пусть a,b е М и а 1 f /W

Утверждение 6.5.6. Пусть М — выпуклое тело в нормированном пространстве и а — его внутренняя точка. Точка b является граничной для М в том и только том случае, когда а. + t(b — а) Е М при 0 t 1.

Доказательство. Если с G Л/, то все точки отрезка [а, с] будут внутренними, кроме, возможно, точки с: для некоторого г > 0 имеется шар W := В (а, г) С М и отсюда легко вывести, что для любой внутренней точки d отрезка [а, с] выпуклая оболочка множества <с>U И 7 будет содержать шар с центром в точке d, целиком принадлежащий М. Если b — граничная точка для М, то найдется последовательность b_n е М, сходящаяся к Ь. Если с = о. + t(b — а) 6 М при каком-то t > 1, то точка b будет внутренней для отрезка [а, с], а значит и внутренней для множества М. Далее, взяв точку с = а + t(b — а) при 0 7 . ?

В заключение заметим, что понятие выпуклого множества имеет смысл и в комплексных линейных пространствах. Так, нетрудно показать, что единичный замкнутый шар В в любом нормированном пространстве является ограниченным замкнутым выпуклым телом с внутренней точкой 0 и следующим свойством симметрии: если х Е В, то ах Е В для всех чисел а, таких что |а| 1 (в комплексном случае а Е С). Более того, можно

доказать, что любое множество В с перечисленными выше свойствами является единичным шаром для нормы, которая задается следующим функционалом Минковского:

f(x) := inf |а > 0: — х Е

Задача 255. Докажите, что угловыми точками множества двоякостохастических матриц порядка п являются матрицы перестановки и только они. Что представляют собой граничные точки этого множества?

Задача 256. Докажите, что множество всех внутренних точек выпуклого тела и замыкание любого выпуклого множества являются выпуклыми множествами.

Задача 257. Пусть М — выпуклое множество, обладающее внутренней точкой, и М — его замыкание. Докажите, что ни одна точка множества М jI не является внутренней точкой множества М.

Задача 258. Пусть V — нормированное пространство и В — замкнутое ограниченное выпуклое тело, для которого нуль является внутренней точкой и вместе с любой точкой х G В множество В содержит все точки вида ах при |а| 1.

Докажите, то функционал Минковского задает некоторую, возможно другую, норму на пространстве V, для которой множество В является единичным шаром.

Задача 259. В гильбертовом пространстве рассматривается «гильбертов кирпич» — множество вида

М := |(a?i,Х2. .) 6 Z2W : l^fcl Г’ А; = 1,2, L Л/ J

Докажите, что множество М выпукло, замыкание его аффинной оболочки совпадает с /2ОЮ и в то же время jI не имеет ни одной внутренней точки.