Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

9.5. Метод градиентного спуска

Оценки скорости сходимости (9.9), (9.12), (9.13), (9.15)-(9.17) показывают, что весьма удачным может оказаться такой выбор направления спуска - sk, при котором αk = 1. Ясно, что если sk = φ' (xk), то


В пользу такого выбора направления спуска можно привести и следующие неформальные соображения. Поскольку антиградиент, то есть - φ' (xk), в точке хk указывает направление наискорейшего убывания функции, то естественным представляется сместиться из точки xk по этому направлению.

Метод спуска, в котором sk = φ'(xk), называют методом градиентного спуска.

Схема 1 итерационной процедуры метода градиентного спуска такова. В качестве начального приближения может быть выбрана любая точка х0∈Еn. (k + 1)-е приближение xk+1, исходя из найденного значения хk, строится по формуле xk+1 = xkksk где sk = φ' (хk), а в качестве βk выбирается число, удовлетворяющее неравенству


где 0 <λ≤λk≤1, а


В дальнейшем мы будем пользоваться следующей краткой записью:

х0∈Еn, xk+1 = xkksk (k = 0, 1, ....,) (9.7)
sk=φ'(xk)(9.18)
βk: φ(xkksk)≤(1-λk)φ(xk)+λkωk (9.8)
(9.19)

Теорема 9.4 дает следующую оценку скорости сходимости схемы 1 метода градиентного спуска:


а в случае сильной выпуклости функции φ (x) из теоремы 9.5 получаем


и


В случае, когда λk = 1, то есть βk определяется в результате одномерной минимизации:


релаксационный процесс называют методом скорейшего спуска.

Для φ(х) ∈ С1 (E2) метод скорейшего спуска имеет геометрическую интерпретацию: точка xk+1 является точкой касания луча


с линией уровня


Схема 2.

(9.7)
sk=φ'(xk)(9.18)

βk:

(9.19)

В качестве βk здесь (как и в условиях (9.14)) выбирается наибольшее число, удовлетворяющее неравенствам (9.19). Заметим, что по сравнению с (9.14) здесь, в (9.19), опущен сомножитель


поскольку здесь всегда Δk = 1.

Теорема 9.6 дает для этой схемы следующие оценки скорости сходимости: для выпуклой функции φ(x) будет


а в случае сильной выпуклости функции φ(x) оценки приобретают вид



Априорные оценки скорости сходимости методов спуска показывают существенную зависимость скорости сходимости градиентного спуска от точности вычислений φ' (xk) и величины βk. Потеря точности, а это обычное явление в окрестности точек минимума либо в овражной ситуации, может вообще нарушить сходимость релаксационного процесса градиентного спуска. В этом случае, если не представляется возможность повысить точность вычислений, возникает необходимость попытаться воспользоваться другими методами, которые, в отличие от метода градиентного спуска, учитывают, кроме свойств выпуклости, и другие свойства минимизируемой функции.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"