jadan (1)

Определение30. Функция f(x),определенная на выпуклом множестве X Rn, называется выпуклой на X, если

f (λx1 + (1 − λ)x2) ≤ λf(x1) + (1 − λ)f(x2)

(82)

для любых x1 X, x2 X и 0 ≤ λ ≤ 1.

Если неравенство(82)выполняется как строгое для всех x1 X, x2 X, x1 = x2 и

0 < λ < 1, то f(x) называется строго выпуклой функций на X.
Определение31. Функция f(x),определенная на выпуклом множестве	X Rn,
называется сильно выпуклой на X с константой θ > 0, если
f (λx1 + (1 − λ)x2) ≤ λf(x1) + (1 − λ)f(x2) − θλ(1 − λ) x1 − x2 2	(83)

для любых x1 X, x2 X и 0 ≤ λ ≤ 1.

Сильно выпуклую на X функцию с константой θ > 0 будем называть просто сильно выпуклой,если точное значение положительной константы θ для нас не существенно.Сильно выпуклая функция всегда является строго выпуклой функцией,а та,в свою очередь,просто выпуклой функцией.

Определение32. Функция f(x),определенная на выпуклом множестве X Rn, на - зывается вогнутой(строго,сильно)на X, если −f(x) является выпуклой(строго,сильно) функцией на X.

В дальнейшем будут рассматриваться в основном выпуклые функции,все результаты, касающиеся этих функций,полностью переносятся на вогнутые функции с соответствующими изменениями.Непосредственно из определений30и32следует,что любая линейная (точнее, аффинная) функция f(x) = aT x + b, где a Rn, b R,является одновременно и выпуклой и вогнутой функцией.Это единственный класс функций,обладающий данным свойством.

Приведем простейшие примеры выпуклых функций,область определения которых принадлежит действительной прямой R:

1.f(x) = xp, p ≥ 1, X = R+;

2.f(x) = |x|p, p ≥ 1, X = R;

3.f(x) = ecx, c R, X = R;

4.f(x) = − ln x, X = R++;

5.f(x) = x ln x, X = R++.

51

Все эти функции строго выпуклы на соответствующем множестве X,первая и вторая функции при p = 2 оказываются даже сильно выпуклыми.Последнюю функцию f(x) = x ln x называют отрицательной энтропией.Обычно ее доопределяют в точке x = 0, полагая f(0) = 0.

Из других часто встречающихся выпуклых функций укажем произвольные нормы в Rn,

в частности,гельдеровские нормы:
x p =	n	|xi|p 1/p , 1 ≤ p < ∞,	(84)
	i
	=1

а также их предельный случай чебышевскую норму:

x ∞ = max {|x1|, |x2|, . . . , |xn|} .

(85)

Как нормы,функции(84), (85)не только выпуклы,но и положительно однородны,т.е.

f(λx) = λf(x), когда λ ≥ 0.Примером сильно выпуклой функции на всем пространстве Rn является квадратичная функция f(x) = x, Ax , где A симметричная положительно определенная матрица.

При проверке выпуклости функции f(x) на выпуклом множестве X может оказаться полезным следующее простое утверждение.

Утверждение13. Функция f(x) выпукла на выпуклом множестве X Rn тогда и только тогда,когда функция одного аргумента φ(α) = f(x + αs) выпукла по α на множестве Ax,s = {α R : x + αs X} для любого x X и любого ненулевого s Rn.

R	n	Доказательство. Необходимость.Предположим,что точка x X и направление s
		таковы что множество Ax,s состоит более,чем из одной точки,т.е. Ax,s либо отрезок,

либо луч,либо прямая.Возьмем две точки α1 Ax,s, α2 Ax,s, α1 < α2.Тогда для любого 0 ≤ λ ≤ 1 имеем αλ Ax,s, где αλ = λα1 + (1 − λ)α2 .Кроме того,в силу выпуклости функцииf(x)

φ(αλ) = f(x + αλs) = f (λ(x + α1s) + (1 − λ)(x + α2s)) ≤

