Множество точек называется выпуклым если. Свойства выпуклых множеств

Примеры выпуклых множеств

1. E n .

2. Пустое множество.

3. Множество, состоящее из одной точки

,

где
.

4. Гиперплоскость

где
, a ≠ 0, иb – число. Приn = 3 это множество совпадает с обычной плоскостью, а приn = 2 – с прямой.

5. Полупространство

где
, a ≠ 0, иb – число.

6. Конус

а y (k) – заданные векторы
. Заметим, что часто рассматриваются конусы с вершиной не в нуле, а в какой-либо другой точке
, то есть множества типа

7. Выпуклая комбинация (оболочка) конечного числа точек

Такое множество геометрически представляет собой n -мерный выпуклый многогранник.

8. Пересечение конечного числа полупространств

где
. Такое множество называется многогранным выпуклым множеством. В том случае, когда оно ограничено, оно также является выпуклым многогранником. Таким образом, возможны два представления выпуклого многогранника – в виде выпуклой оболочки конечной совокупности точек и в виде пересечения конечного числа полупространств, заданных неравенствами.

9. Шар радиуса r ≥0 с центром в

.

В качестве примеров невыпуклых множеств можно назвать множество целых чисел или множество рациональных чисел.

2.1.2. Свойства выпуклых множеств

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

Объединение двух выпуклых множеств не обязательно выпукло.

Пример: объединение двух точек не есть выпуклое множество.

также является выпуклым множеством.

Эти утверждения следуют из определения выпуклого множества. Докажем, например, первое утверждение для пересечения двух множеств
и
. Пусть. Рассмотрим

Из выпуклости A иB получаем, что
и
при всех
. Отсюда
. Утверждение доказано.

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

В качестве примера приведем выпуклый многогранник. Его крайними точками являются его вершины.

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

Примером строго выпуклого множества является замкнутый шар.

2.1.3. Опорная гиперплоскость

Рассмотрим важнейшее понятие опорной гиперплоскости . Прежде всего заметим, что любая гиперплоскость , где
, a ≠ 0, определяет в пространстве
два замкнутых полупространства

Гиперплоскость является пересечением этих полупространств и одновременно границей каждого из них.

Пусть имеется некоторое выпуклое множество S и его граничная точкаy .

Определение . ГиперплоскостьH , проходящая через точкуy и содержащая все точки множествоS в одном из определяемых ею замкнутых полупространств, называется гиперплоскостью,опорной к множествуS в точкеy .

Можно показать, что опорную гиперплоскость можно провести через любую граничную точку выпуклого множества. Иллюстрация опорной гиперплоскости приведена на рис. 3.1.

Рис. 3.1. Опорная гиперплоскость H к выпуклому множеству S в точке y .

Отметим, что опорная гиперплоскость может быть не единственна (см. рис. 3.2).

Рис. 3.2. Две опорных гиперплоскости H 1 и H 2 к выпуклому множеству S в точке y .

Пусть теперь задано два непустых множества A иB . ГиперплоскостьH называетсяразделяющей гиперплоскостью, если все точки множестваA лежат в одном из замкнутых полупространств, определяемых гиперплоскостьюH , а все точки множестваB лежат в другом из определяемых ею замкнутых полупространств. Можно доказать несколько теорем о разделяющих гиперплоскостях. Рассмотрим простейшую из них. Пусть
– совокупность внутренних точек множестваA .

Теорема 3.1. ПустьA иB – два непустых выпуклых множества, причем
Ø. Тогда существует гиперплоскостьH , разделяющая множестваA иB. 1

Примеры разделяющих гиперплоскостей приведены на рис. 3.3 и 3.4.

Рис. 3.3. Гиперплоскость H разделяет множества S 1 и S 2 , не имеющие общую точку

Рис. 3.4. Гиперплоскость H разделяет множества S 1 и S 2 , имеющие общую точку

Выпуклые и вогнутые функции

Задача линейного программирования - это нахождение минимума линейной функции f: n > 1 , заданной на некотором замкнутом выпуклом множестве, выделенном линейными неравенствами.

Общая задача линейного программирования имеет вид:

Дана система m линейных уравнений и неравенств с n переменными

и линейная функция F = c 1 x 1 + c 2 x 2 +… + c n x n min (max)

