jadan (1)

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

Следующий пример

f(x) =	|2,|	,	−x = ±1,	1,	X = [0, 1]
	x		1 < x <

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

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

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

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

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

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

замкнуты.

Доказательство. Необходимость.Предположим,что последовательность {xk} такова, что xk X и xk → xø.Кроме того,пусть f(xk) ≤ β. Так как f(x) замкнутая функция,то обязательно xø X.Действительно,в противном случае,взяв точки [xk, β + ε], где ε > 0 произвольное число,получили бы: [xk, β+ε] epif и [xk, β+ε] → [øx,β +ε]. Но [øx,β +ε] / epif, что противоречит замкнутости функции f(x).Таким образом, xø X и f(øx) конечно.

Не умаляя общности,можно считать,что f(xk) → µ, где µ ≤ β.В силу конечности значения функции f в точке xø и в силу замкнутости надграфика f(x) должно выполняться неравенство: f(øx) ≤ µ ≤ β.Следовательно, µ конечная величина и,более того, Lβ замкнутое множество.

Достаточность.Пусть все множества уровня замкнуты.Если теперь взять сходящуюся к xø последовательность точек {xk} из X, для которой f(xk) → β, то f(xk) ≤ β+ε для любого ε > 0 и k достаточно больших.Но множество Lβ+ε замкнуто.Отсюда в силу произвольности ε > 0 заключаем,что f(øx) ≤ β.Поэтому,беря последовательность точек [xk, µk] epif, сходящуюся к точке [øx, µø],получаем в силу вышесказанного

µø = lim µk ≥ lim inf f(xk) ≥ f(øx).

k→∞ k→∞

Таким образом, [øx, µø] epif и,стало быть, epi f замкнутое множество.

61

В дальнейшем,как правило,будут рассматриваться лишь замкнутые выпуклые функции и нигде это специальным образом не оговаривается.Обратим внимание,что у замкнутой функции эффективная область может оказаться незамкнутой,например,если взять выпуклую функцию f(x) = 1/x,определенную на положительной части прямой,то для нее domf = {x R : x > 0}.

1.2.2.Дифференциальные критерии выпуклости функций

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

Теорема36. (Критерий 1-го порядка).Пусть f(x) дифференцируемая функция на выпуклом множестве X Rn. Тогда f(x) сильно выпукла на X с константой θ > 0 в том и только том случае,когда

f(x) − f(x0) ≥ fx(x0), x − x0 + θ x − x0 2

(97)

для любых x, x0 X.

Доказательство. Необходимость.Пусть 0 < λ ≤ 1.Согласно определению сильно выпуклой функции

f(λx + (1 − λ)x0) ≤ λf(x) + (1 − λ)f(x0) − θλ(1 − λ) x − x0 2

или

	2	f(λx+(1−λ)x0)−f(x0)
f(x) − f(x0) − θ(1	− λ) x − x0 ≥	λ			=
	=	f(x0+λ(x−x0))−f(x0)			=
		λ
	=	λ fx(x0),x−x0 +o(λ)	=

λ

= fx(x0), x − x0 + o(λλ) .

Отсюда,устремляя λ ↓ 0, приходим к (97).

Достаточность.Пусть для любых x, x0 X выполнено(97).Возьмем x0 = λx1 + (1 − λ)x2, где x1, x2 X, 0 ≤ λ ≤ 1.Согласно(97)имеют место неравенства

f(x1) − f(x0) ≥ fx(x0), x1 − x0 + θ x1 − x0 2,

f(x2) − f(x0) ≥ fx(x0), x2 − x0 + θ x2 − x0 2.

Умножим первое неравенство на λ, а второе на 1 − λ,и сложим их.Учитывая,что x1 − x0 = (1 − λ) (x1 − x2) , x2 − x0 = λ (x1 − x2)

и

λ(1 − λ)2 + (1 − λ)λ2 = λ(1 − λ),

62

получаем

λf(x1) + (1 − λ)f(x2) − f(x0) − θλ(1 − λ) x1 − x2 2 ≥ fx(x0), λ x1 + (1 − λ)x2 − x0 = 0.

Таким образом,выполняется неравенство(83)из определения сильно выпуклой функции.

Так как сильно выпуклая функция при константе θ = 0 превращается просто в выпуклую функцию,то в качестве следствия из теоремы36получаем следующий результат.

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

f(x) − f(x0) ≥ fx(x0), x − x0

(98)

для любых x, x0 X.

Если рассмотреть линейную функцию

g(x) = f(x0) + fx(x0), x − x0 ,

то график этой функции касается графика дифференцируемой функции f(x) в точке x0 (см.рис. **) .Неравенство(98)означает,что f(x) ≥ g(x),т.е.график f(x) лежит выше g(x).

Для сильно выпуклых функций наряду с теоремой36имеет место также следующее утверждение.

Теорема38. Пусть f(x) дифференцируемая функция на выпуклом множестве X Rn. Тогда f(x) сильно выпукла на X с константой θ > 0 в том и только том случае , когда

fx(x) − fx(x0), x − x0 ≥ 2θ x − x0 2

(99)

для любых x, x0 X.

Доказательство. Необходимость.Для доказательства необходимости неравенства(99) можно воспользоваться теоремой34.Имеем

f(x) − f(x0) ≥ fx(x0), x − x0 + θ x − x0 2,

f(x0) − f(x) ≥ fx(x), x0 − x + θ x − x0 2,

Складывая эти два неравенства,приходим к(99).

Достаточность Пусть выполнено(99).По теореме Ньютона-Лейбница

1

f(x) = f(x0) + fx (x0 + α(x − x0)) , x − x0 dα

0

63

для любых x и x0 из X.Поэтому в силу(99)

f(x) − f(x0) − f1x(x0), x − x0 =

=

01

α−1 fx (x0

+ α(x − x0)) − fx(x0), α(x − x0) dα ≥

=

=

0

fx (x0 + α(x

−

x0)) , x

−

x0

dα

−

fx(x0), x

−

x0

1

≥

−

x0)

2dα =

θ

x

−

x0

2.

0 α−12θ α(x

Таким образом,выполняется неравенство(97),которое в силу теоремы36достаточно,чтобы

f(x) была сильно выпуклой функцией с константой θ.

Приведем теперь аналогичный результат для просто выпуклых функций.Он получается

из(99)при θ = 0.

R

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

. Тогда f(x) выпукла на X в том и только том случае , когда

fx(x) − fx(x0), x − x0 ≥ 0

для любых x, x0 X.

Обратимся теперь к дважды дифференцируемым функциям и рассмотрим критерии их

выпуклости и сильной выпуклости.

Теорема40. (Критерий 2-го порядка).Пусть

f(x) дважды непрерывно дифферен-

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

X = . Тогда f(x) сильно

выпукла на X с константой θ > 0 в том и только том случае , когда

y, fxx(x)y ≥ 2θ у 2

(100)

для любых x X и y Rn.

y = 0n,поэтому в дальнейшем

Доказательство. Неравенство(100)тривиально,когда

считаем,что y = 0n.

n

Необходимость.Предположим сначала,что x intX. Тогда x+ αy X для всех y R

и α достаточно малых.Так как

f(x) дважды дифференцируемая функция,то

α2

f(x + αy) = f(x) + α fx(x), y +

y, fxx(x)y + o(α2).

2

Отсюда,на основании теоремы36,получаем

α2

y, fxx(x)y + o(α2) = f(x + αy) − f(x) − α fx(x), y ≥ θα2 y 2.

(101)

2

Неравенство(101)сводится к неравенству(100)после деления левой и правой части на α2 и перехода к пределу при α ↓ 0.

Если x X, но x / intX,то возьмем последовательность {xk} такую,что xk intX и xk → x при k → ∞.Тогда после предельного перехода приходим к(100).

64

Достаточность.Используя формулу	Тейлора с остаточным членом в форме Лагранжа,
а также неравенство(100) ,получаем для	x + y X:

f(x + y) − f(x) − fx(x), y = 12 y, fxx(x + αy)y ≥ θ y 2,

где 0 ≤ α ≤ 1.Поэтому

f(x + y) − f(x) ≥ fx(x), y + θ y 2.

Следовательно,по теореме36,функция f(x) сильно выпукла с константой θ.

В качестве следствия из этой теоремы при θ = 0 получаем следующее утверждение.

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

y, fxx(x)y ≥ 0

(102)

для всех x X и y Rn.

Теорема41дает сравнительно простой критерий проверки выпуклости дважды непрерывно дифференцируемой функции,а именно,достаточно убедиться в том,что ее матрица вторых производных положительно полуопределена на X.

1.2.3.Дифференцируемость по направлениям и субдифференциал

В предыдущем разделе мы дополнительно предполагали,что выпуклая функция является дифференцируемой,чтобы получить условия(98)и(102).Однако,выпуклость-это такое замечательное свойство,что оно само по себе обеспечивает некоторую гладкость функции, а именно,ее дифференцируемость по направлениям.

Лемма10. Пусть f(x) выпуклая функция на выпуклом множестве X Rn и x0 riX. Тогда для любого ненулевого направления s LinX, функция

ψ(α) =	f(x0 + αs) − f(x0)	(103)
	α

является неубывающей на множестве

A+ = {α > 0 : x0 + αs X} .

Кроме того, ψ(α1) ≥ ψ(α2) для всех α1 A+ и α2 A−, где

A− = {α < 0 : x0 + αs X} .

Доказательство. Прежде всего отметим,что множество A+ заведомо непустое,поскольку x0 riX и s LinX.Имеем ∆ε(x0) ∩a X X для достаточно малого ε > 0. Кроме

65

того, x0 + αs a X для всех α R.Поэтому x0 + αs ∆ε(x0) ∩a X X при α достаточно малом.По той же самой причине множество A− также непустое.

Проверим сначала,что функция ψ(α) является неубывающей на A+ Пусть α1 A+, α2 A+ и α1 ≤ α2.Обозначим λ = α1/α2 Имеем 0 < λ ≤ 1.Поэтому в силу выпуклости функции f(x):

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

Следовательно,

ψ(α	) = α−1		[f(x + α			s)		−		f(x )]		≤
1		1	[(1	0	1						0					f(x )] =
	≤	α−1		−	λ) f(x			) + λf (x				0	+ α s)		−
		1				0							2			0
	= α−1		λ [f(x + α				s)		−		f(x )] =
		1			0	2					0			).
	= α−1		[f(x + α			s)		−		f(x )] = ψ(α
		2		0	2						0		2

Таким образом, ψ(α) неубывающая на A+ функция. Возьмем теперь любые α1 A+, α2 A− и обозначим

	λ1	=		α1	, λ2 =	−α2	.
			α1	− α2
						α1 − α2

Имеем λ1 > 0, λ2 > 0 и λ1 + λ2 = 1. Так как

x0 = λ1(x0 + α2s) + λ2(x0 + α1s),

то в силу выпуклости функции f(x):

f(x0) =	f (λ1(x0 + α2s) + λ2(x0 + α1s)) ≤
≤	λ1f(x0 + α2s) + λ2f(x0 + α1s).

Откуда,если переписать данное неравенство как

(λ1 + λ2) f(x0) ≤ λ1f(x0 + α2s) + λ2f(x0 + α1s),

получаем

λ1 [f(x0 + α2s) − f(x0)] ≥ −λ2 [f(x0 + α1s) − f(x0)]

или

α1 [f(x0 + α2s) − f(x0)] ≥ α2 [f(x0 + α1s) − f(x0)] .

Поэтому после деления данного неравенства на α1α2 < 0 приходим к выводу,что ψ(α1) ≥

ψ(α2).

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

	лению s LinX:		f(x0	+ αs) − f(x0)
	f (x0	; s) = lim			.	(104)
		α↓0		α

66

= f 2 12 x1 + 12 x2

≤ f(x1) + f(x2),

Кроме того, f (x0; s) ≤ ψ(α) для всех достаточно малых α > 0, где ψ(α) функция (103).

Доказательство. Согласно лемме10функция ψ(α),имеющая вид(103),является неубывающей и ограниченной снизу на множестве A+.Поэтому существует предел ψ(α) при α ↓ 0,который и есть f (x0; s).Справедливость неравенства f (x0; s) ≤ ψ(α) следует опять же из-за монотонности функции ψ(α).

Замечание1. Если функция f(x) дифференцируема в точке x0, то , как известно из анализа,ее производная по любому направлению s Rn существует и имеет место формула:

f (x0; s) = fx(x0), s ,

(105)

где fx(x0) градиент функции f(x) в точке x0.

Рассмотрим вопрос о поведении производной по направлению f (x0; s), как функции

второго аргумента s. Напомним , функцияf(x) называется положительно однородной,если f(λx) = λf(x) для λ > 0.Выпуклые положительно однородные функции удовлетворяют условию:

f(x1 + x2) = 2f 12 x1 + 12 x2 ≤

из которого,полагая в частности, x1 = 0n, x2 = x,получаем: f(x) ≤ f(0n)+f(x) или f(0n) ≥ 0.Для замкнутых выпуклых положительно однородных функций обязательно f(0n) = 0, поскольку в этом случае справедливо и противоположное неравенство.

f(0n) ≤	lim f(λx) = lim λf(x) = f(x) lim λ = 0.
	λ 0	λ	0	λ 0
	↓	↓		↓

Теорема43. Пусть f(x) выпуклая функция на выпуклом множестве X Rn и пусть x0 riX. Тогда f (x0; s) есть положительно однородная функция от второго аргумента s на множествеLin X.

Доказательство. Положительная однородность функции f (x0; s) по s следует непосредственно из определения(40),так как

f (x0	; λs) = lim	f(x0 + αλs) − f(x0)	= λ lim	f(x0 + αλs) − f(x0)	= λf (x0; s).
	α↓0	α	α↓0	(αλ)

Далее,в силу выпуклости функции f(x) для λ1 ≥ 0, λ2 ≥ 0, λ1 + λ2 = 1 и s1LinX, s2 Lin выполняется

f(x0+α(λ1s1+λ2s2))−f(x0)

=

α

=

f(λ1(x0+αs1)+λ2(x0+αs2))−(λ1+λ2)f(x0)

≤

α

≤

λ

1

f(x0+αs1)−f(x0)

+ λ

2

f(x0+αs2)−f(x0

= λ

f (x

; s

) + λ

f (x ; s ).

α

α

1

0

1

2

0 2

67

Отсюда после перехода к пределу по α ↓ 0 получаем

f (x0; λ1s1 + λ2s2) ≤ λ1f (x0; s1) + λ2f (x0; s2).

Таким образом f (x0; s) выпукла по s.

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

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

Определение36. Пусть f(x) функция,определенная на множестве X Rn. Тогда вектор a Rn называется субградиентом функции f(x) в точке x0 X, если

f(x) − f(x0) ≥ a, x − x0 x X.

(106)

Множество всех субградиентов функции f(x) в точке x0 называется ее субдифференциалом в x0 и обозначается ∂X f(x0). Если множество X совпадает со всем пространством Rn,то будем просто писать ∂f(x0).

Здесь понятия субградиента и субдифференциала введены для произвольной функции f(x) и произвольного множества X.Однако наиболее содержательны они для выпуклых функций.Так,согласно теореме37,если выпуклая функция f(x) дифференцируема в точке x0,то для нее

f(x) − f(x0) ≥ fx(x0), x − x0 x X.

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

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

иточка x0 riX. Тогда :

1.Если f(x) выпуклая функция на X, то ∂X f(x0) = и ∂X f(x0) является выпуклым замкнутым множеством;

2.Если ∂X f(x) = для всех x X, то f(x) выпуклая функция на X.

Доказательство. Докажем сначала первое утверждение.Пусть f(x) выпуклая функция на X.Рассмотрим ее надграфикepi f,которое является выпуклым множеством и возьмем точку [x0, f(x0)] epi f. Понятно , что[x0, f(x0)] / ri(epi f).Тогда по теореме15точка [x0, f(x0)] собственно отделима отepi f,т.е.существуют [a,α ] Rn+1,не равные нулевому вектору в совокупности,и такие,что

[a,α ], [x, µ] ≥ [a,α ], [x0, f(x0)]

(107)

68

для всех [x, µ] epi f.А также можно указать такое [øx, µø] epi f, что
[a,α ], [øx, µø] > [a,α ], [x0, f(x0)] .	(108)
Если α = 0, то a = 0n и неравенства(107)и(108)переходят в соответственно	a, xø >
a, x0 и
a, x ≥ a, x0 x X.

Но это означает,что точка x0 riX собственно отделима от X,что быть не может. Предположим теперь,что α = 0.Тогда обязательно α > 0,так как,если α < 0, то ,

устремляя µ → +∞,приходим к нарушению неравенства(107).Положим,не умаляя общности, α = 1.Неравенство(107)в этом случае перепишется как

a, x + µ ≥ a, x0 + f(x0) x X, µ ≥ f(x).

В частности,беря µ = f(x),получаем

f(x) − f(x0) ≥ −a, x − x0 x X.

Откуда следует,что −a ∂X f(x0).Таким образом,субдифференциал ∂X f(x0) не является пустым множеством.Его замкнутость и выпуклость следует непосредственно из определения36субдифференциала.

Докажем теперь второе утверждение.Пусть точки x1 X, x2 X произвольны и пусть

0 ≤ λ ≤ 1. Положим x = λx1 + (1 − λ)x2. Так как x X и ∂X f(x) = ,то существует a ∂X f(x),для которого

f(x1) − f(x) ≥ a, x1 − x , f(x2) − f(x) ≥ a, x2 − x .

Умножим первое неравенство на λ, второе на 1 − λ,и сложим

λf(x1) + (1 − λ)f(x2) − f(x) ≥ λ a, x1 − x + (1 − λ) a, x2 − x = = λ a, x1 − λx1 − (1 − λ)x2 +

+ (1 − λ) a, x2 − λx1 − (1 − λ)x2 =

= λ(1 − λ) a, x1 − x2 − λ(1 − λ) a, x1 − x2 = 0.

Таким образом,

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

Следовательно, f(x) выпуклая функция на X.

Можно дополнительно показать,что в случае,когда выпуклое множество X обладает непустой внутренностью,субдифференциал ∂X f(x) выпуклой функции f(x) в любой точке x intX оказывается ограниченным множеством.

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

69

Доказательство. Замкнутость и выпуклость f(x) следует из предыдущей теоремы.

Поэтому остается			доказать только ограниченность ∂X f(x0).Пусть				a ∂X f(x0) и пусть
a = 0	n. Так как	x	intX,то можно указать ε > 0 такое,что ∆			(x	) = x + εB		X, где B
		0		n	ε	0	0
единичный шар			в R		с центром в нуле.Обозначим f = maxx ∆ε (x0).Из непрерывности

выпуклой функции f(x) на ∆ε(x0) следует,что максимум достигается и f ≤ +∞. Согласно определению субградиента для любого x X выполняется неравенство a, x−

x0 ≤ f(x) − f(x0).В частности,беря x = x0 + ε a −1a ∆ε(x0),получаем

f(x0 + ε a −1a) − f(x0) ≤ a, x − x0 = ε a .

Отсюда,поскольку f(x0 + ε a −1a) ≤ f получаем: a ≤ ε−1(f −f(x0)) < +∞,что в силу произвольности субградиента a означает ограниченность ∂X f(x0).

Если взять выпуклую функцию f(x) = |x|,определенную на действительной прямой R, то для нее субдифференциал ∂f(0) совпадает с отрезком [−1, 1].Во всех остальных точках

Rданная функция дифференцируема.

Вотносительно граничных точках множества X субдифференциал может быть пустым. Приведем пример такой функции

f(x) = − 1 − x2, X = [−1, 1] R.

В точках ±1 касательные к графику выпуклой функции f(x) принимают вертикальное положение.

Можно привести также пример выпуклой функции,у которой субдифференциал в граничных точках множества X не пуст.Пусть δ(x|X) индикаторная функция непустого выпуклого замкнутого множества X Rn и пусть x0 X.Согласно определению,вектор a Rn будет субградиентом δ(x|X) в точке x0,если

a, x − x0 ≤ δ(x|X) − δ(x0|X) = 0 x X.

(109)

О векторе a,удовлетворяющем неравенству(109),говорят как о нормали к множеству X в точке x0.Совокупность всех нормалей в точке x0 X образует конус,называемый нормальным конусом к X в этой точке и обозначаемый N (x0|X).Таким образом,субдифференциал индикаторной функции множества X в граничной точке x0 X совпадает с нормальным конусом N (x0|X) к X в этой точке.

Рассмотрим теперь связь между производными выпуклой функции по направлениям и ее субградиентами.

Теорема46. Пусть f(x) выпуклая функция на выпуклом множестве X Rn. Пусть,кроме того, x0 riX. Тогда :

1. имеет место следующая формула для субдифференциала:
∂X f(x0) = a Rn : a, s ≤ f (x0; s) s LinX, s = 0n ;	(110)

70