ВОЕНЫ АЛЛАХА1АЗАЗАЗАЗ / 3_Выпуклые функции_сент_9_2008

20	О.А. Кашина, А.И. Кораблев

3. Выпуклые функции

Определение 1. Функция

f

, определенная на

E	n	, называется
любого			t 0, 1

выпуклой, если для любых выполняется неравенство

x, y

и

						t
f		t x 1 t		y

f		x		1 t		f

y

.

(1)

Если при

x y

и

t

	0,1

неравенство (1)

выполняется как строгое, то функция вается строго выпуклой.

f

назы-

		Определение 2. Функция			f	, определенная на
E	n	, называется вогнутой (строго вогнутой), если
функция			f	является выпуклой (строго выпуклой).

Очевидно, что любая строго выпуклая (строго вогнутая) функция является выпуклой (вогнутой) функцией, но не наоборот.

Приведем некоторые операции допустимые в классе выпуклых функций.

Теорема 1. Пусть все функции

f	i

,

i 1, ...,

m

,

выпуклы

m f i i 1

	на	E	n	,	числа	i	0 .
fi	также				выпукла.

Тогда функция

Доказательство. Пусть заданы векторы x, y

и число	t 0, 1 . Так	как функции	fi , i 1, ..., m ,
выпуклы,	то для всех	i выполняются неравенства
fi t x 1 t y t fi x 1 t fi y .			Умножая эти

Методы оптимизации: Часть I

21

неравенства на	неотрицательные величины
суммируя их	по	i , получим неравенство

	i

и

m

i

m

i

m

i

f

y

t

i

f

x

i

t x 1 t

1 t

i 1

i 1

i 1

fi

y

.

Следовательно, f t x 1 t Что и требовалось.

Теорема 2. Пусть на

y
E	n

t f x 1 t f y .

определены функции

fi , i 1, ..., m ,

f x

	max f	i
	1 i m

x

. Если все

fi – вы-

пуклые, то функция f также выпуклая.

	Доказательство.				Пусть заданы векторы			x, y
и	число	t 0,1 . Так			как функции	fi	выпуклы,
то	для	всех	i	выполняются неравенства

	i					t
f		t x 1 t		y

i

f

t x

1 t

y

для

всех

i .

Из

i

max

f

t x 1 t

y

1 i m

то есть

f t x 1

f	i		x		1 t		f	i
t max fi x
		1 i m
полученных

				i
	t max		f
	1 i m
t y t f		x

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

i

1 t

max

f

y

1 i m

неравенств

имеем

i

x

1 t

max

f

y

,

1 i m

1 t f y .

Что

и

требовалось.

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

Теорема 3. Пусть функция определена на отрезке a, b R и является на нем выпуклой и

22					О.А. Кашина, А.И. Кораблев
неубывающей; функция				выпукла				на	выпуклом
множестве G E	n	, x a, b ,					f	x x
для всех x G . Тогда функция						f	выпукла на G .
Доказательство.				Пусть		x, y G ,			t 0,1 .
Тогда t x 1 t y			t x 1 t y						в	силу
выпуклости функции				на	G	.	Очевидно,			что
t x 1 t y a, b . Поэтому, а также в силу
монотонности и выпуклости					на		a, b ,		имеем

		t x 1

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

t

y

t

x

1 t

y

t

x

1 t

y

.

t

f

t x

1 t

y

f

x

1 t

f

y

.

Что

m

и	требовалось.
Теорема 4. Пусть		A – матрица размерности
n,	b – вектор размерности m , – функция,

определенная и выпуклая на многообразии

y : y E	m	, y

Тогда функция

Ax

f

b, x E

выпукла

n

,

на

f x

E n .

Ax

b

.

Доказательство. Пусть заданы векторы и число t 0, 1 . Тогда имеем

x,

y

Методы оптимизации: Часть I

f

t x

1 t

y

A

t x 1 t

y

b

t

Ax

b

1 t

Ay

b

t

Ax b

1 t

Ay b

t f

x

1 t

Что

и

требовалось.

23

f y .

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

пуклость ее сужения на всевозможные прямые в	E	n	.

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

Пусть заданы функция f

Сужение функции

f

на

делим следующим образом:

и векторы прямую

x, R

s

E	.
n

опре-

t

f

x

ts

.

(2)

Теорема 5. Функция

f

является выпуклой

тогда и только тогда, когда выпуклой является и функция , определенная по формуле (2) при

любых x, s En .

Доказательство. Необходимость. Пусть

f

–

выпуклая функция,	x, s E	n	. Покажем,

также является выпуклой. Пусть a,b

что функция

R, t 0,1 .

Тогда

24

О.А. Кашина, А.И. Кораблев

t a 1 t b

f

t x as 1 t x bs

t f x as 1 t f x bs t a 1 t b .

Достаточность.

Предположим, что для про-

извольных x, s E

n

функция

– выпуклая. Пусть

x, y E

n

и

t 0,1 . Тогда

f

t x

1 t

y

f

y t

x y

t

t 1 1 t 0 t 1 1 t 0

t f x 1 t f y .

Что и требовалось.

Далее установим связь между выпуклыми множествами и выпуклыми функциями.

Пусть c R – некоторая константа. Множе-

ство			n	,	f x c	называется ле-
			Ec f x : x E
беговым множеством					функции	f .
			Теорема 6. Пусть		функция	f	выпукла на
E	n	. Тогда любое ее лебегово множество выпукло.

Доказательство.

Тогда из f x c, f y

Пусть x, y Ec f , t 0,1c и в силу выпуклости f

.

		t x		t
f			1			y
образом,				x, y

лость множества

t	f		x			1
Ec f ,						что
	Ec f .

t

f y c . Таким и означает выпук-

Эта теорема устанавливает одностороннюю связь между выпуклыми множествами и выпуклыми

Методы оптимизации: Часть I

25

функциями. Утверждение, обратное теореме 6, не имеет места.