ВОЕНЫ АЛЛАХА1АЗАЗАЗАЗ / 1_Выпуклые_множества_сент_9_2008
.pdf20 |
О.А. Кашина, А.И. Кораблев |
|
|
Элементы выпуклого анализа
Выпуклый анализ – это раздел современного математического анализа, посвященный изучению выпуклых множеств и выпуклых функций. Изложение основ выпуклого анализа можно найти, напри-
мер, в [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 . |
Легко увидеть, что любая крайняя точка выпуклого множества является его граничной точкой, но не всякая граничная точка является крайней.