09. Вычисление градиента

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

Простейшей формулой вычисления проекций градиента является конечная разность вперёд:

, , (1.21)

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

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

Машинное эпсилон – это наименьшее положительное число, для которого при машинном сложении чисел выполняется неравенство

.

Например, в компьютерной математической системе MATLAB задаётся с помощью встроенной константы .

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

Алгоритм вычисления градиента.

Входные параметры: и – точка, в которой вычисляется градиент, и значение в ней функции; – процедура вычисления целевой функции; – параметр приращения аргумента.

Выходной параметр – значение градиента.

1. Положить , , , .

2. Положить .

3. Вычислить , .

4. Положить .

5. Если , то положить и перейти к шагу 2.

6. Остановиться.

По формуле разности вперёд (1.21) при известном значении функции в точке для вычисления градиента требуется дополнительных вычислений функции.

С помощью центральных разностей значения проекций градиента вычисляются по формуле:

, . (1.22)

Погрешность этой формулы составляет . Однако эта формула требует дополнительных вычислений значений целевой функции. Поэтому в численных методах оптимизации первого порядка применяется формула конечной разности вперёд (1.21), требующая меньшего числа вычислений функции. Для примеров 1.7 и 1.8 с методом наискорейшего спуска использовалась формула (1.21). Формула же центральных разностей (1.22) применяется в методах второго порядка.

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