Выпуклый анализ. Субградиент и субдифференциал функции. Лекция 21

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

ЛЕКЦИЯ 21
7. СУБГРАДИЕНТ И СУБДИФФЕРЕНЦИАЛ ФУНКЦИИ
(ПРОДОЛЖЕНИЕ)

2.

7. СУБГРАДИЕНТ И СУБДИФФЕРЕНЦИАЛ ФУНКЦИИ
(ПРОДОЛЖЕНИЕ)
7.2. Критерий существование субградиента функции.

3.

7.2. Критерий существования субградиента функции.
Следующая теорема
является критерием существования субградиента и, следовательно, субдифференциала у
функции
I : U ® R1.
Теорема 2.
Пусть
U Rn
- открытое выпуклое множество. Для того, чтобы
u U
необходимо и достаточно, чтобы эта функция была выпуклой на множестве U .
Доказательство. Необходимость. Пусть для некоторой функции I : U ® R 1
функция
I : U ® R1
имела непустой субдифференциал в каждой точке
¶I ( u ) ¹ Æ, "u U .
Докажем выпуклость функции I . Для всех u , v U , 0, 1 полагаем
u = u + ( 1 - ) v U , c ( u ) ¶I ( u ) ¹ Æ
справедливо
Последовательно подставляем в I (u ) ³ I (v) + c(v), u - v , "u U . (1.1)
I ( u ) - I ( u ) ³ c ( u ) , u - u ,
(1- ) I ( v ) - I ( u ) ³ c ( u ) , v - u .
I ( u ) +(1- )I ( v ) - I ( u ) ³
v ® u ,
u®v
v ® u
(1)
6 4 44 7=0 4 4 48
c ( u ) , u + ( 1 - ) v - u ,

4.

I ( u ) +(1- )I ( v ) - I ( u )
6 4 44 7=0 4 4 48
³ c ( u ) , u + ( 1 - ) v - u Þ
I ( u ) +(1- )I ( v ) ³ I ( u )
}
Þ I ( u ) £ I ( u ) +(1- )I ( v )
u +( 1- ) v
I ( u + ( 1 - ) v ) £ I ( u ) +(1- )I ( v )
Необходимость доказана.
Достаточность. Пусть
I : U ® R 1 выпуклая функция и v U . Надо показать,
что ¶I ( v ) ¹ Æ. Для произвольного e R n , e = 1 полагаем v ( t ) = v + te. В силу
для достаточно малых t0 > 0 будет выполняться
открытости множества U
v ( t ) U , t 0, t0 ) . Из выпуклости функции I
dI ( v )
e
по теореме 3.7 для всех e существует
v v( t)
de
U
производная функции
I по направлению e.
В пространстве R
переменных ( u , )
A = { ( u , ) R n +1 u U ; > I ( u ) } ,
n +1
I
рассмотрим множества
dI ( v )
ì
ü
n +1
B = í( u , ) R u = v + te; = I ( v ) + t
; 0 £ t < t0 ý .
de
î
þ
I ( v) A
B
v v + t0e U
u

5.

Множество
A R n +1 выпукло. Доказательство этого факта аналогично
I
доказательству выпуклости надграфика выпуклой функции теорема 4.1.
Множество
B R n +1
тоже выпукло. Покажем что для малых t0 будет выполняться
( 2)
A I B = Æ.
В самом деле, пусть
1)
2)
I ( v) A
представляет собой отрезок прямой, и поэтому
( u, ) A.
u
B
v v + t0 e U
Имеются две возможности
u ¹ v + te, "t 0, t0 ) Þ ( u , ) Ï B;
( u, ) A выводим
- I ( v ) > I ( v + te ) - I ( v ) . ( 3)
$t 0, t0 ) : u = v + te .
> I ( u ) = I ( v + te ) Þ
По лемме 3.1 из выпуклости функции
выпуклость функции j
I
для достаточно малых
( t ) = I ( v + te ) , t 0, t0 .
dI ( v )
В силу
t0 > 0
следует
По первому критерию выпуклости
dI ( v )
.
j ( t ) ³ j ( 0 ) + j ' ( t ) ( t - 0 ) Þ I ( v + te ) - I ( v ) ³ t
de
I ( v + te )
I ( v)
de

6.

Из (3) - I ( v ) > I ( v + te ) - I ( v )
dI ( v )
³t
dI ( v )
выводим
( 3) отсюда I ( v + te ) - I ( v ) ³ t
de
6 4 4 7de4 48
dI ( v )
dI ( v )
.
Þ - I ( v) > t
- I ( v ) > I ( v + te ) - I ( v ) ³ t
de
de
Тогда из определения множества
следует, что
ì
u = v + te;
ü
ï
ï
B = í( u , ) R n +1
dI ( v ) ; 0 £ t < t0 ý
= I ( v) + t
ï
ï
de
î
þ
Ï B. Таким образом, u, A Þ u ,
( u, ) = ( v + te, )
и (2) A I B = Æ
( 2)
(
(
)
действительно имеет место. Тогда существует гиперплоскость
æd ö
с нормальным вектором n = ç ÷ R n +1 , n ¹ 0, отделяющая множества
èd ø
{
и
) ÏB
}
и B = B, т. е.
A = ( u , ) R n +1 u U ; ³ I ( u )
æ
dI ( v ) ö
ç v + te, I ( v ) + t
÷ B, имеет место неравенство G
de ø
è
dI ( v ) ö
æ
d , u + d ³ d , v + te + d ç I ( v ) + t
÷,
de ø
è
" ³ I ( u ) , u U , t 0, t0 .
(4)
для всех
G
( u, ) A
I
A
U
B
n
u

7.

æd ö
Покажем, что для вектора n = ç ÷ имеет место d ³ 0.
èd ø
I
Действительно, из (4)
A
v
d, u + d ³ d, v + t e +
u
U
n
B
Полагаем
0 dI ( v )
æ
+d ç I ( v ) + t
de
è
при
d, v + d ³ d, v +d
Покажем, что
d ¹ 0.
ö
÷ , t 0, t0
ø
u = v, " > I ( v ) , t = 0
( 4)
выводим
æ >I ( v) ö
I ( v ) Þ d ³ d I ( v ) Þ d ç - I ( v ) ÷ ³ 0 Þ d ³ 0.
è
ø
d = 0 из (4) находим
d , u ³ d , v + te , u U , t 0, t0 .
u = v + e d.
От противного
Заметим, что для малых по модулю
U
Тогда из (5)
0
открытое
u = v +e d U
e
( 5)
будет выполнено
.
d , v + e d ³ d , v + te Þ d , e d ³ d , te Þ e d , d ³ t d , e

8.

При
t=0
отсюда
e d, d ³ t d,e ,
В силу произвольности знака числа
d = 0.
Однако
e
t 0, t0
получим
æd ö
ç ÷ ¹ 0. Получили противоречие.
èd ø
Таким образом, d
æ
dI ( v )
d , u + d ³ d , v + te + d ç I ( v ) + t
de
è
> 0.
> 0.
ö
÷ , ( 4)
ø
В результате получим
d
, u + ³
d
dI ( v )
d
, v + te + I ( v ) + t
,
d
de
" ³ I ( u ) , u U , t 0, t0 .
Обозначим c ( n ) = -
d
d
2
³ 0.
последнее неравенство возможно только если
Разделим неравенство (4)
на величину d
e d
( 6)
и перепишем (6). В результате получим
dI ( v )
- c ( v ) , u + ³ - c ( v ) , v + te + I ( v ) + t
.
de
( 7)

9.

Неравенство (7) - c ( v ) , u +
верно для всех
к
³ I ( u)
I ( u ) + 0.
и
®I ( u ) +0
0
0
³ - c ( v) , v + t e + I ( v) + t
t 0, t0 .
Полагаем в нем
dI ( v )
t=0
de
( 7)
и устремляем
Тогда
- c ( n ) , u + I ( u ) ³ - c ( v ) , v + I ( v ) , u U Þ
I ( u ) - I ( v ) ³ c ( n ) , u - v Þ c ( v ) ¶I ( v ) ¹ Æ.
Теорема доказана.
.