Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 36 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

Составители: 

Рубрика: 

1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА
36
vuvw
Uu
-=-
Î
inf .
Справедливо следующее утверждение (см. рис 5).
Теорема 22. Пусть
n
RU Ì
- замкнутое множество. Тогда для всякой
точки
n
RvÎ
существует ее проекция на это множество. Если множество
U
выпукло, то проекция единственна и равенство
)(vPw
U
= имеет место тогда и только тогда,
когда
Uuwuvw Î"³-- ,0, . (1)
Доказательство. Задача построения
)(vPw
U
= - проекции точки
v
на множество
U
сводится к минимизации
функции
1
: RUI ® , определенной равенством
vuvuvuvI --=-= ,)(
2
.
Очевидно, что точка минимума этой функции, если она существует,
должна принадлежать множеству
(
)
,
BOvU
r
=
I
, где
(
)
,
Ov
шар столь
большого радиуса, что для него
Æ
¹
B . Множество
B
компактно, а функция
I
непрерывна, поэтому по теореме Вейерштрасса точка минимума
U
w
Î
функции
I
действительно существует, и wvP
U
=)( . Множество
B
является
выпуклым как пересечение двух выпуклых множеств. Тогда по теореме 21 в точке
w
выполнено неравенство
'(),0
Iwuw
-³
.
Из него следует искомое условие (1). Теорема доказана.
1.14. Отделимость точки и множества. Точку и выпуклое множество
можно разделить гиперплоскостью так, что они будут находиться в разных
полупространствах, определяемых этой гиперплоскостью.
Теорема 23. Пусть
n
RU Ì выпуклое множество. Тогда для любой точки
Uv int
Ï
существует вектор
(
)
0
cv
¹
, такой, что
v
w
u
Рис . 5
U
1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА


                                        w - v = inf u - v .
                                                  uÎU



       Справедливо следующее утверждение (см. рис 5).

       Теорема 22. Пусть U Ì R n - замкнутое множество. Тогда для всякой
точки v Î R n существует ее проекция на это множество. Если множество U
                                       выпукло, то проекция единственна и равенство
                                       w = PU (v ) имеет место тогда и только тогда,
                      u
                                       когда
   v            w             U
                                                   w - v, u - w ³ 0, "u Î U .             (1)

                    Рис . 5                   Доказательство.             Задача   построения
w = PU (v) - проекции точки v на множество U                           сводится к минимизации
функции I : U ® R 1 , определенной равенством

                                  I (v ) = u - v 2 = u - v , u - v .

       Очевидно, что точка минимума этой функции, если она существует,
должна принадлежать множеству B = O ( v, r ) I U , где O ( v, r ) шар столь

большого радиуса, что для него B ¹ Æ . Множество B компактно, а функция I
непрерывна, поэтому по теореме Вейерштрасса точка минимума wÎU
функции I действительно существует, и PU ( v ) = w . Множество B является
выпуклым как пересечение двух выпуклых множеств. Тогда по теореме 21 в точке
w выполнено неравенство

                                        I '( w), u - w ³ 0 .

       Из него следует искомое условие (1). Теорема доказана.

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

       Теорема 23. Пусть U Ì R n выпуклое множество. Тогда для любой точки
v Ï int U существует вектор c ( v ) ¹ 0 , такой, что


                                                 36

Страницы