Выпуклый анализ. Выпуклые функции.. Лекция 13

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

ЛЕКЦИЯ 13
3. ВЫПУКЛЫЕ ФУНКЦИИ (ПРОДОЛЖЕНИЕ )

2.

3. ВЫПУКЛЫЕ ФУНКЦИИ
3.5. Критерии выпуклости гладких функций

3.

3.5. Критерии выпуклости гладких функций. Проверка произвольной функции на
выпуклость непосредственно по определению выпуклости обычно сопряжено со
значительными трудностями. Для гладких функций существуют более конструктивные
критерии выпуклости, упрощающие эту проверку.
Теорема 8. (Первый критерий выпуклости дифференцируемой функции). Пусть
U R n выпуклое множество, I Î C 1 (U ), тогда для выпуклости функции
на множестве
U
необходимо и достаточно, чтобы
I (u ) ³ I (v) + I '(v ), u - v , " u , v Î U .
Доказательство. Необходимость. Для всех
I ( a u + (1 - a )v )
выпуклость I
£
u, v ÎU
и
a Î 0,1
a I (u ) + (1 - a ) I (v) Þ
I ( v + a (u - v) ) £ I (v) + a ( I (u ) - I (v) ) Þ
I ( v + a (u - v) ) - I (v) £ a ( I (u ) - I (v ) ) Þ
( 1)
имеем
I

4.

6 4 4( 4 7 4 )4 4 8
I ( v + a (u - v) ) - I (v) £ a ( I (u ) - I (v) ) Þ
=a I ' v +qa ( u - v ) , u - v
0
a I ' ( v + qa (u - v) ) , u - v £ a ( I (u ) - I (v ) ) , q Î 0,1 .
Разделим неравенство (2) на
a 0
и устремим
a
( 2)
к нулю
I ' ( v ) , u - v £ I (u ) - I (v )
В результате получим (1)
I (u ) ³ I (v) + I '(v), u - v
Достаточность. Пусть
Из (1)
u , wa Î U :
для
v, wa Î U :
( 1)
находим
I (u ) - I ( wa ) ³ I ' ( wa ) , u - wa ,
I (v) - I ( wa ) ³ I ' ( wa ) , v - wa .
Первое из этих неравенств умножим на
Имеем
Необходимость доказана.
u, v ÎU и a Î 0,1 . Положим
wa = a u + ( 1 - a ) v Î U .
I (u ) ³ I (v) + I '(v), u - v , " u, v ÎU
для
( 1) .
a,
второе на
(1 - a )
и сложим их почленно.

5.

I (u ) - I ( wa ) ³ I ' ( wa ) , u - wa a
I (v) - I ( wa ) ³ I ' ( wa ) , v - wa
( 1-a )
a I (u ) + (1 - a ) I ( v ) - I ( wa ) ³
³ I ' ( wa ) , a ( u - wa ) + (1 - a ) ( v - wa ) =
= wa
6 447
4 48
= I ' ( wa ) , a u + (1 - a ) v - wa = I ' ( wa ) , wa - wa = 0.
Таким образом,
a I (u ) + (1 - a ) I ( v ) - I ( wa ) ³ 0 Þ
æ a u +}( 1-a ) v ö
I ç wa ÷ = I ( a u + ( 1 - a ) v ) £ a I (u ) + (1 - a ) I ( v ) .
ç
÷
è
ø
и теорема доказана.

6.

Теорема 9. (Второй критерий выпуклости дифференцируемой функции). Пусть
U Rn
выпуклое множество,
на множестве
U
I Î C1 (U ),
тогда для выпуклости функции
I
необходимо и достаточно, чтобы
I '(u ) - I '(v), u - v ³ 0, " u , v Î U .
Доказательство. Необходимость. В силу выпуклости функции
по первому критерию выпуклости
I
( 3)
на множестве
I (u ) ³ I (v) + I '(v), u - v , " u , v Î U
(теорема 8) следует, что для любой пары точек
u, v ÎU
U
( 1)
справедливы неравенства
I (u ) ³ I (v) + I '(v), u - v , I (v) ³ I (u ) + I '(u ), v - u .
Сложим эти неравенства почленно
I (u ) + I (v) ³ I (v) + I (u ) + I '(v), u - v + I '(u ), v - u Þ
- I '(v), u - v - I '(u ), v - u ³ 0 Þ
- I '(v), u - v + I '(u ), u - v ³ 0 Þ I '(u ) - I '(v), u - v ³ 0
Необходимость доказана.

