Выпуклый анализ. Выпуклые множества. Лекция 8

1. ВЫПУКЛЫЙ АНАЛИЗ

ЛЕКЦИЯ 8
2. ВЫПУКЛЫЕ МНОЖЕСТВА
(ПРОДОЛЖЕНИЕ)

2.

2. ВЫПУКЛЫЕ МНОЖЕСТВА
(ПРОДОЛЖЕНИЕ)
2.6. Замыкание и внутренность выпуклых множеств(продолжение).
2.7. Внутренность и относительная внутренность выпуклых множеств.

3.

2.6. Замыкание и внутренность выпуклых множеств(продолжение). Следующее
утверждение усиливает теорему 14.
Теорема 15. Пусть U
1) Для всех
Ì R n выпуклое множество и int U ¹ Æ.
u0 Î int U , v Î U , a Î ( 0,1]
справедливо включение
va = a u0 + ( 1 - a ) v = v + a ( u0 - v ) Î int U .
и
2) Для всех
u0 Î int U , y Ï int U , l > 1
имеет место
wl = u0 + l ( y - u0 ) Ï U .
Доказательство. 1) Из включения
v
U
O ( u0 , d )
u0
( 3)
( 4)
U
v va
u0
wl y
u0
U
u 0 Î int U следует существование
{
Тогда
окрестности
}
O ( u0 , d ) = u Î R n u - u0 < d Ì U .

4.

Пусть
a Î ( 0,1] .
Полагаем
va = a u0 + ( 1 - a ) v.
ww va
a
u0
U
Полагаем wa
O ( u0 , d )
U)
w ÎU ,
ad
v-w <
.
1-a
( 5)
= a u0 + ( 1 - a ) w и оценим по норме разность между точками va и wa :
a u0 + ( 1-a ) v
}
va
множества
a u0 + ( 1-a ) w
}
wa
-
= a u0 + ( 1 - a ) v - a u0 - ( 1 - a ) w =
<
v
w w va
a
U
u0
O ( u0 , d )
O ( wa , ad )
va
ad
1-a
6 7³08
6 7³08
678
= ( 1-a ) v - ( 1-a ) w = ( 1-a ) v - w <
Таким образом, va
т. е. точка
v ÎU
( v - предельная точка
для которой будет выполняться неравенство
следует существование точки
v
Из включения
Î O ( wa , ad ) ,
1 - a ) ad
(
<
1-a
при чем
лежит строго внутри окрестности
= ad .
b = ad - va - wa > 0,
O ( wa , ad ) .

5.

vv
u
a
w
Покажем, что справедливо вложение
O ( wa , ad ) Ì U .
u - wa
a = u0 +
a
( 6)
u Î O( wa , ad )
С этой целью для всех
и установим, что
a - u0 =
a
U
a u0
O ( u0 , d )
O ( wa , ad )
положим
a Î O ( u0 , d ) Ì U .
uÎO ( wa ,ad ) Þ<ad
u - wa
wa
<
С другой стороны из
Действительно,
ad
= d Þ a Î O ( u0 , d ) Ì U
a
w +a ( u0 - w )
}
wa = a ( a - u0 ) +
Î}U
Î}U
+ w + a ( u0 - w ) = a a + w - a w = a a + ( 1 - a ) w Î U .
u - wa
a = u0 +
Þ u = a ( a - u0 ) +
a
Вложение (6) доказано. Для завершения доказательства первого пункта теоремы требуется
установить, что точка
va
входит в множество
O( wa ,ad ) Ì U
вместе со

6.

своей окрестностью
- va - wa > 0.
uÎO ( va , b ) Þ£ b
u - va
vv
b = ad -
где
В самом деле, если
u - wa =
£
O ( va , b ) ,
wu
u Î O ( va , b ) , то
u - wa + va - va £
+ va - wa £
ad - va - wa
b
a
wa
U
u0
O ( u0 , d )
O ( wa , ad )
+ va - wa =
= ad - va - wa + va - wa = ad Þ u Î O ( wa , ad ) .
( 6)
входит в U вместе с окрестностью
Таким образом, u Î O ( wa , ad ) Ì U , va
O ( va , b )
и пункт 1) теоремы доказан.
2) Пусть теперь
wl y
U
wl = u0 + l ( y - u0 ) , l > 1, u0 Î int U , y Ï int U .
wl Î U
От противного примем, что
l > 1.
u0
находим
Из представления для
wl - u0
y = u0 +
.
l
при каком-либо
wl = u0 + l ( y - u0 )
Полагаем
a=
1
>1
l
Î ( 0, 1) .

