Тема 2. Задача нелинейного программирования (продолжение) (стр. 1 )

Лекция №4

Тема 2. Задача нелинейного программирования (продолжение)

2.  Задачи выпуклого программирования

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

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

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

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

 

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

1. En.

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. Свойства выпуклых множеств

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

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

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

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

,

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

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

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

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

.

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

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

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

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

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

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

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

и .

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1. Понятие выпуклой и вогнутой функций

Определение 1. Функция f(x), заданная на выпуклом множестве XEn, называется выпуклой на X, если для двух любых и имеем

(3.1)

при любом .

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

 

Определение 2. Функция f(x), заданная на выпуклом множестве XEn, называется строго выпуклой на X, если для двух любых и имеем

при любом .

Определение 3. Функция f(x), заданная на выпуклом множестве XEn, называется вогнутой на X, если функция –f(x) выпукла на X.

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

 

Примеры графиков выпуклых и вогнутых функций приведены на рис. 3.5-3.7.

Рис 3.5. Пример выпуклой функции, заданной на выпуклом множестве [A,B]. Здесь [C,D] – отрезок прямой линии

Рис 3.6. Пример строго выпуклой функции, заданной на выпуклом множестве [A,B]. График строго выпуклой функции не может включать отрезка прямой линии типа [C,D] на рис. 3.5.

Рис 3.7. Пример вогнутой функции, заданной на выпуклом множестве [A,B].

2.2.2. Свойства выпуклых функций. Пусть функции f(x) и g(x) выпуклы на выпуклом множестве XEn. Тогда:

1.  Функции f(x)+g(x) и max {f(x), g(x)} выпуклы на X.

2.  Функция cf(x) выпукла на X при c≥0.

3.  Функция f(x) непрерывна на (см. рис. 3.8).

4.  Множество является выпуклым множеством при любом числе b (см. рис. 3.9).