Метод градиента (наискорейшего спуска или крутого восхождения или метод Бокса-Уилсона)

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

Реализация этого интуитивно понятного метода носит название метода крутого восхождения или метода градиента. Помимо направления, в математической реализации метода необходимо иметь и алгоритм выбора шага поиска – при слишком большом шаге неизбежны потери на рыскание вокруг экстремума, а при слишком маленьком движение к цели будет медленным. Градиент функции f(x₁, x₂, ..., x_n) в каждой точке направлен в сторону наибольшего локального возрастания этой функции:

grad f(x)= .

Если выбрано начальное приближение x=x₀, то каждое очередное вычисляется так:

x_m+1=x_m–a_mgrad f(x_m),

где значение a_m определяет величину шага и может быть вычислено как наименьший положительный корень скалярного уравнения

(x_m–a_mgrad f(x_m))=0.

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

Теперь еще о величине шага. При наличии погрешностей в определении значения целевой функции шаг должен убывать по мере приближения к цели, т.е. его величина должна быть членом последовательности беззнаковых чисел, удовлетворяющей условию lim a_n=0 при n→¥ . Сумма членов этой последовательности должна расходиться , а сумма квадратов – сходиться . Мы уже рассматривали эти условия Дворецкого при изучении методов поиска корня в условиях помех. Кестен показал, что асимптотическая сходимость может быть заменена затухающим колебательным процессом, если длину шага уменьшать по гармоническому закону только после того, как соответствующая составляющая градиента поменяет знак.

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