![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Метод наискорейшего спускаПри использовании метода наискорейшего спуска на каждой итерации величина шага аk выбирается из условия минимума функции f(x) в направлении спуска, т. е. f(x[k] –akf’(x[k])) = Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции Алгоритм метода наискорейшего спуска состоит в следующем. 1. Задаются координаты начальной точки х[0]. 2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k])=g. 3. Определяется величина шага ak, путем одномерной минимизации по а функции (a) = f(x[k] - af'(x[k])). 4. Определяются координаты точки х[k+1]: хi[k+1] = xi[k] – аkf’i(х[k]), i = 1 ,..., п. 5. Проверяются условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Рис. 1.17. Геометрическая интерпретация метода наискорейшего спуска (с решением задачи одномерной оптимизации на каждой итерации) В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (рис. 1.17). Траектория спуска зигзагообразная, причем вблизи точки минимума функции цели соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по а функции (a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции d f(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках: d f(a)/da = -f’(x[k+1]f’(x[k]) = 0. Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе) мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями i, i =1, …, n, матрицы являются корни характеристического уравнения Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (рис. 1.18), а направление антиградиента этих функций может существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости. Рис. 1.18. Схема сходимости метода наискорейшего спуска для овражной функции Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х[0] находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.
|