АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. Деньги и их функции.
  2. Ms Excel: мастер функций. Логические функции.
  3. SALVATOR создает Знания-Образы, когнитивные имитационные модели сознания, расширяющие человеческие возможности и защитные функции.
  4. А) Ведущая и подчиненная функции.
  5. Абстрактные классы и чистые виртуальные функции. Виртуальные деструкторы. Дружественные функции. Дружественные классы.
  6. Алгебраическое интерполирование функции.
  7. Асимптоты графика функции.
  8. Банки и их функции. Банковская система
  9. Банковская система РФ. Центральный банк и его функции.
  10. Билет 35(Деньги; сущность и функции. Понятие и типы денежных систем. Денежные агрегаты. Закон денежного обращения.)
  11. Бинарные соответствия между множествами.
  12. Биосфера: понятие и современные представления, функции. Вклад Ж-Б Ламарка, Э. Зюсса, В.И. Вернадского. Эволюция биосферы. Границы биосферы.

Определение. Пусть 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 – его подмножество. Функция

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

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

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

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

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

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

Обратно, пусть функция cM является выпуклой. Множество М не является выпуклым, если существуют a, b∈M и λ∈[0, 1], для которых (λa+(1-λ)b) ∈ M. Тогда λcM(a)+(1-λ)cM(b) = 0+0 =0, cM(λa+(1-λ)b)= +∞, что противоречит условию выпуклости функции cM (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 из RN и является дифференцируемой на этом множестве, то можно использовать дополнительные критерии выпуклости (см. соответствующие теоремы математического анализа):

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)