≤ λf(x + α1s) + (1 − λ)f(x + α2s) = λφ(α1) + (1 − λ)φ(α2).

Таким образом,функция φ(α) выпукла на Ax,s.

Достаточность.Возьмем две произвольные отличные друг от друга точки x1 и x2 из X.Тогда направление s = x2 − x1 ненулевое и множество Ax,s состоит более,чем из одной точки.Беря в качестве x точку x1,получаем: f(x1) = φ(0), f(x2) = φ(1).Кроме того,имеем в силу выпуклости функции φ(α) на Ax,s для произвольного 0 ≤ λ ≤ 1:

f(λx1 + (1 − λ)x2) = f (x1 + (1 − λ)(x2 − x1)) =

=f (x + 0 á s + (1 − λ)s) =

=f (x + (λ á 0 + (1 − λ) á 1) s) =

=φ(λ á 0 + (1 − λ) á 1) ≤ λφ(0) + (1 − λ)φ(1) =

=λf(x1) + (1 − λ)f(x2).

52

Таким образом, f(x) выпуклая функция на X.

Обозначим через Λm вероятностный симплекс в пространстве Rm,т.е.множество

Λm =	λ R+n : λi = 1 .
	m
	i
	=1

Теорема30. Пусть f(x) выпуклая функция на выпуклом множестве X Rn и пусть xi X, 1 ≤ i ≤ m, произвольные точки из X. Тогда

f	m	λixi ≤	m	λif(xi)	(86)
			i
	i=1		=1

для любого λ = [λ1, . . . , λm] Λm.

Доказательство. Прежде всего отметим,что точка m λixi,как выпуклая комбина-

i=1

ция точек из выпуклого множества X,принадлежит X.

Доказательство будем проводить по индукции.При m = 1 утверждение очевидно,а при m = 2 следует из определения выпуклой функции.Предположим,что оно верно для для всех m вплоть до m = k и докажем его для m = k + 1.Пусть λ Λk+1 и

При этом считаем,что ранее случаям.Тогда

где

x = k+1 λixi = k λixi + λk+1xk+1. i=1 i=1

0 < λk+1 < 1,так как иначе все сводится к уже рассмотренным

x = λk+1xk+1 + 1 − λk+1 x,ø

k		−
i
		λi
xø =	γixi, γi =	1 λk+1	≥ 0, 1 ≤ i ≤ k.
=1

Так как λ Λk+1, то γ = [γ1, . . . , γk] Λk.Поэтому				xø X и в силу выпуклости функции
f(x) и предположения индукции
f		k+1
		i=1 λixi	= f λk+1 + (1 − λk+1)øx ≤

≤λk+1f(xk+1) + (1 − λk+1

≤λk+1f(xk+1) + (1 − λk+1

k+1 λif(xi).= i=1

)f(øx) ≤

) k γif(xi) =

i=1

Таким образом,неравенство(86)выполняется и при m = k + 1.

53

Неравенство(86)носит название неравенства Йенсена.Из него в частных случаях могут быть получены многие известные неравенства,например, неравенство между арифметическим и геометрическим средним,которое для двух переменных имеет вид:

√

(a

+ b)/2,

(87)

ab ≤

где a, b

≥

0.Продемонстрируем его вывод с помощью выпуклой функции

−

ln x. Полагая

λ

1

= λ

2

= 1/2,получаем согласно(86)

≤

−

2−

− ln

a 2

.

+ b

ln a

ln b

Беря экспоненту от левой и правой части этого неравенства,приходим к(87).

Рассмотрим теперь некоторые операции над выпуклыми функциями,которые сохраняют выпуклость.Нетрудно проверить(проверьте это),что имеет место следующий результат

Теорема31. Пусть f1(x), . . ., fm(x) выпуклые функции на выпуклом множестве X Rn и αi ≥ 0, 1 ≤ i ≤ m. Тогда следующие две функции

	m
	i
f(x) =	αifi(x),
	=1
f(x) =	max fi(x)	(88)
	1≤i≤m

выпуклы на X.

Из утверждения теоремы31,в частности,следует,что операция умножения выпуклой функции на неотрицательную константу оставляет ее выпуклой.Точно также,сумма двух выпуклых функций,определенных на одном и том же выпуклом множестве X,также будет выпуклой функцией на X.Вообще говоря,выпуклые функции на выпуклом множестве X образуют конус в пространстве всех функций,определенных на X.Имеются и другие операции над выпуклыми функциями,которые сохраняют их выпуклость.Некоторые из них будут рассмотрены несколько ниже.

Согласно теореме31,так называемая кусочно-линейная функция (точнее, кусочно-аффинная функция)

n

1

1

m

n

R

n, bi

R

≤

≤

f(x) = max

aT x + b

, . . . , aT x + bm

,

ai

, 1

i

m,

(89)

выпукла на R .При этом все пространство

R разбивается на m или меньшее число обла-

стей,на каждом из которых функция

f(x) линейна.Частным случаем кусочно-линейной

функции(89)является следующая выпуклая функция на

Rn:

f(x) = max {x1, . . . , xn} .

54

Суперпозиция f(x) = g(h(x)) двух выпуклых функций g(y) и h(x),определенных соответственно на R и Rn,при дополнительном требовании монотонности первой функции дает опять выпуклую функцию на Rn. Напомним , функцияg(y) называется неубывающей на R,

если g(y1) ≤ g(y2) для всех y1 < y2.Если же g(y1) ≥ g(y2) для y1 < y2, то такая функция g(y) называется невозрастающей на R.

Утверждение14. Пусть g(y) и h(x) выпуклые функции соответственно на R и Rn.Пусть,кроме того, g(y) неубывающая функция на R. Тогда функция f(x) = g(h(x)) выпукла на Rn.

Доказательство. Возьмем произвольные x1 Rn, x2 Rn и 0 ≤ λ ≤ 1.Обозначим xλ = λx1 + (1 − λ)x2.В силу выпуклости функции h(x) выполняется неравенство

h(xλ) ≤ λh(x1) + (1 − λ)h(x2).

Но внешняя функция g(y) является неубывающей и выпуклой R.Поэтому

f(xλ) = g(h(xλ)) ≤ g(λh(x1) + (1 − λ)h(x2)) ≤

≤ λg(h(x1)) + (1 − λ)g(h(x2)) = λf(x1) + (1 − λ)f(x2).

Таким образом, f(x) выпуклая функция на Rn.

Приведенное утверждение,является одним из простейших вариантов целой серии утверждений относительно выпуклости суперпозиций двух функций.Можно,например,ослабить условие,которое требует,чтобы функции g(y) и h(x) были определены на всем пространстве.Более того,можно даже не требовать,чтобы внутренняя функция h(x) была бы выпуклой.Анализ доказательства утверждения14показывает,что справедлив также следующий результат.

Утверждение15. Пусть g(y) выпуклая невозрастающая функция на R, а h(x) вогнутая функция на Rn. Тогда функция f(x) = g(h(x)) выпукла на Rn.

Используя утверждение14,а также некоторое обобщение утверждения15,получаем, что следующие две функции являются выпуклыми:

1.f(x) = eh(x), X = Rn;

2.f(x) = − ln(−h(x)), X = {x Rn : h(x) < 0}.

Здесь h(x) выпуклая на Rn функция.

Рассмотрим далее два важных выпуклых множества,которые связаны с выпуклыми функциями.

Эпиграф функции.Напомним определение эпиграфа функции.

Определение33. Пусть функция f(x) определена на множестве X Rn. Тогда множество

epi f = {[x, µ] X × R : µ ≥ f(x)}

55

называется эпиграфом или надграфиком функции f(x).

Теорема32. Для того,чтобы функция f(x),определенная на выпуклом множестве X, была выпуклой на X, необходимо и достаточно , чтобы epif был выпуклым множеством.

Доказательство. Необходимость.Пусть функция f(x) выпукла на X.Возьмем две произвольные точки [x1, µ1] epi f и [x2, µ2] epi f.Возьмем также 0 ≤ λ ≤ 1 и обозначим xλ = λx1 + (1 − λ)x2, µλ = λµ1 + (1 − λ)µ2. Тогда

λ[x1, µ1] + (1 − λ)[x2, µ2] = [xλ, µλ].

Из выпуклости множества X следует,что xλ X.Кроме того,поскольку f(x) выпуклая функция,

f(xλ) ≤ λf(x1) + (1 − λ)f(x2) ≤ λµ1 + (1 − λ)µ2 = µλ.	(90)
Неравенство(90)показывает,что [xλ, µλ] epi f.Таким образом,множествоepi	f является
выпуклым.

Достаточность.Пустьepi f выпуклое множество.Тогда из [x1, µ1] epi f, [x2, µ2]

epi f следует,что [xλ, µλ] = λ[x1, µ1] + (1 − λ)[x2, µ2] epif для любого 0 ≤ λ ≤ 1,т.е. f(xλ) ≤ µλ = λµ1 + (1 −λ)µ2.Но это верно для любых µ1 ≥ f(x1) и µ2 ≥ f(x2),в частности, при µ1 = f(x1), µ2 = f(x2).Отсюда приходим к неравенству

f(xλ) = f (λx1 + (1 − λ)x2) ≤ λf(x1) + (1 − λ)f(x2).

Поскольку точки x1 X и x2 X были взяты произвольно,то f(x) выпуклая функция на X.

Операция пересечение эпиграфов двух выпуклых функций f1(x) и f2(x),определенных соответственно на множествах X1 и X2,приводит опять к выпуклому множеству,которое является эпиграфом функции

f(x) = max {f1(x), f2(x)} .

Данная функция имеет вид функции(88)и определена на множестве X = X1 ∩ X2.

Но пересекая не только два,а произвольное конечное или бесконечное число выпуклых множеств,мы опять получаем выпуклое множество.Поэтому,если функция двух аргументов g(x, y) выпукла по x Rn для любого y Y Rm,то следующая функция

f(x) = sup g(x, y)	(91)
y Y

также выпукла по x.

Более того когда функция двух аргументов g(x, y) выпукла одновременно относительно обоих переменных и Y непустое выпуклое множество,то наряду с(91)функция

f(x) = inf g(x, y)	(92)
y Y

56

выпукла по x при условии,что f(x) принимает конечное значение по крайней мере для одного x.Чтобы проверить это,возьмем x1 X и x2 X, где X область определения функции f(x).Тогда для произвольного ε > 0 можно указать y1 Y и y2 Y такие,

что f(xi) ≤ g(xi, yi) + ε, i = 1, 2.Беря 0 ≤ λ ≤ 1 и обозначая xλ = λx1 + (1 − λ)x2, yλ = λy1 + (1 − λ)y2,имеем последовательно

f(xλ) =	infy Y g(xλ, y) ≤ g(xλ, yλ) ≤
≤	λg(x1, y1) + (1 − λ)g(x2, y2) ≤ λf(x1) + (1 − λ)f(x2) + ε.

Отсюда в силу произвольности ε > 0 заключаем,что функция f(x) выпукла на X. Из при - веденного доказательства видно,что если функция g(x, y) сильно выпукла,то и функция f(x) оказывается сильно выпуклой.

Эпиграф функции f(x) есть проекция эпиграфа функции g(x, y) на соответствующее подпространство,а именно,

epi f = {[x, µ] : [x, y, µ] epi g для некоторого y Y } .

Так какepi g выпуклое множество,то и его проекция также является выпуклым множеством.Область определения X функции f(x) совпадает с проекцией области определения функции g(x, y) на подпространство первой переменной x.

В качестве следствия получаем,что функция расстояния до непустого выпуклого множества X Rn

ρ(x|X) = ρmin(x|X) = infy X x − y ,

где á норма в Rn,выпукла на Rn. Функция же расстояния до наиболее удаленной

точки множества X

ρmax(x|X) = supy X x − y ,

всегда выпукла,даже в случае отсутствия выпуклости у множества X.

Используя функцию вида(92),можно убедиться в справедливости условия(73).Действительно,пусть имеется положительно определенная блочная матрица

BT	C	,
A	B

где A и C симметричные матрицы,матрица C положительно определена.Тогда,если ввести функцию двух аргументов

то она является y = y(x) = −C−1

g(x, y) = x, Ax + y, Cy + 2 x, By ,

сильно выпуклой.Ее минимум по y достигается в единственной точке BT x и после подстановки приходим к квадратичной функции

f(x) = g(x, y(x)) = x, (A − BC−1BT )x ,

57

которая также сильно выпукла.Поэтому матрица A − BC−1BT ,называемая дополнением по Шуру матрицы C,должна быть положительно определенной.

Множество подуровня.Обратимся теперь ко второму важному множеству(вернее, семейству множеств),связанному с выпуклыми функциями,а именно,к множеству подуровня.Напомним его определение.

Определение34. Пусть f(x) функция,определенная на множестве X. Тогда мно - жество

Lβ = {x X : f(x) ≤ β}

называется множеством Лебега или множеством подуровня функции f(x).

Нетрудно видеть,что если f(x) выпуклая функция,определенная на выпуклом множестве X,то для любого β множество Лебега Lβ выпукло.

Теорема33. Пусть f(x) непрерывная сильно выпуклая функция с константой θ, определенная на замкнутом выпуклом множестве X. Тогда для любого β множество подуровня Lβ ограничено.

Доказательство. Если множество Lβ пусто,то утверждение теоремы тривиально. Предположим теперь,что множество Lβ не пусто.Возьмем произвольную точку x0 Lβ. Пусть ∆1(x0) шар единичного радиуса с центром в точке x0.В силу непрерывности f(x) и замкнутости X существует такое α R, что f(x) ≥ α для всех x X ∩ ∆1(x0).Для значения f(x0) функции f(x) согласно определению величин α и β выполняются неравенства

α ≤ f(x0) ≤ β.

Покажем,что

	x	−	x	0 ≤	1 +	β − α		x	Lβ	.	(93)
						θ
Данное неравенство очевидно,если точка						x Lβ	такова,что				x ∆1(x0).Далее будем

предполагать,что x Lβ \ ∆1(x0). Тогда x − x0 > 1. Положим λ = x − x0 −1 < 1 и рассмотрим точку xø = λx + (1 − λ)x0.В силу выпуклости множества Lβ точка xø Lβ.

Имеем

xø =		1		x + 1 −			1				x0 =
	x	x0					x−x0
=		−1		[x + (	x		x0				1) x0] .
	x−x0
						−		−

Откуда

1

xø − x0 = x − x0 x + ( x − x0 − 1)x0 − x − x0 x0 = 1.

Таким образом,точка xø принадлежит границе единичного шара ∆1(x0).Поэтому с учетом сильной выпуклости функции f(x) получаем

α ≤

)f(x )

−

θλ(1

−

λ)

x

−

x

0

2

≤

f(øx) ≤ λf(x) + (1 − λ2

0

≤ β − θλ(1 − λ) x − x0

=

x − x0 2 =

.

= β − θ x − x0 −2 ( x − x0 − 1)

=

β − θ ( x − x0 − 1) .

58

Отсюда приходим к требуемому неравенству(93),из которого следует,что множество Lβ ограничено.

При определении выпуклых функций все время оговаривалось,что они заданы на выпуклом множестве X.Существует также другой подход к описанию выпуклых функций,а именно,считается,что они заданы на всем пространстве Rn и при этом могут принимать значения ±∞,операции с которыми(сложение и умножение на ноль и на бесконечные числа)подчинены специальным правилам.При таком соглашении функции вида f(x) ≡ +∞ или f(x) ≡ −∞ также оказываются выпуклыми.Чтобы выделить множество точек,в которых значения функции f(x) отличны от +∞, вводят понятие эффективной области функции,определяемой следующим образом

domf = {x Rn : f(x) < +∞} .

У выпуклых функций их эффективная область всегда выпукла.

Те выпуклые функции f(x),которые не принимают значение −∞ и не равны тождественно +∞,называются собственными.В противном случае они называются несобственными.Важным примером собственной выпуклой функции является индикаторная функция непустого выпуклого множества X Rn:

δ(x|X) =	+∞,	x / X.
	0, x	X,

Примером несобственной выпуклой функции на R,не равной тождественно +∞,является следующая функция

	1, x = 0 или x = 1,
f(x) = −∞, x (0, 1),

+∞, x / [0, 1].

Вдальнейшем мы будем рассматривать только собственные выпуклые функции.Более того, при их задании,как правило,будем придерживаться первого подхода,т.е.оговаривать то множество,на котором данная выпуклая функция определена и принимает конечные значения,т.е.,говоря другими словами,ее эффективную область.

Свойство выпуклости функций приводит к тому,что такие функции обладают многими дополнительными важными свойствами,например,они являются непрерывными функциями на относительных внутренностях своих областей определения(эффективных областей), а разрывы лишь на относительной границе этих областей.

Теорема34. Пусть f(x) выпуклая функция на выпуклом множестве X Rn. Тогда f(x) непрерывна в любой точке x riX.

Доказательство. Доказательство проведем при упрощающих предположениях,что intX = .Считаем также,не умаляя общности,что 0n intX и f(0n) = 0.Выполнения последних двух предположений всегда можно добиться заменой переменной y = x−x0, где x0 intX,и добавлением константы к функции.Эти преобразования соответствуют

59

сдвигу надграфика функции f(x) в n + 1-мерном пространстве и фактически не меняют ее вид.

Обозначим через ∆δ(0n) окрестность начала координат,определяемую с помощью первой гельдеровской нормы

∆1(0n) = {x Rn : x 1 ≤ δ} .

Эта окрестность является выпуклым многогранником,натянутым на		2n точек xj,δ Rn,
имеющими вид: xj,δ = ±δei, где ei i-й единичный орт, 1 ≤ i ≤ n.
Так как 0n intX,то можно указать такое	ø
	δ > 0, что ∆δø(0n) X.Пусть
c = max	f(x ø).
1≤j≤2n	j,δ
ø
Если взять произвольное 0 < δ < δ,то из выпуклости функции f(x) получаем
f (xj,δ) = f δxj,δø = f δxj,δø + (1 − δ)0n ≤ δf xj,δø ≤ δc,		1 ≤ i ≤ 2n.	(94)

Поскольку окрестность ∆δ(0n) есть выпуклый многогранник,порожденный точками xj,δ, то любая точка x из этой окрестности представима в виде выпуклой комбинации точек xj,δ, 1 ≤ 1 ≤ 2n.Поэтому в силу неравенства Йенсена и(94)

f(x) = f

2n

λjxj,δ ≤

2n λjf (xj,δ) ≤ δc,

(95)

j

=1

j=1

где λj ≥ 0, 1 ≤ j ≤ 2n, и

2n

j=1 λj = 1.

∆

(0

) наряду с точкой x также содержит

того,что окрестность

С другой стороны,из

δ

n

также и точку −x,получаем

2 (−x) ≤ 2 f(x) + 2 f(−x) ≤

2 f(x) +

2 δc.

0 = f(0n) = f

2 x +

1

1

1

1

1

1

Откуда

f(x) ≥ −δc.

(96)

ø

Из(95)и(96)видно,что какое бы

ε > 0 мы ни взяли,за счет выбора

можно

0 < δ ≤ δ

добиться того,что |f(x)| ≤ ε для всех x ∆δ(0n).Но это и означает,что функция

f(x)

непрерывна в нуле.

Еслиint X = ,то следует обратиться кri X,которое согласно утверждению теоремы8 обязательно непустое множество.По-прежнему,не ограничивая общности,можно считать, что 0n riX и f(0n) = 0.При этом предположенииri X = LinX и рассмотрение на функции f(x) на всем пространстве Rn следует заменить на ее рассмотрение на подпространстве Lin.Взяв в этом подпространстве соответствующий ортонормированный базис,задаваемый столбцами матрицы Q и сделав соответствующую замену переменных x = Qy,получаем вместо f(x) выпуклую функцию f÷(y) = f(Qy).Выпуклое множество Y ,на котором эта

60