Теорема

Пересечение выпуклых множеств выпукло. Доказать самостоятельно.

Определение.

Функция f(x) называется выпуклой, если её область определения выпукла и для любого x₁,x₂X, (0,1) выполняется f(x₁+(1-)x₂) f(x₁)+(1-)f(x₂)

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

Определение.

Функция f(x), для которой -f(x) выпукла называется вогнутой.

Определение

Функция f(x) на R_n называется строго выпуклой, если xy, 0<<1 выполняется

f(x+(1-)y)<f(x)+(1-)f(y),

сильно выпуклой с константой l>0, если при 0  1 выполняется

f(x+(1-)y)f(x)+(1-)f(y)-l(1-)||x-y||²/2

Cвойства выпуклых функций

1.Теорема:

Любая точка локального min выпуклой функции является в то же время точкой глобального минимума.

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

Пусть x*- точка локального минимума функции, она не является точкой глобального минимума, то есть yX такая что:

f(y)<f(x*) (*)

Рассмотрим точки вида x = y+(1-)x* ,(0,1)

Так как X выпукло, то xX (по определению). Из выпуклости функции f(x)

и из (*) следует:

f(x)=f(y+(1-)x*)(по вып.)f(y)+(1-)f(x*)<(*)f(x*)+(1-)f(x*)=f(x*)

Получено: f(x)<f(x*) 

Но это противоречит предположению о том, что х*- локальный минимум. Противоречие доказывает утверждение теоремы.

Теорема(о сильно выпуклой функции)

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

Без доказательства

2.Теорема:

Пусть функция f(x) имеет вторую непрерывную производную. Для того, чтобы функция была выпуклой необходимо и достаточно, чтобы её вторая производная была неотрицательна. (Без доказательства)

Для сильно выпуклых функций: ²f (x)  l_*I., где I- единичная матрица, l>0

Эту теорему можно рассматривать как критерий выпуклости

дифференцируемых функций.

Замечание:

Не все выпуклые функции дифференцируемы.

1.f(x) = x-выпуклая, не дифференцируемая

2.y = x² выпуклые, проверка выпуклости по второй производной

y = -ln(x)

3.Теорема (неравенство Йенсена):

Чтобы фукция f (x) была выпукла необходимо и достаточно, чтобы

 m 2, x₁,x_2,…,x_mХ и _i  0 _i =1 выполнялось:

_{m m}

f (  _i* x_i )   _{i *} f (x_i ). (*)

^{i=1 i=1}

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

Достаточность, т.е. справедлива (*), нужно доказать выпуклость: пусть

m = 2, тогда f (x) – выпукла по определению.

Необходимость, т.е. дана выпуклость, нужно доказать (*):

Доказательство по индукции.

при m = 2 (*) выполняется по определению.

Пусть при m = k теорема доказана (индукционное предположение).

Докажем при m = k + 1:

_k+11, тогда _i x_i = _k+1*x_k+1 + (1 - _k+1)_{* i *} x_i /(1 - _k+1),

тогда _{i *} x_i Х., так как выпуклое множество содержит все выпуклые

комбинации своих точек.

Воспользуемся свойством выпуклости функций:

f (_i* x_i )  _k+1*f (x_k+1) + (1 - _k+1)_* f ( _i* x_i/(1 - _k+1)) 

Мы предположили, что теорема доказана для m=k (если выполнены условия теоремы – проверим)

_i/(1-_k+1)= (1-_k+1)/ (1-_k+1)=1 удовлетворяет условиям теоремы (сумма всех коэффициентов равна 1)

 _k+1*f (x_k+1) + (1 - _k+1)_{* i *} f (x_i)/(1 - _k+1) = _{i *} f (x_i )

Неравенство доказано.

Упражнения:

• Применить неравенство Йенсена к функции –ln(x) при _i=1/m.

• Доказать, что если функция (x) выпуклая на выпуклом множестве X, то выпукла на X и функция f(x)=max{(x),0}.

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

Без доказательства

Пусть есть направление s ( ||s||=1-норма вектора):

f (x)/ s = lim = f _s(x)= (f (x), s)-производная по направлению

  0,   0

5. Для дифференцируемой функции f (x) на выпуклом множестве X выпуклость эквивалентна неравенству:

f (x +y)  f (x) + (f(x),y ) при всех x, y.

Строгая выпуклость эквивалентна неравенству:

f (x +y)  f (x) + (f(x),y ) при всех x, y.

Сильная выпуклость эквивалентна неравенству:

f (x +y)  f (x) + (f(x),y ) + l_*||y||²/2, где l=const при всех x, y.

Без доказательства

6. Для сильно выпуклых функций справедливы соотношения:

1. f (x)  f (x^*) + l_*|| x - x^*||²/2

2. (f(x), x-x^*)  l_*|| x - x^*||²

3. ||f(x)||  l_* || x - x^* ||

Без доказательства