Система (1) называется системой ограничений, а функция F - линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

x={x|Axb, A=, b=( T )}

Задачу линейного программирования записывают и в других формах - канонической и нормальной. Канонической задачей - обозначение Зк, назовем такую:

x={x|Axb, ?0, j=)}

Нормальной задачей - обозначение Зн, назовем такую

x={x|Axb, ?0, j=)}

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

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

На следующем рисунке изображены два множества на плоскости: одно выпуклое, а другое нет.

Рис. 1

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

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.

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

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

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

На рис. приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка N) и угловых (точки А, В, С, D, Е). Точка А - угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка АР, она не является внутренней; точка А - внутренняя для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.

Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), в то же время для невыпуклого множества это не обязательно. Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограниченным , если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным. Выпуклое замкнутое множество точек плоскости, имеющее конечное число угловых точек, называется выпуклым многоугольником, если оно ограниченное, и выпуклой многоугольной областью, если оно неограниченное.

Функция f: называется выпуклой, если ее надграфик epi f= является выпуклым множеством. На рисунке изображена выпуклая функция, её график выделен синим и надграфик закрашен зеленым.

Функция f: называется замкнутой, если ее надграфик - замкнутое множество.

Геометрический смысл решений неравенств, уравнений и их систем

Рассмотрим решения неравенств.

Утверждение 1. Множество решений неравенства с двумя переменными a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1, включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства a11x1+a12x2>=b1.

Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не лежащую на ее границе - построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется и во всех точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке, оно не выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости. В качестве контрольной точки удобно взять начало координат О (0; 0), не лежащее на построенной прямой.

Рассмотрим множество решений систем неравенств.

Утверждение 2. Множество решений совместной системы т линейных неравенств с двумя переменными является выпуклым многоугольником (или выпуклой многоугольной областью).

Каждое из неравенств в соответствии с утверждением 1 определяет одну из полуплоскостей, являющуюся выпуклым множеством точек. Множеством решений совместной системы линейных неравенств служат точки, которые принадлежат полуплоскостям решений всех неравенств, т.е. принадлежат их пересечению. Согласно утверждению о пересечении выпуклых множеств это множество является выпуклым и содержит конечное число угловых точек, т.е. является выпуклым многоугольником (выпуклой многоугольной областью).

Координаты угловых точек - вершин многоугольника находят как координаты точек пересечения соответствующих прямых.

При построении областей решений систем неравенств могут встретиться и другие случаи: множество решений - выпуклая многоугольная область (рис. а); одна точка (рис. б); пустое множество, когда система неравенств несовместна (рис. в).

Определение понятия двойственности с помощью преобразования Лежандра

Пусть f:. Функция f*: определенная равенством f*(x*)==(x*), называется сопряженной функцией к f, а функция f**: определенная по правилу f**(x*)==(x*), называется второй сопряженной функцией к f.

Отображение f* (x*) =< x*, x> ? f(x) называется преобразованием Лежандра.

Обычный прием построения двойственной задачи состоит в следующем. Задача минимизации

где X - линейное пространство, включается в класс подобных ей задач, зависящих от параметра:

где Y - некоторое другое линейное пространство, F (x, 0)=f(x) (функцию F называют возмущением f). Обычно F предполагается выпуклой. Двойственной к задаче по отношению к данному возмущению наз. задача

где F* - функция, двойственная (сопряженная) с F в смысле Лежандра - Юнга - Фенхеля. Такая двойственность позволяет связать с каждой выпуклой функцией f: X-> R двойственный объект - сопряженную функцию, заданную на сопряженном пространстве X* и определяемую формулой

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

где X - линейное пространство, выпуклые функции на X, В-выпуклое множество в X (частными случаями (3) являются задачи линейного программирования), обычно применяются следующие стандартные возмущения, зависящие от параметров y=(у 1 ,…, y m), m, Теоремы двойственности для общих классов задач выпуклого программирования утверждают, что при некоторых допущениях на возмущение F значения задач (2) и (2*) совпадают, и более того, решение одной из задач является множителем Лагранжа для другой.

Множество AÌE называется выпуклым, если оно вместе с любыми двумя точками x 1 и x 2 содержит отрезок, соединяющий их, т.е. множества вида

[x 1 x 2 ]={x ÎE n | x =lx 1 +(1-l)x 2 , 0 £l £1}.

Рассмотренные выше полупространства являются выпуклыми множествами. Проверим, например, выпукло ли полупространство Н + ab {x ÎE n | ³b}. Для этого рассмотрим две произвольные точки x 1 и x 2 этого полупространства. Для этих точек выполнены неравенства

x 1 >³ b, x 2 >³ b.

Сложим эти два неравенства, предварительно умножив первое на произвольное число lÎ, а второе на 1-l. В результате получим неравенство

lx 1 > + (1-l) x 2 > = x 1 + (1-l)x 2 >³ b.

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

Рис.2.10.выпуклое(а), невыпуклое(б) множества.

Глава 3.Основные сведения о функциях .

3.1 Понятие функций .

Пусть X и Y два множества. Если указано правило, согласно которому каждому элементу множества X поставлен в соответствие определенный элемент множества Y, то говорят, что задана функция f , отображающая X в Y. Этот факт записывают в виде f: X®Y или y=f(x) , где x ÎX, yÎY. Множество X называется областью данных или областью определения функции, а множество Y- множество значений. Функция f(x) представляет собой правило, которое позволяет каждому значению x поставить в соответствие единственное значение y=f(x) . В этом случае x- независимая переменная, y- зависимая переменная. Функции y=f(x)=f(x 1 +x 2 ,..,x n), т.е. функции с областью задания X Ì E n и множеством значений Y Ì E называют числовыми функциями в отличие от векторных функций, для которых YÌ E m , m>1.

Множество вида

{(x,y)ÎE n +1 ½ y=f(x) при некоторых xÎX}

называют графиком функции y=f(x) .

Ряд физических процессов можно описать с помощью непрерывных функций, т.е. функций, которые обладают свойством непрерывности в каждой точке x, принадлежащей областям их определения.

Функцию f называют непрерывной в точке x 0 ÎX, если для любого числа e>0 можно указать такое число d e >0, что для всех xÎX Ç Ède ½x 0 ½ выполняется неравенство ½f(x)-f(x 0)½

В качестве примеров функций, непрерывных на E n , приведем линейную функцию f 1 (x)=+b=c 1 x 1 +c 2 x 2 +..+c n x n +b и квадратичную функцию f 2 (x)=1/2++b,

где Q- числовая симметрическая матрица размера n*m, с- некоторый вектор из E n и b- некоторое число, а Qx означает произведение матрицы на вектор по правилам перемножения матриц, принятых в линейной алгебре.

3.2 Классификация функций.

3.2.1 Разрывные и дискретные функции.

В инженерных приложениях нередки случаи, когда приходится использовать

разрывные функции. Например, затраты на сообщение некоторой системе количества

тепла при различных температурах системы получаем кусочно- непрерывную кривую (рис 3.1). возможны случаи, когда переменная принимает дискретные значения(рис 3.2).

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

Функции можно также классифицировать в соответствии с их формой, определяющей топологические свойства функций в рассматриваемом интервале.

3.2.2 Монотонные функции.

Функция f(x) является монотонной (рис 3.3) как при возрастании, так и убывании), если для двух произвольных точек x 1 и x 2 , таких, что x 1 f(x 1)£ f(x 2) (монотонно возрастающая функция)
f(x 1)³ (x 2) (монотонно убывающая функция)

Рис.3.3. К понятию монотонной функции.

На рис 3.4 изображен график функции, которая монотонно убывает при x£0 и монотонно возрастает при x³0. Функция достигает своего минимума в точке x=x * (начале координат0) и монотонна по обе стороны от точки минимума. Такие функции называются унимодальными. Заметим что унимодальная функция вовсе не должна быть гладкой (рис. 3.4, а) и даже непрерывной (рис.3.4,б), она может быть изломанной (недифференцируемой), разрывной (рис 3.4, в), дискретной (рис. 3.4 г) и даже может в некоторых интервалах не быть определенной (рис. 3.4, д.).

Итак функция f(x) называется унимодальной на отрезке , если она непрерывна на и существуют числа a и b a£a£b£b, такие, что:

1) если a

2) если b

3) при xÎ f(x)=f * =min f(x);