45

5.Выпуклый анализ.

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

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

Определение 1.

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

То есть если

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

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

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

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

1. - плоскость в . ( - вектор; - координаты).

В :

В общем случае множество ,

- гиперплоскость.

где - скалярное произведение .

- вектор-нормаль к гиперплоскости, - мерный вектор .

- скаляр.

2) - полупространство в .

Примеры в пространстве R².

3) - многогранное множество, где

- матрица размерности ;

- вектор размерности .

В :

1. - выпуклый конус в R².

5) - круг с радиусом и центром .

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

Лемма 1.

(теорема, необходимая для доказательства другой теоремы).

пусть и - выпуклые множества в , тогда выпуклы и следующие множества:

1. - пересечение множеств;

1. - алгебраическая сумма;

1. .

5.2Выпуклые оболочки.

Определение 2.

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

То есть тогда и только тогда, когда она может быть представлена в виде

, , ,

где - положительное целое число,

Примеры:

Замечание:

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

Лемма 2.

Пусть - произвольное множество из . Тогда - наименьшее выпуклое множество, содержащее .

Фактически, является пересечением всех выпуклых множеств, содержащих .

Определение 3.

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

Определение 4.

Если векторы линейно независимы, то выпуклая оболочка называется симплексом с вершинами в точках .

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

5.2.1Отделимость и опорные гиперплоскости.

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

Определение 5.

Совокупность всех точек вида образуют гиперплоскость в ,

где - ненулевой вектор, принадлежащий ;

- скаляр.

Гиперплоскость задает два замкнутых полупространства

и

и два открытых полупространства:

и

Определение 6.

Пусть и - непустые множества в . Гиперплоскость разделяет и , если

и .

Разделения различают:

1. собственная разделимость 

Пример:

1. несобственная разделимость 

Пример:

1. строгая разделимость 

Пример:

1. сильная разделимость 

Пример:

5.3Разделение выпуклого множества и точки.

Теорема:

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

и для

Следствие.

Пусть задано замкнутое выпуклое множество Тогда пересечение всех полупространств, содержащих это множество равно .

Терема Фаркаша.

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

Теорема.

Пусть - матрица размерности , ( - вектор), тогда разрешима только одна из следующих систем:

система 1: ,

система 2:

Если обозначить столбцы матрицы через , то система 2 имеет решение, если принадлежит выпуклому конусу, порожденному векторами .

Графически:

система 2 имеет решение.

Система 1 имеет решение, если замкнутый выпуклый конус и открытое полупространство имеет непустое пересечение.

система 1 имеет решение.

Следствие 1.

Пусть - матрица размерности , ,

тогда разрешима только одна из двух систем:

система 1: ;

система 2: .

Замечание.

Это следует из предыдущей теоремы при замене на .

Следствие 2.

Пусть - матрица размерности ,

- матрица размерности ,

- - мерный вектор ,

тогда разрешима только одна из следующих систем:

система 1: ;

система 2: .

5.4Опорная гиперплоскость к выпуклым множествам.

Пусть - непустое множество в и , где - граница множества, то есть:

, содержащая по крайней мере одну точку и хотя бы одну точку

Гиперплоскость называется опорной к в точке , если

либо , то есть для всех ;

либо , то есть для всех .

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

Иллюстрации.

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

Теорема.

Эта теорема говорит о существовании опорной гиперплоскости к выпуклому множеству в граничной точке.

Теорема.

Пусть и (непустые выпуклые множества), такие, что .

Тогда существует гиперплоскость , разделяющая и , то есть

.

Теорема(Жордана).

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

система 1: ;

система 2: .

5.5Выпуклые конусы и полярность.

Определение.

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

Если - выпуклое множество, то оно называется выпуклым конусом.

Определение.

Пусть имеется непустое множество ,

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

Если , то совпадает по определению с .

Лемма.

Пусть , , в . Тогда справедливы следующие утверждения:

1. - замкнутый выпуклый конус;

2. , где - полярный к конус;

3. если , то .

5.6Многогранные множества.

Определение.

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

( 5.6.0 )

где

- ненулевые векторы,

- скаляры

Многогранное множество замкнуто и выпукло

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

Примеры многогранных множеств:

, матрица размерности .

5.7Экстремальные точки и экстремальные направления.

Определение.

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

при справедливо только

при .

Пример:

1)

- множество экстремальных точек.

1. .

Любая точка выпуклого множества может быть представлена как выпуклая комбинация экстремальных точек. Это верно для ограниченных множеств.

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

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

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

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

Определение.

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

б) два направления называются различными , если .

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

Пример.

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

- экстремальные направления.

Определение.

Если , где - матрица размера ранга , то, учитывая структуру множества , вектор является направлением множества тогда и только тогда, когда .

5.7.1Характеристики экстремальных точек и экстремальных направлений.

Теорема 1(о характеристике экстремальных точек ).

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

где - невырожденная матрица порядка , удовлетворяющая неравенству

.

Следствие.

Число экстремальных точек множества конечно.

Число экстремальных точек не превосходит величину .

Теорема(существования экстремальных точек ).

Пусть задано непустое множество , где - матрица размера ранга , - вектор из .Тогда имеет по крайней мере одну экстремальную точку.

5.7.2Экстремальные направления.

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

- компонента

Следствие.

Число экстремальных направлений конечно.

Число экстремальных направлений не превосходит .