Градиентные методы

Если функция дифференцируема, вычисление производных дает информацию о поведении функции в исследуемой точке и, следовательно, позволяет находить лучшее направление поиска. Скорость изменения функции f (X) в произвольном направлении l определяется производной . Здесь частные производные представляют собой направляющие косинусы. Геометрическая иллюстрация для случая функции двух переменных приведена на рис.

Поверхность уровня целевой функции, описываемая уравнением f (X) = const, имеет размерность n – 1.

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

. Отсюда следует, что максимальная скорость увеличения функции будет в направлении l, совпадающем с нормалью. Вектор, имеющий направление нормали к поверхности функции в данной точке и длину , - градиент. Обозначается градиент как grad f (X) или Ñ f (X). Он полностью определяется своими проекциями – производными функции по переменным:

В задачах на минимум используется противоположное направление – антиградиент.

Значения производных могут быть найдены по приближенным формулам:

,

.

Более точный результат дает вторая формула, но она требует больше вычислений. Чем точнее необходимо вычислить производную, тем меньше должно быть D х. Однако недопустимо, чтобы разность значений функции была соизмерима с погрешностью вычисления. Если переменные имеют разные единицы измерения, можно перейти к относительным переменным y_i, используя минимально и максимально возможные значения переменных x_i: . Значения y_i лежат в диапазоне [0, 1].

Знание градиента (антиградиента) позволяет осуществлять перемещение из текущей точки в направлении наибольшего улучшения функции. Для линейных функций оно постоянно и поэтому его требуется определять всего один раз. В нелинейных функциях значение градиента зависит от вектора X, то есть его необходимо пересчитывать при любом изменении X. В градиентном методе поиск минимума производится согласно рекуррентным формулам: , где h^k - шаг. В первой формуле величина изменения переменных DX зависит как от шага, так и от величины градиента. Удобнее, когда расстояние между последовательными точками зависит только от величины шага. Поэтому предпочтительнее вторая формула. В ней используется нормированный градиент, длина которого всегда равна. Поэтому он задает лишь направление, но не влияет на величину DX. .

Алгоритм градиентного метода.

1) Задать начальную точку, начальное значение шага и точность по величине градиента e, вычислить f (X⁰) и положить k = 0.

2) В текущей точке X ^k вычислить градиент (производные и его длину.

3) Проверить: если закончить поиск.

4) Определить новую точку X ^{k +1} и вычислить в ней значение функции.

5) Проверить: если f (X ^{k+ 1})£ f (X ^k), увеличить k на единицу и перейти на шаг 2; если иначе, уменьшить h^k в два раза и перейти на шаг 4.

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

В результате решения задачи определяется оптимальный шаг h ^*, по которому находится следующая точка: При таком определении новой точки, значение функции в ней будет лучше, чем в X ^k.

Алгоритм наискорейшего спуска.

1) Задать начальную точку и точность по величине градиента e, положить k = 0.

2) В текущей точке X ^k вычислить градиент (производные и его длину.

3) Проверить: если закончить поиск.

4) Провести одномерный поиск.

5) Определить новую точку X ^{k +1} , увеличить k на 1 и перейти на шаг 2.

На рис. показаны две траектории движения к минимуму функции f (X)=(x ₁- x ₂)²+(x ₂-2)⁴, полученные алгоритмом. Минимум на направлении антиградиента достигается в точке касания с линией уровня, а градиент в этой точке ортогонален ей. Поэтому каждое последующее направление ортогонально непосредственно предшест­вую­щему. Из рис. видно, что с приближением к экстремуму частота вычисления градиента увеличивается, и вблизи минимума метод наискорейшего спуска вырождается в градиентный.

Градиентные методы плохо работают в условиях оврага: при попадании на дно оврага резко падает скорость движения и возможна остановка поиска до достижения окрестности минимума.