7.

}
Î( 0,1)
} æ }U Îi}nt U ö
1
y = u0 + ( wl - u0 ) = u0 + a çç wl - u0 ÷÷ ,
l
è
ø
=a
Тогда
где
a Î ( 0,1) , wl Î U , u0 Î int U .
тогда должно выполняться
Следовательно,
wl Ï U
y Î int U ,
при всех
По доказанному первому пункту теоремы
что противоречит условию
l > 1.
y Ï int U .
Теорема доказана полностью.
Очевидно, что из доказанной теоремы сразу следует справедливость теоремы 14.
Упражнение 1.
Из утверждения теоремы 15
Пусть U Ì R выпуклое множество, int U
n
для всех
a Î ( 0,1] справедливо
¹ Æ, u0 Î int U , v Î U .
va = a u0 + ( 1 - a ) v Î int U .
Тогда
( 3)
вывести утверждение теоремы 14: внутренность выпуклых множеств выпукла.
Решение. Пусть
следует
u1 , u2 Î int U , a Î ( 0,1) .
Î( 0,1) Îint U
В силу
intU Ì U
æ Î(}0,1) ö Îint}U ÌU
} }
ua = a u1 + ç1 - a ÷ u2 Î int U .
ç
÷
è
ø
из (3)

8.

2.7. Внутренность и относительная внутренность выпуклых множеств. Выпуклое
множество может иметь и не иметь внутренних точек. Например, круг в
R2
внутренние
точки имеет, а отрезок прямой – нет. Выясним условия не пустоты внутренности
выпуклого множества.
Лемма 1. Пусть
S ( u0 , u1 ,L , un ) Ì R n
- симплекс, натянутый на точки
m
m
ì
u0 , u1 ,L , un S ( u0 , u1 ,L , um ) = íu = å li ui li ³ 0, å li = 1üý ,
i =0
i =0
î
þ
u1 - u0 ,L , um - uл0 -нз/ . Тогда int S ( u0 , u1 ,L , un ) ¹ Æ.
Доказательство.
u
из множества
Для доказательства достаточно построить хотя бы одну точку
int S ( u0 , u1 ,L , un ) .
n
u = å li ui ,
i =0
Покажем, что
n
ål
i =0
i
Полагаем
= 1, li > 0, i = 0,1,L , n.
u Î int S ( u0 , u1 ,L , un ) ¹ Æ.
независимости векторов
u1 - u 0 , , u n - u 0
линейных алгебраических уравнений
( 1)
Действительно, в силу линейной
для всех
u Î Rn
система

9.

n
ål ( u -u ) = u -u
i
i =1
i
0
0
( 2)
Þ
l1 ( u11 - u01 ) + l2 ( u21 - u01 ) + L + ln ( u1n - u01 ) = u1 - u01 ,
l1 ( u12 - u02 ) + l2 ( u22 - u02 ) + L + ln ( un2 - u02 ) = u 2 - u02 ,
L L L L L L L L L L L L L L L L L L L L L L
l1 ( u1n - u0n ) + l2 ( u2n - u0n ) + L + ln ( unn - u0n ) = u n - u0n
относительно неизвестных
li , i = 1, , n имеет единственное решение li ( u ) ,
n
i = 1,L , n, непрерывно зависящее отn u Î R . Полагаем
l0 (u ) = 1 - å li ( u ) , u Î R n .
Очевидно, что функция l0
n
ål ( u -u )
i =1
i
i
0
}u
= u - u0
i =1
1
: Rn ® R
( 2)
непрерывна. При
n
u = u = å li ui , система (2)
i =0
принимает вид
n
ål ( u -u ) = u -u .
i =1
i
i
0
( 3)
0

10.

}li
å li ( ui - u0 ) = u - u0 .
n
Для
li = li , i = 1, , n
соотношение
превращается в тождество. Действительно,
n
ål ( u -u )
i =1
i
i
0
i =1
n
å liui
i =0
}
= u - u0 Þ
å liui
1
6 7i=8
l0u0 +
æ n ö
li ui - ç å li ÷ u0 =
å
i =1
è i =1 ø
n
n
n
ål u
i =0
i i
- u0 Þ
n
æ n ö
æ n ö
li ui - ç å li ÷ u0 = l0u0 + å li ui - u0 Þ - ç å li ÷ u0 = l0u0 - u0 Þ
å
i =1
è i =1 ø
è i =1 ø
i =1
( 1) Þ=1
64 7 48
æ n ö
- ç å li ÷ u0 = -u0 Þ 0 º 0.
è i =0 ø
n
Таким образом, набор чисел
li = li , i = 1, , n
является решением системы (2)

11.

( 1)
n
å l ( u - u ) = u - u ( 2 ) . Тогда
i =1
i
i
0
li ( u ) = li > 0, i = 1,L , n.
0
n
l0 (u ) = 1 - å li ( u ) , u Î R n
( 3)
i =1
li
n }
l0 (u ) = 1 - å li ( u ) =
i =1
В силу непрерывности функций
Из (3)
находим
( 1) Þ= l0
64 7 48
n
1 - å li = l0 > 0.
( 4)
i =1
li : R ® R 1 , i = 0,1, , n
n
из неравенств
вытекают неравенства
l0 (u ) > 0, li ( u ) > 0, i = 1,L , n, ( 4 )
l0 (u ) > 0, li ( u ) > 0, i = 1,L , n,
для всех точек
u ÎO ( u , ) ,
n
из (2)
ål ( u -u )
i =1
i
i
n
0
li = li ( u )
где величина
= u - u0
u = u0 + å li ( u ) ( ui - u0 ) =
i =1
(2)
>0
при
достаточно мала. Для этих точек
li = li ( u ) , i = 1,L , n,
находим
æ n
ö
u0 + å li ( u ) ui - ç å li ( u ) ÷ u0 =
i =1
è i =1
ø
n

12.

( 3) Þ= l0 ( u )
6 44
7 4 48
n
n
n
æ n
ö
æ
ö
= u0 + å li ( u ) ui - ç å li ( u ) ÷ u0 = 1 - å l ( u ) u + å l ( u ) u =
i
i
i
ç
÷ 0
i =1
è i =1
ø
i =1
è i =1
ø
m
ìï
íu = li ui li ³ 0,
ïî i =0
üï
li =1ý
i =0
þï
m
å
å
6 4 4 7 4 48
n
n
= l0 (u )u0 + å li ( u ) ui = å li ( u ) ui Î S ( u0 , u1 ,L , un ) .
i =1
Последнее включение означает, что
i =0
u Î int S ( u0 , u1 ,L , un ) .
Лемма доказана.

13.

Упражнение 1. Даны:
æ 34 ö
æ1ö
æ 0ö
æ 1ö
u0 = ç ÷ , u1 = ç ÷ , u2 = ç ÷ , v = ç 1 ÷
è0ø
è1ø
è 1ø
è2ø
1. Доказать, что множество
ìïæ l0 + l2 ö
üï
S ( u0 , u1 , u2 ) = íç
÷ l0 + l1 + l2 = 1, li ³ 0, i = 1, 2,3ý
ïîè l1 + l2 ø
ïþ
является двух мерным симплексом, натянутым на векторы u0 , u1 , u2 .
æ 34 ö
2. Доказать, что v = ç ÷ Î Int S ( u0 , u1 , u2 ) .
1
è2ø
1. Очевидно, что
S ( u0 , u1 , u2 )
Вектора
ìï æ 1 ö
üï
æ0ö
æ1ö
= íl0 ç ÷ + l1 ç ÷ + l2 ç ÷ l0 + l1 + l2 = 1, li ³ 0, i = 1, 2,3ý =
è1ø
è1ø
ïî è 0 ø
ïþ
= co { u0 , u1 , u2 }
æ 0 ö æ 1 ö æ -1ö
æ 1ö æ 1 ö æ 0 ö
u1 - u0 = ç ÷ - ç ÷ = ç ÷ , u2 - u0 = ç ÷ - ç ÷ = ç ÷
è1ø è 0ø è 1 ø
è 1ø è 0 ø è 1 ø
линейно независимы.

14.

Тогда
2.
S ( u0 , u1 , u2 ) -
симплекс.
Найдем решение системы линейных уравнений
ì æ1ö
æ0ö
æ 1ö æ 34 ö
ïl0 ç ÷ + l1 ç ÷ + l2 ç ÷ = ç 1 ÷ ,
í è 0ø
è1ø
è 1ø è 2 ø Þ
ïl + l + l = 1
î 0 1 2
ìl0 + l2 = 34 ,
ï
1
íl1 + l2 = 2 , Þ
ïl + l + l = 1
î 0 1 2
ìl0 = 12 > 0,
ï
1
íl1 = 4 > 0, Þ
ïl = 1 > 0.
î 2 4
v Î Int S ( u0 , u1 , u2 ) .
U Ì R n - непустое выпуклое множество. Для того, чтобы
несущее подпространство
= dim ( LinU )
}
int U ¹ Æ необходимо и достаточно, чтобы dim U = n,
LinU
подпространство PaffU т.е. чтобы несущее подпространство совпадало с R n .
Теорема 16. Пусть
Доказательство. Необходимость.
окрестность
Пусть
v Î int U ¹ Æ.
Тогда существует
O ( v, ) Ì U , т. е. шар с центром в точке v, принадлежащий множеству U .
Отсюда выводим
O ( v, ) Ì U Ì affU Þ affU = R n Þ LinU = R n Þ dim U = n.
Необходимость доказана.