7.

Достаточность. Для всех
неравенства
u, v ÎU , a Î 0,1
следует доказать справедливость
I ( au + ( 1-a ) v) £ a I ( u ) + ( 1-a ) I ( v) Þ
a I ( u ) + ( 1- a ) I ( v) - I ( au + ( 1- a ) v) ³ 0 Þ
a I ( u ) + ( 1- a ) I ( v) - I ( au + ( 1- a ) v) + a I ( au + ( 1- a ) v) -
-a I ( a u + ( 1 - a ) v ) = a I ( u ) - a I ( a u + ( 1 - a ) v ) +
+ ( 1- a ) I ( v) + a I ( au + ( 1- a ) v) - I ( au + ( 1-a ) v) =
= a éë I ( u ) - I ( a u + ( 1 - a ) v ) ùû + ( 1 - a ) I ( v ) +
+ I ( a u + ( 1 - a ) v ) ( a - 1) = a éë I ( u ) - I ( a u + ( 1 - a ) v ) ùû +
1 4 4 4 4 2 4 4 4 43
+ ( 1 - a ) éë I ( v ) - I ( a u + ( 1 - a ) v ) ùû
1 4 4 4 4 2 4 4 4 43
Таким образом следует доказать. что
I2
a I1 + ( 1 - a ) I 2 ³ 0.
I1

8.

Для всех
w, Dw Î R n
имеет место формула конечных приращений
1
ò I ' ( w + t Dw ) , Dw dt ( 4 )
последовательно вычисляем выражения
I = I (u ) - I ( a u + ( 1 - a ) v ) , I = I (v) - I ( a u + ( 1 - a ) v )
I ( w + Dw ) - I ( w ) =
0
1
Для выражения
2
I1
полагаем
w1 = a u + ( 1 - a ) v, w1 + Dw1 = u Þ Dw1 = u -
a u + ( 1-a ) v
w1
= u-
-a u - ( 1 - a ) v = u ( 1 - a ) - ( 1 - a ) v = ( 1 - a ) ( u - v ) .
( 5)
Тогда в силу (4) и (5) выводим
w1
( 4)
ö
æ w1 +Dw1 ö æ
I1 = I ç u ÷ - I ç a u + ( 1 - a ) v ÷ = I ( w1 + Dw1 ) - I ( w1 ) =
è
ø è
ø
( 4) 1
æ a u +( 1-a ) v ( 1-a ) ( u -v ) ö ( 1-a ) ( u -v )
= ò I ' ç w1 + t Dw1 ÷ , Dw1 dt =
è
ø
0
1
= ( 1 - a ) ò I ' ( a u + ( 1 - a ) v + t ( 1 - a ) ( u - v ) ) , ( u - v ) dt. ( 6 )

9.

Для выражения
Dw2 = v Тогда в силу (4)
I2
полагаем
a u -( 1-a ) v
w2 = a u + ( 1 - a ) v, w2 + Dw2 = v Þ
= v - a1 u - ( 1 - a ) v = a ( v - u ) . ( 7 )
I ( w + Dw ) - I ( w ) = ò I ' ( w + t Dw ) , Dw dt ( 4 ) находим
w2
0
w2
æ
6
4
4
7
4 48 ö
( 4)
w2 +Dw2
æ
ö ç
I 2 = I ç v ÷ - I a u + ( 1 - a ) v ÷ = I ( w2 + Dw2 ) - I ( w2 ) =
÷
è
ø ç
è
ø
1
( 4)
æ a u +( 1-a ) v a ( v -u ) ö
= a ò I ' ç w2 + t Dw2 ÷ , v - u dt =
è
ø
0
1
Таким образом,
= a ò I ' ( a u + ( 1 - a ) v + ta ( v - u ) ) , v - u dt .
0
DI ( u , v, a ) = a I1 + ( 1 - a ) I 2 =
1
( 1-a ) ò I '( a u + ( 1-a ) v + t ( 1-a ) ( u - v ) ) , ( u - v )
=a
0
I1
1
a
dt
+
( 1-a )
ò I '( a u +( 1-a ) v +ta ( v -u ) ) , v -u dt
0
I2
=

10.

1
= a ( 1 - a ) ò I ' ( a u + ( 1 - a ) v + t ( 1 - a ) ( u - v ) ) , u - v dt +
0
1
+ ( 1 - a ) a ò I ' ( a u + ( 1 - a ) v + ta ( v - u ) ) , v - u dt =
0
é1
æ 6 4 4 4 4 4 7z1 4 4 4 4 48 ö
= a ( 1 - a ) × êò I 'ça u + ( 1 - a ) v + t( 1 - a ) ( u - v ) ÷ ê0
ç
÷
êë
è
ø
ù
æ 6 4 4 4 4 7z2 4 4 4 48 ö
- I ' ç a u + ( 1 - a ) v + ta ( v - u ) ÷ , u - v dt ú .
ú
ç
÷
úû
è
ø
( 8)
z1 = a u + ( 1 - a ) v + t ( 1 - a ) ( u - v ) =
Обозначим
= au + ( 1-a ) v + t ( 1-a ) u - t ( 1-a ) v =
b11
b12
= éëa + t ( 1 - a ) ùû u + éë( 1 - a ) - t ( 1 - a ) ùû v = b11u + b12 v.

11.

Заметим, что
b11 = a + t ( 1 - a ) ³ 0, b12 = ( 1 - a ) - t ( 1 - a ) ³ 0.
b11 + b12 = a + t ( 1 - a ) + ( 1 - a ) - t ( 1 - a ) =
= a +1-a + t ( 1-a ) - t ( 1-a ) = 1
Из выпуклости множества U отсюда следует, что z1 = b11u + b12 v Î U .
При этом
Аналогично, обозначим
z2 = a u + ( 1 - a ) v + ta ( v - u ) =
b 22
6
4
4
7
4 48
64 7 48
= a u + ( 1 - a ) v + ta v - ta u = a ( 1 - t ) u + ( 1 - a ( 1 - t ) ) v =
b 21
= b 21u + b 22 v.

12.

Заметим, что
b 21 = a ( 1 - t ) ³ 0,
При этом
b 22 = 1 - a ( 1 - t ) ³ 0
b 21 + b 22 = a ( 1 - t ) + 1 - a ( 1 - t ) = 1.
Из выпуклости множества
Кроме того
U
отсюда следует, что
a u + ( 1-a ) v + t ( 1-a ) ( u - v )
z1
-
z2 = b 21u + b 22 v Î U .
a u + ( 1-a ) v + ta ( v -u )
z2
=
= a u + ( 1 - a ) v + t ( 1 - a ) ( u - v ) - a u - ( 1 - a ) v - ta ( v - u ) =
= t ( 1 - a ) ( u - v ) - ta ( v - u ) =
= t ( u - v) ( 1-a + a ) = t ( u - v) Þ
1
u - v = ( z1 - z2 ) .
t
( 9)

13.

Из (8)
1
DI ( u , v, a ) = a ( 1 - a ) ´ ò
0
z1
æ
ö
I 'çau + ( 1- a ) v + t( 1 - a ) ( u - v ) ÷ è
ø
1
( z1 - z2 )
t
æ
ö
- I ' ç a u + ( 1 - a ) v + ta ( v - u ) ÷ , u - v
è
ø
z2
dt
( 8)
z1 = a u + ( 1 - a ) v + t ( 1 - a ) ( u - v ) ,
в силу (9)
z2 = a u + ( 1 - a ) v + ta ( v - u )
u-v =
1
( z1 - z2 )
t
имеем
( 9)
³ 0 по условию теоремы
6
4
4 44 7 4 4 4 48 ³0
1
1
DI ( u , v, a ) = a ( 1 - a ) ò I ' ( z1 ) - I ' ( z2 ) , z1 - z2
dt.
t
0
По доказанному
Следовательно
z1 , z2 Î U . Тогда для этих точек выполнено условие (3)
I '(u ) - I '(v), u - v ³ 0, " u , v ÎU .
( 3)
DI ( u , v, a ) ³ 0.
Теорема доказана.

14.

Теорема 10. (Критерий выпуклости дважды дифференцируемой функции). Пусть
U Rn
выпуклое множество,
на множестве
U
I Î C 2 (U ),
достаточно, чтобы
I ''(u )x , x ³ 0,
если
int U ¹ Æ,
( 10 )
" u ÎU , x Î R n ,
то это условие является необходимым.
Доказательство. Необходимость. Пусть int U
n
Тогда найдется число e 0 0, что
x ÎR .
u + ex
Из второго критерия выпуклости
выводим
тогда для выпуклости функции
¹ Æ.
Возьмем
u + ex Î U ,
u
u Î int U
если
ex
и
e £ e0.
I '( u ) - I '(v ), u - v ³ 0, " u , v Î U
( 3)
I ' ( u + ex ) - I '(u ), ex = I '' ( u + qex ) ex , ex =
( 3)
= e 2 I '' ( u + qex ) x , x ³ 0,
q Î 0,1 , e Î -e 0 , e 0 .
( 11)
I

15.

Сокращая в неравенстве (11)
и устремляя
Если
e
e
2
I '' ( u + qex ) x , x ³ 0
к нулю, получим (10).
u Î U \ int U ,
0
I ''(u )x , x ³ 0,
( 11)
на
e 0
2
( 10 )
то так как выпуклое множество не может содержать
изолированных точек, найдется последовательность
{ uk } ® u, uk Î intU , k = 1, 2,L
.
По доказанному выше будет выполняться
I ''(uk )x , x ³ 0, x Î R n .
Переходя здесь к пределу при
k ® ¥, получим условие (9) и для точек u Î U \ int U .
Необходимость доказана.
Достаточность. В силу второго критерия выпуклости достаточно доказать неравенство
Имеем
I '(u ) - I '(v), u - v ³ 0, u , v ÎU .
I '(u ) - I '(v), u - v =
''( v +q ( u - v ) ) ( u - v ), q Î 0,1
6I 4
4 4 7 4 4 48
I '(v + ( u - v ) ) - I '(v) , u - v =

16.

}x
æ 6 4 7w 48 ö }x
= I '' ç v + q (u - v) ÷ (u - v ), u - v = I '' ( w ) x , x ,
ç
÷
è
ø
Где обозначено
q Î 0,1
ÎU
ÎU
w = v + q (u - v) = q u + ( 1 - q ) v Þ w Î U ,
x = u - v Î Rn.
Тогда из условия (10)
искомое
I ''(u )x , x ³ 0,
" u ÎU , x Î R n
( 10 )
получим
( 10 )
I '(u ) - I '(v), u - v = I '' ( w ) x , x ³ 0.
Таким образом, для функции
I
выполнен второй критерий выпуклости
дифференцируемых функций и, следовательно, она выпукла. Теорема доказана.
Пример 10. Определить значения параметров, для которых функция
определенная равенством
I ( x, y, z ) = x 2 + 2axy + by 2 + cz 2
будет выпуклой на всем пространстве
R3.
I : R 3 ® R1 ,

17.

Решение.
Функция
I
дважды непрерывно дифференцируема на всем пространстве
R3.
По теореме 10 для ее выпуклости требуется положительность матрицы
æ 2
ç
I ''( x, y, z ) = ç 2a
ç 0
è
2a
2b
0
0 ö
÷
0 ÷.
2c ÷ø
Вычислим ее главные миноры и выясним, при каких значениях параметров они будут
не отрицательны.
2 0,
2 2a 0
2 2a
2
= 4b - 4a 2 ³ 0, 2a 2b 0 = ( 4b - 4a ) 2c ³ 0.
2a 2b
0 0 2c
Таким образом, искомая область изменения параметров определяется неравенствами
a 2 £ b, c ³ 0.
Например, значения параметров
неравенствам удовлетворяют.
a = 2, b = 5, c = 1
этим

18.

Упражнение. Построить область изменения значений параметров
a
и
b,
для
которых функция
1
I ( x, y ) = éë( 1 - b ) x 2 + 4axy + ( 1 + b ) y 2 ùû
2
2
будет выпуклой на всем пространстве R .
Решение.
æ ( 1 - b ) x + 2ay ö
æ1 - b
I ' ( x, y ) = ç
÷ Þ I '' ( x, y ) = ç
è 2a
è ( 1 + b ) y + 2ax ø
Условия выпуклости функции I :
ì1 - b ³ 0,
ìb £ 1,
Þ í 2
Þ
í
2
2
2
îb + 4a £ 1
î1 - b - 4a ³ 0
ìb £ 1,
ï
b2
Þ í a2
+
£1
ï ( 1 ) 2 12
î 2
-
1
2
2a ö
÷
1+ b ø
b
1
1
2
-1
a