Метод наискорейшего спуска (в англ. литературе «method of steepest descent») - это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:
- это значения аргумента функции (управляемые параметры) на вещественной области.
В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:
где i, j,…, n - единичные векторы, параллельные координатным осям.
Градиент в базовой точке 
строго ортогонален к поверхности, а его направление показывает направление наискорейшего возрастания функции, а противоположное направление (антиградиент), соответственно, показывает направление наискорейшего убывания функции.
Метод наискорейшего спуска является дальнейшим развитием метода градиентного спуска. В общем случае процесс нахождения экстремума функции является итерационной процедурой, которая записывается следующим образом:
где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;
Единичный вектор направления, который определяется по формуле:
- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента:
Константа, определяющая размеры шага и одинаковая для всех i-х направлений.
Величина шага выбирается из условия минимума целевой функции f(х) в направлении движения, т. е. в результате решения задачи одномерной оптимизации в направлении градиента или антиградиента:
Другими словами, величину шага определяют при решении данного уравнения:
Таким образом, шаг расчета выбирается такой величины, что движение выполняется до тех пор, пока происходит улучшение функции, достигая, таким образом, экстремума в некоторой точке. В этой точке вновь определяют направление поиска (с помощью градиента) и ищут новую точку оптимума целевой функции и т.д. Таким образом, в данном методе поиск происходит более крупными шагами, и градиент функции вычисляется в меньшем числе точек.
В случае функции двух переменных данный метод имеет следующую геометрическую интерпретацию: направление движения из точки касается линии уровня в точке . Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Условие ортогональности векторов направлений спуска в соседних точках записывается следующим выражением:
Траектория движения к точке экстремума при использовании метода наискорейшего спуска, изображенная на графике линии равного уровня функции f(x)
Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):
Траектория поиска остается в малой окрестности текущей точки поиска:
Приращение целевой функции не меняется:
Градиент целевой функции в точке локального минимума обращается в нуль:
Следует отметить, что метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Овраг представляет собой впадину, линии уровня которой приближенно имеют форму эллипсов с различающимися во много раз полуосями. При наличии оврага траектория спуска имеет вид зигзагообразной линии с малым шагом, вследствие чего результирующая скорость спуска к минимуму сильно замедляется. Это объясняется тем, что направление антиградиента этих функций существенно отклоняется от направления в точку минимума, что приводит к дополнительной задержке в расчете. В результате алгоритм теряет вычислительную эффективность.
Овражная функция
Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции. Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек. Так же скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска.
Методика расчета
1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции
2 шаг : Задаем начальное приближение
3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.
Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .
Описание [ | ]
Усовершенствования [ | ]
Метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Для борьбы с этим явлением используется, суть которого очень проста. Сделав два шага градиентного спуска и получив три точки, третий шаг следует сделать в направлении вектора, соединяющего первую и третью точку, вдоль дна оврага.
Для функций, близких к квадратичным, эффективным является метод сопряжённых градиентов .
Применение в искусственных нейронных сетях [ | ]
Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.
Ссылки [ | ]
- J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)
Литература [ | ]
- Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
- Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
- Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
- С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.
Правила ввода функции
В методе наискорейшего спуска
в качестве направления поиска выбирается вектор, направление которого противоположно направлению вектора градиента функции ▽f(x). Из математического анализа известно, что вектор grad f(x)=▽f(x) характеризует направление наиболее быстрого возрастания функции (см. градиент функции). Поэтому вектор - grad f (X) = -▽f(X) называется антиградиентом
и является направлением наиболее быстрого ее убывания. Рекуррентное соотношение, с помощью которого реализуется метод наискорейшего спуска, имеет вид X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
где λ k >0 - величина шага. В зависимости от выбора величины шага можно получить различные варианты градиентного метода. Если в процессе оптимизации величина шага λ фиксирована, то метод носит название градиентного метода с дискретным шагом. Процесс оптимизации на первых итерациях можно значительно ускорить, если λ k выбирать из условия λ k =min f(X k + λS k) .
Для определения λ k используется любой метод одномерной оптимизации. В этом случае метод называется методом наискорейшего спуска. Как правило, в общем случае недостаточно одного шага для достижения минимума функции, процесс повторяют до тех пор, пока последующие вычисления позволяют улучшать результат.
Если пространство очень вытянуто по некоторым переменным, то образуется “овраг”. Поиск может замедлиться и идти зигзагами поперек дна “оврага”. Иногда решение невозможно получить за приемлемое время.
Еще одним недостатком метода может быть критерий остановки ||▽f(X k)|| <ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Пример
. Начиная из точки x k =(-2, 3) определите точку x k +1 методом наискорейшего спуска для минимизации функции .
В качестве направления поиска выберем вектор градиент в текущей точке
Проверим критерий остановки . Имеем 
Вычислим значение функции в начальной точке f(X 1) = 35. Сделаем
шаг вдоль направления антиградиента
Вычислим значение функции в новой точке
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
или f’(X 2) = 2598 λ 1 – 425 = 0.
Получим шаг λ 1 = 0.164
Выполнение этого шага приведет в точку
в которой значение градиента 
, значение функции f(X 2) = 0.23. Точность не достигнута, из точки делаем шаг вдоль направления антиградиента .
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Получаем λ 1 = 0.52
Аннотация: В данной лекции широко освещены такие методы многопараметрической оптимизации как метод наискорейшего спуска и метод Давидона – Флетчера – Пауэлла. Кроме того, проводится сравнительный анализ вышеперечисленных методов с целью определения наиболее действенного, выявляются их преимущества и недостатки; а также рассматриваются проблемы многомерной оптимизации, такие как метод оврагов и метод многоэкстремальности.
1. Метод наискорейшего спуска
Суть данного метода заключается в том, что с помощью упомянутого ранее метода покоординатного спуска осуществляется поиск из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении. Затем поиск производится в направлении, параллельном другой оси, и т.д. Направления, конечно, фиксированы. Кажется разумным попытаться модифицировать этот метод таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль "наилучшего" направления. Не ясно, какое направление является "наилучшим", но известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство может быть обосновано следующим образом.
Предположим, что осуществляется перемещение из точки x в следующую точку х + hd , где d - некоторое направление, a h - шаг некоторой длины. Следовательно, перемещение производится из точки (x 1 , х 2 , ..., х n) в точку (x 1 + zx 1 , x 2 + zх 2 , ..., х n + zх n) , где
Изменение значений функции определяется соотношениями
| (1.3) |
С точностью до первого порядка zx i , причем частные производные вычисляются в точке x . Как следует выбрать направления d i , удовлетворяющие уравнению (1.2), чтобы получить наибольшее значение изменения функции df ? Здесь возникает задача максимизации с ограничением. Применим метод множителей Лагранжа, с помощью которого определим функцию
Величина df , удовлетворяющая ограничению (1.2), достигает максимума, когда функция
Достигает максимума. Ее производная
Следовательно,
 |
(1.6) |
Тогда di ~ df/dx i и направление d параллельно направлению V/(x) в точке х .
Таким образом, наибольшее локальное возрастание функции для заданного малого шага h имеет место, когда d есть направление Vf(x) или g(х) . Поэтому направлением наискорейшего спуска является направление
В более простом виде уравнение (1.3) можно записать так:
Где - угол между векторами Vf(x) и dx . Для заданной величины dx мы минимизируем df , выбирая , чтобы направление dx совпадало с направлением -Vf(x) .
Замечание . Направление градиента перпендикулярно в любой точке линии постоянного уровня, поскольку вдоль этой линии функция постоянна. Таким образом, если (d 1 , d 2 , ..., d n) - малый шаг вдоль линии уровня, то
И, следовательно,
 |
(1.8) |
