4.3.Градиентные методы оптимизации

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

, (4.1)

где – текущее приближение к решению ; – параметр шага, – направление поиска в -мерном пространстве на каждом шаге.

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

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

Этот метод называется также оптимальным градиентным методом, методом Коши и является самым простым градиентным методом, и основан на определении минимума функции в направлении градиента. Является вариантом градиентного спуска с переменным шагом и имеет вид

Значение шага вычисляется на каждой итерации путем решения задачи одномерной минимизации

.

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока убывает. Критерий останова итерационного процесса

Преимущество метода – в его устойчивости, то есть при достаточно малом обеспечивается выполнение условия

.

Недостаток метода состоит в уменьшении скорости сходимости при приближении к . Метод является основой градиентных методов и применяется на начальных этапах поиска экстремума.

4.3.2.Метод Ньютона

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

,

где – матрица Гессе; – градиент функции.

Достоинства метода Ньютона:

– для квадратической минимизируемой функции метод позволяет найти минимум за один шаг;

– если минимизируемая функция относится к классу поверхностей вращения (т.е. обладает симметрией), то метод также обеспечивает сходимость за один шаг (поскольку в точке минимума аргументы минимизируемой функции и ее квадратической аппроксимации совпадают);

– если функция несимметрична, то метод не обеспечивает сходимость за конечное число шагов. Но для многих функций (даже очень сложных, например, для функции Розенброка) достигается более высокая скорость сходимости, чем при использовании других модификаций метода наискорейшего спуска.

Основными недостатками метода Ньютона считают:

• необходимость вычисления и обращения матрицы Гессе на каждой итерации; кроме расходования машинного времени эти операции могут привести к значительным вычислительным погрешностям, если матрица Гессе окажется плохо обусловленной (т.е. значение определителя этой матрицы будет близко к нулю);

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

4.3.3.Модифицированный метод Ньютона

При поиске экстремума неквадратных функций метод Ньютона не очень надежен, при неудачном выборе начального приближения шаг поиска окажется слишком большим и итерации не сойдутся. Для устранения этого недостатка используют модифицированный метод Ньютона. Он реализуется такими итерациями:

, .

Коэффициент (параметр шага) выбирают на каждом шаге так, чтобы , (как в методе Коши), это гарантирует, что .

Метод эффективный и надежный, если вычисление первых и вторых производных не связано с трудностями. Недостаток состоит в необходимости построения и решения линейного уравнения, содержащего элементы матрицы Гессе (для вычисления ).