ПОЗНАВАТЕЛЬНОЕ

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

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

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

1 234

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

, (4.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 234