Методы первого порядка

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

Все градиентные методы плохо работают в овражных функциях.

1. Метод градиентного спуска с постоянным шагом. . Основной недостаток – необходимость частого вычисления производных.

2. Метод наискорейшего градиентного спуска. Шаг определяется решением задачи одномерной оптимизации: . Вдали от оптимума эффективность метода повышается по сравнению с методом градиентного спуска, а в окрестности – снижается из-за частой смены направлений.

3. Метод проекции градиента. .

4. Метод Гаусса-Зейделя. Метод проекции градиента, в котором шаг выбирается как решение задачи минимизации .

5. Метод кубической интерполяции. Задается начальная точка и с помощью серии пробных шагов находятся две точки, первые производные в которых имеют противоположные знаки. По величине функции и ее первых производных в полученных точках строится интерполяционный полином третьей степени. В качестве приближения точки минимума берется точка минимума полинома. Процесс поиска заканчивается, если производная в точке минимума полинома достаточно мала или процедура становится неэффективной.