Выпуклые множества и выпуклые функции

Определение. Пусть X – векторное пространство, a, b∈X. Множество

[a, b] = {x∈X| ∃λ∈[0, 1]: x = λa+(1-λ)b}

называется отрезком, соединяющим точки a и b.

Нетрудно убедиться, что такое определение отрезка согласуется с обычным определением отрезка на плоскости и в трехмерном пространстве.

Определение. Пусть X – векторное пространство. Множество M⊆X называется выпуклым, если для всех a, b∈M выполняется условие [a, b] ⊆ M, т.е. множество M с любыми двумя точками содержит соединяющий их отрезок.

Определение. Пусть X – векторное пространство, M⊆X выпуклое подмножество. Функция f:M→R называется выпуклой, если для всех a, b∈M выполняется условие

∀λ∈[0, 1] f(λa+(1-λ)b) ≤ λf(a)+(1-λ)f(b), (4.1.1)

т.е. если две точки графика функции соединить отрезком, то график функции будет лежать ниже этого отрезка.

Иногда удобнее считать, что функция определена не на подмножестве M⊆X, а на всем векторном пространстве X. Для этого мы будем использовать следующее правило: в тех точках x∈X, в которых функция была неопределена, будем полагать, что f(x) = +∞.

Таким образом, мы будем иметь дело с функциями, значениями которых могут быть не только действительные числа, но и символ +∞. Если такие функции проверять на выпуклость, надо уметь совершать арифметические операции над символом +∞. Определим их естественным путем:

∀λ≥ 0 λ(+∞) = +∞, (+∞)+(+∞) = +∞, ∀y∈R y + (+∞) = +∞.

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

Определение. Пусть X – векторное пространство, M⊆X – его подмножество. Функция

c_M(x) = 0, если x∈M; c_M(x) =+∞ в противном случае (4.1.2)

называется индикаторной функцией подмножества M.

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

Теорема 4.1.1. Множество M⊆X является выпуклым тогда и только тогда, когда индикаторная функция c_M является выпуклой.

Доказательство. Пусть M⊆X – выпуклое множество. Если c_M(a)=+∞ или c_M(b) = +∞, равенство (4.1.1) выполняется по правилам действий с бесконечностью.

Если же c_M(a)≠+∞ и c_M(b) ≠ +∞, то c_M(a) = c_M(b) =0, т.е. a, b∈M. В силу выпуклости множества М для всех λ∈[0, 1] имеем (λa+(1-λ)b)∈M, или c_M(λa+(1-λ)b)=0. В таком случае c_M(λa+(1-λ)b) = λc_M(a)+(1-λ)c_M(b) =0.

Обратно, пусть функция c_M является выпуклой. Множество М не является выпуклым, если существуют a, b∈M и λ∈[0, 1], для которых (λa+(1-λ)b) ∈ M. Тогда λc_M(a)+(1-λ)c_M(b) = 0+0 =0, c_M(λa+(1-λ)b)= +∞, что противоречит условию выпуклости функции c_M (4.1.1).

Теорема доказана.

Определение. Пусть функция f: M→R. Множество Epi(f) = {(x,y)∈M×R| f(x) ≤ y} называется надграфиком функции f.

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

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

Теорема 4.1.2. Функция f: M→R является выпуклой тогда и только тогда, когда ее надграфик Epi(f) является выпуклым подмножеством в M×R.

Доказательство. Условие (x,a), (y,b)∈Epi(f) означает, что f(x) ≤ a, f(x) ≤ b. Тогда для всех λ∈[0, 1] справедливо λf(x)+(1-λ)f(y) ≤ λa+(1-λ)b.

Если f – выпуклая функция, то f(λx+(1-λ)y) ≤ λf(x)+(1-λ)f(y) ≤ λa+(1-λ)b,

т.е. (λx+(1-λ)y, λa+(1-λ)b) ∈ Epi(f), а это – условие выпуклости множества Epi(f).

Пусть Epi(f) выпукло. Для всех x, y ∈ М всегда (x,f(x)), (y,f(y) ∈Epi(f), поэтому (в виду выпуклости) (λx+(1-λ)y, λf(x)+(1-λ)f(y)) ∈Epi(f), т.е. f(λx+(1-λ)y) ≤ λf(x)+(1-λ)f(y).

Теорема доказана.

Замечание. Если функция f определена на открытом подмножестве M из R^N и является дифференцируемой на этом множестве, то можно использовать дополнительные критерии выпуклости (см. соответствующие теоремы математического анализа):

1) Если f непрерывно дифференцируема на M, то ее выпуклость равносильна выполнению следующего условия: для всех a, b∈M выполняется неравенство f(a) – f(b) ≥ grad f(b)(a-b);

2) Если f дважды непрерывно дифференцируема на M, то ее выпуклость равносильна неотрицательной определенности матрицы ее вторых производных (которую можно проверять по критерию Сильвестра).

Поиск по сайту: