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

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

В текущей точке вычисляется  Grad F(X), и затем в направлении градиента ищется Min F(X). Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению – направление градиента), наиболее часто используется сканирование до первого локального минимума по направлению Grad F(X).

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

В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска Min по направлению (задается величиной H – шагом поиска по направлению). Условием окончания может являться малость модуля градиента  функции F(X): |Grad F(X)| < . Можно также использовать и малость приращений по переменным в результате шага, но только в том случае, если на данном шаге мы «проскочили» оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптимуму, а малостью коэффициента пропорциональности шага H.

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

Метод наискорейшего спуска отличается от градиентного спуска способом определения величины Hk, которая находится из условия:

  (*)

Такой выбор Hk Обеспечивает максимально возможное уменьшение функции F(X) вдоль направления ее антиградиента  В точке Х(K).

Таким образом, для определения Hk на каждом шаге метода наискорейшего спуска решается одномерная задача минимизации функции ФK(H), для чего можно использовать рассмотренные выше методы одномерной оптимизации.

Пример 64. Минимизировать функцию  методом наискорейшего спуска, завершив вычисления при , I = 1, 2.

Решение. Найдем частные производные:

1-й шаг. Положим Х(0) = (0, 0), тогда

Функцию Ф0(H) находим, используя соотношение (*). Для нахождения точки минимума функции Ф0(H) используем метод Пауэлла. Поскольку шаг H изменяется в пределах 0 < H < 1, то за первоначальное значение примем H = 0,  а H = 0.5. Таким образом находим H0 = 0.22.

Значит, Х(1) =(0, 0) – 0.22(1, 1) = (-0.22, -0.22).

Вычислим значение производных: F(-0.22, -0.22) = (0.204, -0.236). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:

Снова используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим H1 = 0.32.

Значит, Х(2) =(-0.22,-0.22) – 0.32(0.204, -0.236) = (-0.2853, -0.1445).

Вычислим значение производных: F(-0.2853, -0.1445) = (0.08, 0.0726). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:

Используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим H2 = 0.24.

Значит, Х(3) =(-0.2853-0.240.08, -0.1445-0.240.0726) = (-0.3045, -0.1619).

Вычислим значение производных: F(х(3)) = (0.0182, -0.0205). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и

Пример 65. Минимизировать функцию F(X, Y) = X3+2Y2-3X-4Y, методом градиентного спуска с дроблением шага, завершив вычисления при

Решение. Найдем частные производные:

1-й шаг. Положим Х(0) = (0, 0), тогда

Функцию Ф0(H) находим, используя соотношение (*). Для нахождения точки минимума функции Ф0(H) используем метод Пауэлла. Поскольку шаг H изменяется в пределах 0 < H < 1, то за первоначальное значение примем H = 0,  а H = 0.5. Таким образом находим H0 = 0.281.

Значит, Х(1) =(0, 0) – 0.281(-3, -4) = (0.843, 1.124).

Вычислим значение производных: F(х(1)) = (-0.8681, 0.496). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:

Снова используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим H1 = 0.2121.

Значит, Х(2) =(0.833+0.21210.8681, 1.124-0.21210.496) = (1.0171, 1.0188).

Вычислим значение производных: F( х(2)) = (0.1035, 0.0752). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:

Используем метод Пауэлла, полагая H = 0 и H = 0.5, Находим H2 = 0.2196.

Значит, Х(3) =(1.0171-0.21960.1035, 1.0188-0.21960.0752) = (0.9944, 1.002).

Вычислим значение производных: F(х(3)) = (-0.0335, 0.008). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и

Вопросы к главе 6

Метод градиента

1.  Что называется градиентом функции двух переменных?

2.  Как оценивается эффективность поиска градиентным методом?

3.  Какой алгоритм коррекции шага предпочтительнее вблизи оптимума?

4.  Почему в районе оптимума величина шага х убывает при использовании

Алгоритма ?

5.  Исходя из определения Gradf(X) как вектора, указывающего направление

Возрастания функции, что лучше искать: Min или Max?

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

1.  В чем основные отличия метода наискорейшего спуска от метода градиента?

2.  По какому направлению осуществляется поиск из каждой текущей точки при

Поиске Minf(X)?

3.  Как вычисляется градиент F(X) в методе наискорейшего спуска?

4.  Каковы условия окончания поиска?

5.  Можно ли методом наискорейшего спуска найти Maxf(X)?

< Предыдущая		Следующая >