Основная идея метода градиентного спуска

Для иллюстрации основной идеи метода градиентного спуска рассмотрм следующий пример. Пусть нам необходимо спуститься на дно оврага темной безлунной ночью. (Ночь, темно и не видать ни зги). Как нам поступить?
Рассмотрим сначала алгоритм метода покоординатного спуска. Если в нашем распоряжении имеется компас (система координат), можно воспользоваться им для выбора направления спуска. Тогда можно, выбрав направление движения на восток (по координате x), двигаться до тех пор, пока спуск в этом направлении продолжается. Рано или поздно должен наступить момент, когда дальнейший спуск в восточном направлении прекратится (продолжение движения на восток приведет к необходимости не спускаться, а подниматься по склону). В этот момент мы меняем направление с восточного на северное (фиксируем достигнутое значение x и начинаем двигаться по координате y) до тех пор, пока будет возможен спуск в северном направлении (направлении y). После того как возможность спуска в северном направлении будет исчерпана, мы снова меняем направление, на этот раз с северного опять на восточное, переходя таким образом в избранном нами методе покоординатного спуска к следующей итерации (эта песня хорша, начинай сначала).
Отличие метода градиентного спуска от метода покоординатного спуска заключается в выборе направления спуска: вместо того чтобы сразу, не зная броду, начать движение на восток, чтобы потом сменить направление движения на север, мы до начала движения нащупываем ногами почву под ногами, чтобы узнать, в каком направлении на следует двигаться, чтобы быстрее спускаться вниз. Как найти это направление не чисто-конкретно-технически ногами, а математически? Уравнение z=f(x,y) считаем заданным (известным). Для скалярной функции двух переменных z=f(x,y) в математике вводится понятие о ее градиенте, − это вектор, компоненты которого равны частным производным от функции f(x,y) по x и по y. Если выбрать компас (ввести систему координат xOy), то вектор градиента функции z=f(x,y) будет иметь следующие компоненты:
gradz= i ·∂f(x,y)/∂x + j ·∂f(x,y)/∂y
где i и j − единичные орты системы координат xOy (i направлен на восток, а j − на север).
Прощупывание ногами почвы под ногами означает вычисление значений компонент вектора градиента ∂f(x,y)/∂x и ∂f(x,y)/∂y эмпирическим методом "тыка". При этом следует иметь в виду одно существенное обстоятельство: вектор градиента направлен в сторону максимальной скорсоть подъема, а не спуска. И для того, чтобы выбрать нужное направление спуска, необходимо выбрать обратное к нему направление, которое математики иногда называют направлением антиградиента.
Основная идея градиентного метода спуска заключается в выборе направления спуска: на каждой итерации выбирается направление антиградиента. А вот с какой скоростью бежать вниз, и какие при этом проводить дополнительные манипуляции, зависит уже от той или иной разновидности метода градиентного спуска.
На рис. 16.7 представлена графическая интепретация метода градиентного спуска. На рисунке видно, что спуск в направлении антиградиента закначивается в тот момент, когда направление спуска касается линии (поверхности) уровня. Следовательно, в точках касания необходимо изменять направление спуска. Разумно выбрать с этой целью направление, перепендикулярное линии уровня, которое указывает направление наискорейшего спуска из точки касания.

Рис. 16.7. Метод градиентного спуска

Заметим, что градиентные методы позволяют найти решение любой задачи нелинейного программирования, однако в общем случае их применение позволяет найти точку локального экстремума. По этой причине целесообразно исопльзовать градиентные методы для тех задач, в которых всякий локальный экстремум является одновременно и глобальным. В том случае, когда задача нелинейного программирования имеет ограничения в форме равенств или неравенств, к описанной выше вербальной схеме необходимо добавить новые элементы. Так, если речь идет о задаче с ограничениями-неравенствами, необходимо на склоне поставить соответствующие заборы с часовыми на вышках и их окликами: "Стой, кто идет?" И далее - в зависимости от обстановки. Есть мтеоды решения задач нелинейного программирования, в которых через эти заборы прыгать нельзя. А есть и такие методы, в которых допускаются варианты "за флажки, жажда к жизни сильней!". Если же рассматривается задача с ограничениями в форме равенств, то на склоне нужно прочертить тропинки, по которым можно ходить туда-сюда, туда-сюда, в поисках счастья, то бишь, заветного донышка. И тут уж не до глобального минимума (" развязали − да вилки попрятали") − найти бы синицу в руках − локальный минимум на той тропинке, по которой ходить пока еще можно.

11.8.2. Простейший вариант реализации метода градиентного спуска

В самом простом варианте реализации основной идеи метода градиентного спуска исходят из необходимого условия экстремума функции многих переменных, в соответстви с которым в точке минимума (на самом дне) градент равен нулю. Для функции двух переменных это означает, что ∂f(x*,y*)/∂x=0 и ∂f(x*,y*)/∂y=0, где x*,y* − координаты дна (не обязательно глобального). Пусть x₀, y₀ − начальное приближение (координаты точки, из которой начинается спуск). Тогда можно поступить следующим образом. Рассмотрим уравнение
gradz= i ·∂f(x,y)/∂x + j ·∂f(x,y)/∂y=0
Координаты дна (x*,y*) этому уравнению удовлетворяют, что означает, что одновременно обе компоненты веткора градиента в точке (x*,y*) должны обращаться в нуль:
∂f(x*,y*)/∂x =0
∂f(x*,y*)/∂y =0
Рассмотрим следующую задачу:
∂f(x,y)/∂x =0
∂f(x,y)/∂y =0
откуда необходимо найти значения x и y. В соответствии с общей идеей классического метода итераций можно поступить следующим образом.
При k=0 примем, что x^(k)=x⁽⁰⁾=x₀ и y^(k)=y⁽⁰⁾=y₀, т.е. стартуем из точки начального приближения. Тогда первое приближение находим очень просто
x⁽¹⁾ = x⁽⁰⁾ − ∂f(x⁽⁰⁾,y⁽⁰⁾)/∂x
y⁽¹⁾ = y⁽⁰⁾ − ∂f(x⁽⁰⁾,y⁽⁰⁾)/∂y
Здесь в правых частях поставлен знак "−", что указывает на то обстоятельство, что первый шаг мы делаем в направлении антиградиента, т.е. в сторону убывания функции z=f(x,y). Аналогичным образом можно сделать следующий шаг, выбрав в качестве исходной точки теперь уже точку (x⁽¹⁾,y⁽¹⁾). Как говорится, далее по расписанию:
x^(k+1) = x^(k) − ∂f(x^(k),y^(k))/∂x
y^(k+1) = y^(k) − ∂f(x^(k),y^(k))/∂y
В данном случае длина шага в направлении антиградиента
Обобщение на случай функции n переменных f(x), x=(x₁,x₂,...,x_n) может быть записано в следующем виде
x_1(k+1) = x_1(k) − ∂f(x_1(k),x_2(k),...,x_n(k))/∂x₁
x_2(k+1) = x_2(k) − ∂f(x_1(k),x_2(k),...,x_n(k))/∂x₂
...
x_n(k+1) = x_n(k) − ∂f(x_1(k),x_2(k),...,x_n(k))/∂x_n
причем x₍₀₎=(x₁₍₀₎,x₂₍₀₎,...,x_n(0))=x₀ где x₀=(x₁₍₀₎,x₂₍₀₎,...,x_n(0)) − начальное приближение.
В векторной форме полученную схему итерационного процесса можно записать в виде
x^(k+1) = x^(k) − f′(x^(k))
где x^(k) − вектор k-того приближения, f′ − вектор первых производных функции f(x)

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

1. условие малости приращения аргумента |x^(k+1) − x^(k)| <ε

2. условие малости градиента |f′(x^(k))|<γ

Здесь ε и γ − заданные малые величины. Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий.