2015-04-01
436
Метод наискорейшего спуска является итерационным, относится
к методам первого порядка и на каждой итерации требует вычисления
n частных производных минимизируемой функции.
Как и в § 2.2, решаем задачу (2.1.1): найти x * Î En, для которого выполнено условие
f (x *) = min f (x),
x Î En
где x = (x 1, x 2, …, xn) т – вектор варьируемых параметров x 1, x 2, …, xn; n – размерность вектора х; f (x) – вещественная скалярная функция векторного аргумента или функция n -переменных; En – n- мерное евклидово пространство.
Метод решения этой задачи представим в виде
x (k + 1) = x (k) + a ks (k), k = 0, 1, 2, …, (2.3.1)
т. е. начиная с некоторой начальной точки x (0) Î En строится последовательность точек x ( k ) Î En, k = 1, 2, …, которая в общем случае бесконечна и, если метод корректен, должна сходиться к x * Î En – точке минимума функции f (x).
Как известно, вектор градиента Ñ f (x) функции f (x)
Ñ f (x) = (¶f (x)/ ¶x 1, ¶f (x)/ ¶x 2, …, ¶f (x)/ ¶xn)т, (2.3.2)
вычисленный в точке x, задает направление наискорейшего возрастания f (x) при движении из данной точки. Модуль градиента при этом численно равен скорости возрастания. Тогда вектор Ñ f (x), обратный по направлению вектору градиента, указывает направление наискорейшего убывания f (x) при движении из точки x. Поэтому естественным является желание выбирать вектор Ñ f (x ( k )) в качестве вектора s ( k ) на каждом шаге процесса
|
|
|
s (k) = –Ñ f (x (k)) (2.3.3)
в предложении, что такой выбор будет способствовать максимально быстрому убыванию функции f (x) при переходе от x ( k ) к x ( k + 1)и в конечном счете приведет к наиболее быстрому определению ее минимума.
Метод наискорейшего спуска можно представить в виде следующего алгоритма:
1. Начать с x (0) Î En, задав e > 0 и k = 0.
2. Вычислить Ñ f (x ( k )) = (¶f (x ( k ))/ ¶x 1, ¶f (x ( k ))/ ¶x 2, …, ¶f (x ( k ))/ ¶xn)т.
3. Если || Ñ f (x ( k )) | | £ e, перейти к выполнению п. 7.
4. Найти a k из решения задачи минимизации функции одной переменной
j(a k) = min {j(a) = f (x (k) – a Ñ f (x (k))}. (2.3.4)
a > 0
5. Вычислить x ( k + 1) по формуле
x (k + 1) = x (k) – a k Ñ f (x (k)). (2.3.5)
6. Если || x ( k + 1) – x ( k ) | | / | | x ( k ) || £ e, перейти к выполнению п. 8.
7. Положить k: = k + 1 и перейти к выполнению п. 2.
8. Процесс окончен: x ( k ) – искомая точка минимума функции f (x).
Отметим некоторые важные свойства метода наискорейшего спуска:
1. Является итерационным, относится к методам первого порядка и на каждой итерации требует вычисления n частных производных минимизируемой функции.
2. Для решения одномерной задачи (2.3.4) при выполнении п. 4 алгоритма на каждом шаге может быть использован любой из методов одномерной минимизации. На практике точное решение большого числа одномерных оптимизационных задач не всегда желательно из-за роста вычислительных затрат, поэтому часто ограничиваются достаточно хорошими приближенными решениями, что без видимого ухудшения скорости сходимости метода может существенно уменьшить общий объем вычислительной работы на каждом шаге алгоритма.
|
|
|
3. Демонстрирует хорошие свойства и скорость сходимости на большом удалении от точки локального минимума функции f (x). В непосредственной близости от этой точки существенно ухудшаются практические свойства метода, что вызвано так называемыми "овражными" эффектами. В результате длина шагов значительно уменьшается, вычислительная устойчивость метода падает, поэтому часто не достигается требуемой точности определения решения задачи.
