Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ВОЕНЫ АЛЛАХА1АЗАЗАЗАЗ / 1_Выпуклые_множества_сент_9_2008

.pdf
Скачиваний:
31
Добавлен:
10.02.2015
Размер:
347.19 Кб
Скачать

20

О.А. Кашина, А.И. Кораблев

 

 

Элементы выпуклого анализа

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

мер, в [2], [3], [9], [12], [13], [20], [23], [25]. Аппарат выпуклого анализа широко используется во многих математических дисциплинах, в моделировании различных явлений и в численных методах решения разнообразных прикладных задач. В частности, выпуклый анализ лежит в основе теории экстремальных задач.

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

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

Определение 1. Пусть заданы точки a, b и любое t 0,1 . Линейная комбинация ta (1

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

E

 

 

n

t)b

и

b

.

 

Часто выпуклую комбинацию записывают в виде b t (a b) или t1 a t2 b; t1 0; t2 0; t1 t2 1.

Легко увидеть, что эти формы записи эквивалентны.

Методы оптимизации: Часть I

 

 

 

 

 

 

21

 

Определение 2. Множество a, b всех выпук-

лых комбинаций точек

a, b

называется отрезком

прямой, соединяющим

эти

точки.

 

 

 

 

Определение 3. Множество D

E

n

называ-

 

ется выпуклым, если отрезок

x, y

включается в

D для любых

x, y D .

 

 

 

 

 

 

Теорема 1. Пусть имеется семейство выпук-

лых множеств

D . Тогда множество

 

D I D

 

 

 

 

 

 

 

 

 

является выпуклым.

 

 

 

 

 

 

 

Доказательство.

Пусть

x, y D

,

тогда

x, y D , . Так как все множества

D

 

выпук-

лые, x, y D ,

, откуда

x, y I D .

Таким

 

 

 

 

 

 

 

 

 

образом, x, y D . Что и требовалось.

 

 

 

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

множеств

Di и чисел i ,

i 1, ..., m,

 

m

 

 

 

m

 

 

 

i Di

 

x E

n

: x i xi ,

xi

Di ,

i 1, ..., m .

 

i 1

 

 

 

i 1

 

 

 

 

Теорема 2.

 

Пусть

для

всех i 1, ..., m мно-

жества

D En

 

– выпуклые,

 

R .

Тогда выпук-

 

 

i

 

 

 

i

 

 

m

ло и множество D i Di .

i 1

22

О.А. Кашина, А.И. Кораблев

Доказательство. Пусть

ствуют такие векторы

xi , yi

x,

y Di ,

D, i

тогда суще-

1, ..., m , что

 

m

 

x

 

i i

 

x

 

i 1

 

,

y

 

m

 

 

i i

 

y

 

i 1

 

. Пусть

t

0,

1

. Так как все

множества Di являются выпуклыми, то для любого i 1, ..., m имеем включение t xi 1 t yi Di .

m

Следовательно, t x 1 t y i t xi 1 t yi D ,

i 1

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

D

.

Теорема 3.

Пусть D E

ство, тогда его

замыкание

n – выпуклое множе- D также выпукло.

Доказательство. Пусть

предельные точки множества

последовательности

xi

 

i 1,2,...

x, y D ,

то есть

x, y

 

D . Тогда существуют

,

yi

 

D

такие,

 

i 1,2,...

 

 

что

lim xi

x ,

lim yi

y .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i

 

 

 

i

 

 

 

 

 

 

 

 

0,1 . Тогда

 

 

Пусть

t

– любое из отрезка

 

 

 

 

y t lim x

 

 

 

 

 

lim

t x

 

 

 

 

 

t x 1 t

 

1 t

 

lim y

 

1 t

 

y

 

.

 

 

 

 

 

i

i

 

 

i

i

i

 

 

i

 

 

i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В силу

выпуклости

 

множества

D

выполня-

ются

включения

t xi

1 t yi

D,

i 1,2, ...

Сле-

 

t x

1 t y

 

,

 

 

 

 

 

 

довательно,

D

что

и

 

означает

 

вы-

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

D

.

Теорема 4. Пусть D – выпуклое множество, тогда его внутренность int D также выпукла.

Выше было приведено определение выпуклой комбинации двух векторов. Обобщим это понятие на

Методы оптимизации: Часть I

23

 

 

случай произвольного

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

векторов

xi E

n

,

i

 

конечного числа векторов.

 

 

m

 

Линейная

комбинация

ti

xi

 

 

i 1

 

1, ..., m

называется

выпук-

лой комбинацией, если

ti

0

,

i 1, ..., m

и

m ti i 1

1

.

Определение 4. Множество всевозможных выпуклых комбинаций любого конечного числа век-

торов из множества D

оболочкой множества

D

E

n

называется выпуклой

 

и обозначается

convD.

Очевидно, что для всякого

D

множество

convD является выпуклым. Нетрудно показать, что

множество D

является выпуклым тогда и только

тогда, когда

D convD.

 

 

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

множества

D

называется наименьшее выпуклое

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

Определение 5. Вектор x из выпуклого множества D называется крайней точкой множества D , если он не является выпуклой комбинацией

никаких двух других векторов из

D .

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