15.

Достаточность. Пусть
dim U = n.
Тогда LinU = affU = R n . Обозначим через
v1 = u1 - u0 ,L , vr = ur - u0 ,
максимальный набор линейно независимых векторов,
перебирая всевозможные точки ui
натянем n - мерный симплекс
Î U , i = 0,1,L , r.
Sn ( u0 , u1 ,L , ur ) = co { u0 , u1 ,L , ur }
r
Для всех
li ³ 0, å li = 1
u 0 , u1 , , u r
r
r
ì
ü
= íu = å li ui li ³ 0, å li = 1ý .
i =0
i =0
î
þ
из выпуклости множества U и включения
r
å l u Î U Þ S ( u , u ,L
При
На точки
u0 , u1 ,L , ur Î U
i =0
следует
i =0
который можно получить,
0
i i
r=n
1
, ur ) Ì U Þ int S n ( u0 , u1 ,L , ur ) Ì int U .
по лемме 1 должно выполняться
достаточно установить, что
r = n.
int S n ( u0 , u1 ,L , ur ) ¹ Æ,
Допустим противное:
поэтому
r < n. Обозначим через
ui -u0
ì
ü
r
}
ï
ï
L = íu = å a i vi a i Î ( -¥, +¥ ) , i = 1,L , r ý .
i =1
ïî
ïþ
( 5)

16.

подпространство, натянутое на вектора
равна
r < n.
для всех
л/н
64 7
48
v1 ,L , vr . Размерность этого подпространства
Из максимальности набора линейно независимых векторов
u ÎU
v1 = u1 - u 0 , , v r = u r - u 0
имеет место равенство
ÎL
67
8
r
u - u0 = å li vi , li Î R1 Þ u - u0 Î L.
( 6)
i =1
выполняется
u Î U афинное
множество
6
4 7 48
Ì L Þ U Ì L + { u0 } Þ affU Ì L + { u0 } Þ
В силу (6) и произвольности
U - { u0 }
6 4 4 LinU
7448
ìu0 ÎU Ì affU ü
affU - í u0 ý Ì L Þ LinU Ì L Þ dim LinU £ dim L = r.
( 7)
î
þ
По условию теоремы n = dim U ( = dim LinU ) . Тогда из (7) выводим n £ r.
Получили противоречие с
Теорема доказана.
r < n.
Остается признать, что
r = n.

17.

Пример 9. Выпуклое множество
{
}
U = u = ( x, y , z ) Î R 3 x 2 + y 2 £ 1, z = 0 ,
представляющее собой единичный круг в плоскости
В тоже время, если рассматривать это множество как
не имеет внутренних точек.
подмножество
R2 = p 2 ,
p 2 = { u = ( x, y, z ) Î R 3 z = 0} ,
то его внутренность не пуста.
Рассмотренный пример приводит к следующему определению.
Определение 12.
Точка
v ÎU Ì R
называется относительно внутренней
точкой множества
U,
открытая окрестность
v,
что
affU
если существует
O ( v, )
z
n
U
O
точки
O ( v, ) I affU Ì U .
v
LinU
x
Множество всех относительно внутренних точек называется относительной
внутренностью множества
U
и обозначается символом
riU .
y

18.

Для единичного круга из примера 9 справедливо
affU = LinU = p 2 = { u = ( x, y , z ) Î R 3 z = 0} Þ
{
}
z
O
v
U
y
riU = u = ( x, y , z ) Î R 3 x 2 + y 2 < 1, z = 0 ¹ Æ.
x
affU = LinU
Существуют множества,
для которых относительная внутренность пуста.
Например, множество, состоящее из двух различных точек.
Для любого выпуклого множества U Ì R n
внутренность не пуста.
Доказательство. Не теряя общности, будем считать, что
Теорема 17.
случае надо перейти к множеству
U - { v} , v Î U ,
будет являться аффинной оболочкой для множества
0 Î affU = LinU É U .
Множество
LinU
которого совпадает с размерностью множества
к доказательству предыдущей теоремы.
U
его относительная
0 Î U . (В противном
при этом множество
U - { v} .
)
affU - { v}
Тогда
подпространство, размерность
и доказательство теоремы сводится