Градиентные методы решения задач нелинейного программирования

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

Градиент всегда перпендикулярен линии уровня, проходящей через ту точку, в которой вычислен градиент. Пример траектории поиска методом градиентного спуска приведен на рис..

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

Показано, что значение a можно определять по некоторым характеристикам функции f(x). Например, если существует такая константа R, что для любых точек

Если известна оценка М сверху максимального собственного числа матрицы , то рекомендуется принять .

Однако, значения R и M обычно заранее неизвестны.

Разработаны различные методы, относящиеся к группе градиентного спуска. Среди них: с постоянным шагом, с дробным шагом и наискорейшего спуска.

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

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

В этом методе направление из касается линии в

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

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

Условия окончания итерационного поиска в градиентных методах связывают обычно с величиной градиента (критерий с номером 3).

Градиентные методы относятся к группе методов 1 порядка, т.к. опираются на вычисления первой производной. Более эффективными могут быть методы второго порядка, которые в том числе используют вторые производные. Однако, здесь могут возникнуть трудности с вычислением и исследованием матрицы вторых производных (матрицы Гессе).

Поиск по сайту: