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

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

В текущей точке вычисляется grad R(x), и затем в направлении градиента ищется min R(x). Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению — направлению градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R(x).

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

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

Условием окончания может являться малость модуля градиента R(x) |grad R(x) | < e. Можно также использовать и малость прира­щений по переменным в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптиму­му, а малостью коэффициента пропорциональности шага h.

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

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