8.3. Метод градиентного спуска

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

будет сходиться к минимуму функции из произвольной начальной точки с координатами [12].

Параметр а в формуле (8.7) определяет длину шага в направлении спуска Длину шага можно выбирать из условия минимизации функции вдоль направления, противоположного градиенту. Такой вариант градиентного метода называют методом наискорейшего спуска: В другом варианте градиентного спуска длина шага а выбирается методом дробления [12, 18]. В последнем

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

При невыполнении этого условия шаг а уменьшается вдвое, вычисляются координаты с новым шагом и вновь проверяется условие (8.8). Дробление шага продолжается до тех пор, пока не будет выполнено условие (8.8).

Для завершения итерационного процесса можно выбрать следующий критерий:

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

С помощью градиентного спуска минимум гладких функций находится значительно быстрее, чем при использовании координатного спуска. Однако наряду с вычислением функции на каждой итерации градиентного метода приходится вычислять составляющие градиента этой функции. Кроме того, сходимость итерационного процесса (8.7) может быть медленной для функций, имеющих овражный рельеф. В этом случае изменением масштабов переменных рекомендуется перейти к котловинному рельефу или применить так называемый овражный метод [12].

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

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

Пусть задана система нелинейных уравнений

Для отыскания решений этой системы составим функционал

минимумы которого должны быть равны нулю в точках, соответствующих корням исходной системы уравнений.

В программах 8.3 реализован метод градиентного спуска с дроблением

шага в соответствии с блок-схемой рис. 8.7

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

Рис. 8.7. Блок-схема программы минимизации функции многих переменных методом градиентного спуска

В диалоговом режиме (строки 20-30) задаются значения переменных: фактическая размерность задачи; допустимая погрешность определения каждой координаты точки минимума; А - начальное значение шага спуска; координаты начальной точки поиска.

После обращения к подпрограмме метода градиентного спуска из строки 60 на дисплей выводятся координаты точки минимума, значение функции в этой точке и количество итераций поиска (строки 70-80).

В подпрограмме метода градиентного спуска итерационный процёсс по формуле (8.7) реализован в строках 110-180. При нарушении условия (8.8) осуществляется уменьшение шага вдвое (строка 190) и вычисления повторяются. Переменная К используется как счетчик итераций. Переменная введена для осуществления программной реализации условий (8.9) завершения итерационного процесса, при этом использована конструкция такая же, как и в программе

В качестве примера используется функция двух переменных (8.6). Подпрограмма вычисления функции состоит из двух арифметических операторов (строки 200-290). Экспоненциальная часть функции необходима и для вычисления градиента, поэтому она вычисляется отдельно.

Составляющие градиента вычисляются в подпрограмме, расположенной в строках 300-390.

В программе метод градиентного спуска оформлен в виде подпрограммы с именем имеющей формальные параметры: допустимая погрешность определения координат точки минимума; А - начальный

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

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

Для тестирования приведем протокол выполнения программы

(см. скан)

(см. скан)

(см. скан)