Line segment

Suppose are two points in . Then the line segment between them is defined as follows:

center

Convex set

The set is called convex if for any from the line segment between them also lies in , i.e.

Examples:

  • Any affine set
  • Ray
  • Line segment

center

center

Related definitions

Convex combination

Пусть , тогда точка называется выпуклой комбинацией точек при условии

Convex hull

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

  • Множество является наименьшим выпуклым множеством, содержащим .
  • Множество является выпуклым тогда и только тогда, когда .

Примеры: center

Finding convexity

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

  • By definition
  • Показать, что получено из простых выпуклых множеств с помощью операций, сохраняющих выпуклость:

By definition

Показать, что получено из простых выпуклых множеств с помощью операций, сохраняющих выпуклость:

Линейная комбинация выпуклых множеств выпукла

Пусть есть 2 выпуклых множества , пусть множество

Возьмем две точки из : и докажем, что отрезок между ними так же принадлежит

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

Если искомое пересечение пусто или содержит одну точку - свойство доказано по определению. В противном случае возьмем 2 точки и отрезок между ними. Эти точки должны лежать во всех пересекаемых множествах, а так как все они выпуклы, то и отрезок между ними лежит во всех множествах, а значит и в их пересечении.

Образ выпуклого множества при аффинном отображении выпуклый

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

Отметим так же, что прообраз выпуклого множества при аффинном отображении так же выпуклый.