1.1.1. Градиентный метод с постоянным шагом

Пусть t_k = t (т.е. не зависит от к)

x_k+1 = x_k - tf(x_k)

Видно, что останавливаемся в любой точке, где f(x_k)=0.

Пример:

f(x) = ax², a>0, x-скаляр

x_k+1=x_k - 2tax_k = (1- 2at)x_k

Отсюда

1-2at<1 at<1- необходимое и достаточное условие существования предела

Если 0<t_k<1/a - сходится,

t_k>1/a - расходится,

t_k=1/a - зацикливается.( t_k=1/a x₁=x₀-2x₀= -x₀ x₂=x₁-2x₁= -x₁=x₀ и т.д.)

Выбор постоянного шага приводит к осложнениям, так как a заранее часто не известно, а при малом значении a – много шагов; при большом – есть риск потери сходимости.

Оценим сходимость этого метода в общем случае.

Теорема (о сходимости метода градиентов)

Пусть f(x)- дифференцируема на R_n, f(x) удовлетворяет условию Липшица:

L>0, x, y верно || f(x)-f(y) || L ||x-y || (*)

(||x²|| = x_i² ), f(x)- ограничена снизу:  f* такая, что f(x) f* >- (**)

и 0< t< 2/L (***)

Тогда при x_k+1= x_k - tf(x_k), справедливо:

• f(x_k)  0, при k (градиент стремится к нулю),

• функция f(x) монотонно убывает (f(x_k+1)f(x_k)),

• f(x_k+1)  f(x_k)-t(1-tL/2)||f(x_k) ||² .

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

Справедливо равенство:

(1)

Пусть x=x_k, y= -tf(x_k) (2)

Подставим (2) в(1):

f(x_k+1)=f(x_k)-t||f(x_k) ||²-t-f(x_k),f(x_k))dt 

Под интегралом:

(f(x_k-tf(x_k))-f(x_k),-tf(x_k))

Из условия теоремы известно: ||f(x)-f(y)|| L||x-y||

В данном случае:

x-y = -tf(x_k), то есть ||f(x_k-tf(x_k))-f(x_k)|| L||- tf(x_k)||

и тогда соответствующее скалярное произведение принимает вид:

 L(- tf(x_k), - tf(x_k)) = Lt²||f(x_k)||²

 f(x_k)- ||f(x_k)||²+Lt²||f(x_k) ||² =f(x_k)-t(1-Lt/2) ||f(x_k) ||²

Обозначим a = t(1-Lt/2); a>0, так как (***)

Отсюда f(x_k+1) f(x_k)-a||f(x_k) ||²

Оценим f(x_k+1) через f(x₀)

Пусть k=0: f(x₁) f(x₀)- a||f(x₀) ||²

k=1: f(x₂) f(x₁)- a||f(x₁) ||² f(x₀)- a||f(x₀) ||² - a||f(x₁) ||².........

f(x_s) f(x₀)- a²

так как a>0, то ² a^-1(f(x₀)-f(x_s+1)) a^-1(f(x₀)-f*), S

то есть ²< ( сумма ограничена) ||f(x_k) ||0, то есть теорема доказана.

Замечание:

Сходимость градиента к нулю не гарантирует сходимости к минимуму.

Пример:

, градиент сходится к нулю, но функция не имеет локальных минимумов.

Равенство градиента нулю - необходимое условие минимума; если к нему добавить положительность второй производной, то будет достаточное условие локального минимума.

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

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

Определение. Множество X называется выпуклым, если x₁,x₂X, [0,1], выполняется x₁+(1-)x₂X, то есть вместе с любыми двумя точками оно содержит и отрезок их соединяющий.

На рис 1 изображено выпуклое множество, на рис 2 - невыпуклое.

рис 1 рис2

Определение. Точка Z называется выпуклой комбинацией точек x₁,x₂,...,x_m, если

, ,,

Теорема (о выпуклом множестве)

Выпуклое множество X содержит все выпуклые комбинации своих точек. Доказать самостоятельно.