2.8. Выпуклые функции на Rm.

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

Функция f: R^m  R называется выпуклой, если при всех x, y  R^m и   (0, 1)

f(x + (1  )y)  f(x) + (1  )f(y).

(10)

Если неравенство (10) строгое, то f называется строго выпуклой. Геометрически выпуклость означает, что график функции на интервале (x, y), соединяющем любые точки x и y, лежит не выше прямой, соединяющей точки (x, f(x)) и (y, f(y)) (см. рис. 3а). Функция f сильно выпукла (с константой c > 0), если неравенство (10) выполняется в следующей более сильной форме

f(x + (1  )y)  f(x) + (1  )f(y) +  c 2 (1  )||x  y||2.

(11)

Рис. 3.

Геометрически это понятие можно интерпретировать так. Пусть точки отрезка [x, y], соединяющего точки x и y, параметризованы параметром :   x + (1  )y. Правая часть неравенства (11) определяет на этом отрезке полином  второго порядка (от ). График сильно выпуклой функции над отрезком [x, y] должен лежать ниже параболы — графика этого полинома (см. рис. 3б).

Критерий выпуклости дифференцируемой функции. Для того, чтобы дифференцируемая функция f была выпуклой необходимо и достаточно выполнения при всех x, y  R^m неравенства

f(x)  f(y)  (f (y), x  y).

(12)

Действительно, определим на отрезке [0, 1] функцию , положив

() = f(x + (1  )y).

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

() = (f (x + (1 )y), x  y).

Неравенство (12) в новых обозначениях переписывается в виде

(1)  (0)  (0),

или, если воспользоваться формулой Лагранжа,

()  (0),

(13)

где  — некоторая точка интервала (0, 1). Из курса математического анализа известно, что для дифференцируемых функций выпуклость эквивалентна монотонности производной. Поэтому, если f выпукла, то  монотонна. Следовательно, имеет место эквивалентное (12) неравенство (13).

З а д а ч а  2.13. Докажите обратное утверждение.

Геометрически доказанное утверждение означает, что значения функции f(x) "лежит выше" гиперплоскости H_y = {(x, )  R^m×R:  = f(y) + (f (y), x  y)}, касательной в точке (y, f(y)) к графику Gr f = {(x, )  R^m× R:  = f(x)} при всех y  R^m (см. рис. 4).

Рис. 4.

Строгая выпуклость дифференцируемой функции, как легко видеть, эквивалентна строгому при x  y неравенству (12). Сильная же выпуклость функции f эквивалентна выполнению при всех x и y неравенства

f(x)  f(y)  (f (y), x  y) + c||x  y||2.

(14)

З а д а ч а  2.14*. Докажите последнее утверждение.

З а д а ч а  2.15*. Докажите, что f  C² сильно выпукла с константой c в том и только том случае, если f (x)  c при всех x  R^m.