4.1 Градиентные методы

Вектор — f'(xk) является направлением наискорейшего убывания функции f(x) и называется антиградиентом. Выбирая в каче­стве направления спуска рк антиградиент функции /(ж) в точке хк, приходим к итерационному процессу вида

xk+1 =хк - akf{xk),ak > 0.

Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом (градиентом) функции, называются градиентными методами и отличаются друг от друга способами выбора длины шага ак. Существует много различных способов выбора длины шага ак, но наиболее распространены три из них. Первый называется методом с постоянным шагом: ак = а. Второй — метод с дроблением шага. Он связан с проверкой на каждом шаге неравенства

f(xk - ак f(xk)) - f(xk) < -е ак \\f'(xk)\\2,

где е — некоторая константа из интервала (0,1).

В третьем методе при переходе из точки хк в точку хк+1 ми­нимизируется по а функция f(xk — a f'(xk)) :

ак = argmin/(sfc — a f'(xk)).

Это метод наискорейшего спуска.

Следующая теорема содержит достаточные условия сходимо­сти метода с постоянным шагом.

Теорема 4.1 (Первая теорема сходимости) Пусть функция f дифференцируема в Rn, ограничена снизу f(x) > f* > —со, вы­полняется условие Липшица для градиента /'(ж) :

\\f'(x)-f'(y)\\<L\\x-y\\

и длина шага а удовлетворяет условию 0 < а < 2/L. Тогда

f(xk) -> 0 при к -> ос и f(xk+1) < f(xk),

при любом выборе начального приближения жо-

Доказательство. Воспользуемся формулой конечных прираще­ний

і

f(x + y)=f(x) + J(f'(x + Ty),y) dr, о

которую перепишем в следующем виде:

1

/(ж + у) = /(ж) + (/'(ж), у) + J (/'(ж + ту) - fix), у) dr.

о

Сделаем подстановки ж = хк,у = —af'{xk). Тогда из неравен­ства Коши - Буняковского Ь)| < ||а|| ||6|| и условия Липшица получим

f(xk+1)<f(xk) + (f'(xk),-af'(xk)) +

і

+ / K/V - raf(xk)) - f(xk), -af(xk))\dT < о

< Z(^)-a||/V)||2 +

і

+ J\\f(xk - raf{xk)) - /V)||||a/V)||dr < о

67

1

< /V) - « H/V)H2 + / L\\raf'(xk)\\ \\af'(xk)\\dr =

о

l

= f(xk)-a\\f(xk)\\2 + La2 \\f(xk)\\2 J rdr =

о

= f(xk) - a(l - La/2)\\f'(xk)\\2 = f(xk) - 7||/V)I|2,

где 7 = a(l — La/2). Из условий теоремы следует, что у > 0 и, следовательно,

f(xk+1)<f(xk). Кроме того, для любого s выполняется неравенство:

к=0

Поэтому, учитывая ограниченность функции / на множестве Rn, получаем оценку сверху для частичных сумм:

£ n/V)ii2 < (/(ж°) - f(*s+1))/j < (л*0) - п/ъ

к=0

Откуда и следует сходимость к нулю градиента f'(xk) при к —> со. Теорема доказана.

В условиях теоремы 4.1 градиентный метод обеспечивает схо­димость последовательности {f(xk)} либо к точной нижней грани mfxf(x) (если функция /(ж) не имеет минимума), либо к значе­нию /(ж*), где х* = Hindoo хк и /'(ж*) = 0 (если такой предел су­ществует). Существуют примеры, когда в точке ж* реализуется седло, а не минимум. Тем не менее, на практике методы гради­ентного спуска обычно обходят седловые точки и находят локаль­ные минимумы целевой функции. Для оценки скорости сходимо­сти метода предположений теоремы 4.1 недостаточно. Сделаем это в случае, когда /(ж) — сильно выпуклая функция.

Определение 4.1 Дифференцируемая функция f называется силь­но выпуклой (с константой I > 0), если для любых х и у из Rn справедливо

Дж + у)> Дж) + (f'(x),y) + l\\y\\2/2. (4.1)

Лемма 4.1 Если функция f является сильно выпуклой (с кон­стантой I > 0), то она имеет глобальный минимум на Rn.

Доказательство.  Из условия (4.1) и неравенства Коши - Бу-няковского следует

/(Ж + у)>/(Ж)-||/'(Ж)||||у|| + /||у||2/2.

Пусть г = 2||/'(ж)||//. Если ||у|| > г, то

f(x + у)> f(x) + |М|(/|М|/2 - ||/'(Ж)||) > f(x). (4.2)

Рассмотрим шар В(х,г) с центром в точке х и радиуса г. По теореме Вейерштрасса непрерывная функция / достигает своего минимума на шаре В(х,г) в некоторой точке ж*. Из неравенства (4.2) следует, что ж* — минимум на всем Rn. Лемма доказана.

Лемма 4.2 Если функция f является сильно выпуклой (с кон­стантой I > 0) и х* — ее глобальный минимум, то для любого х G Rn выполняется неравенство

||Лж)||2>2/(Дж)-Дж*)). (4-3)

Доказательство. Так как функция / сильно выпуклая, то под­становка у = ж* — ж в (4.1) дает следующее неравенство

/(ж) - /(ж*) + (/'(ж), ж* - ж) + /||ж* - ж||2/2 < 0.

Так как

<Д(ж)/У27 + ^/2(ж* - x),f'(x)/V2i + ^/2(ж* - ж)) =

= \\f\x)/V2l + Jl/2(x*-x)\\2>0,

то

\\f{x)\\2/2l + (f'(x),x* -x) + l\\x* - x)\\2/2 > 0 >

> f{x) - f{x*) + (f(x),x* - ж) + l\\x* - x\\2/2.

После приведения подобных членов получим требуемое неравен­ство. Лемма доказана.

Теорема 4.2 (Вторая теорема сходимости) Пусть функция f дифференцируема в Rn, является сильно выпуклой, выполняется условие Липшица для градиента /'(ж) : \\fl(x)—f'(y)\\ < L \\х — у\\ и длина шага а удовлетворяет условию 0 < а < 2/L. Тогда

хк -> х* при к -> ос и \\хк - х*\\ < C'qk, 0 < q < 1.

Доказательство. Воспользуемся неравенством, полученным при доказательстве теоремы 4.1:

f(xk+1) < f(xk) - а(1 - La/2)\\f'(xk)\\2.

По лемме 4.1 существует глобальный минимум х* функции /. Используя (4.3), получим

f(xk+1) < f(xk) - la{2 - La)(f(xk) - f(x*)).

Вычитая из обеих частей неравенства величину /(ж*), получим

_ /(ж*) < (1 _ /а(2 - La))(f(xk) - f(x*)). (4.4)

Обозначим через q\ коэффициент при выражении (f(xk) — /(ж*)). Понятно, что

/(^+1) _ /(ж*) < qk+\f(x°) - /(ж*)). (4.5)

Проверим, что q\ > 0. Функция / является сильно выпуклой. Значит, она не может быть константой и имеется возможность

70выбрать начальную точку ж0 так, чтобы /(ж0) > /(ж*) . Из нера­венства (4.4) при к = 0 имеем

о <^(жV Дж*) < ft(/(*V/00),

откуда и следует требуемое неравенство.

Так как q\ < 1, то f(xk) —> /(ж*). Учитывая, что /'(ж*) = О, из (4.1) при подстановках у = хк — ж* и ж = ж* получим

(/И-/(ж*))>/||ж/;-ж*||2/2.

Следовательно,

||^-ж12<2^ (/(ж0) - /(ж*))//.

Последнее неравенство влечет линейную оценку скорости сходи­мости метода

\\хк - х*\\ < Cqk,

где С = ^2(/(ж°) — /(ж*))//, q = y/gT, а также сходимость после­довательности {хк} к единственной точке минимума ж*. Теорема доказана.