Градиентный спуск

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса.

Описание[править | править вики-текст]

Иллюстрация последовательных приближений к точке экстремума в направлении наискорейшего спуска (красн.) в случае дробного шага. Синим отмечены линии уровня.

Пусть целевая функция имеет вид:

F(\vec{x}):\;\mathbb{X}\to\mathbb{R}.

И задача оптимизации задана следующим образом:

F(\vec{x})\to\min_{\vec{x}\in\mathbb{X}}\!

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом -\nabla F:

\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]}) \!

где \lambda^{[j]} выбирается

  • постоянной, в этом случае метод может расходиться;
  • дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
  • наискорейшим спуском: \lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda\nabla F(\vec{x}^{[j]})) \!

Алгоритм[править | править вики-текст]

  1. Задают начальное приближение и точность расчёта \vec{x}^0, \quad \varepsilon
  2. Рассчитывают \overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]}) \!, где \lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda\nabla F(\vec{x}^{[j]})) \!
  3. Проверяют условие остановки:
    • Если |\vec{x}^{[j+1]}-\vec{x}^{[j]}|>\varepsilon\!, |F(\vec{x}^{[j+1]})-F(\vec{x}^{[j]})|>\varepsilon\! или  \| \nabla F(\vec{x}^{[j+1]}) \| > \varepsilon (выбирают одно из условий), то j=j+1 и переход к шагу 2.
    • Иначе \vec{x}=\vec{x}^{[j+1]}\! и останов.

Соотношение Канторовича[править | править вики-текст]

Для квадратичной функции вида \frac{x^T \Gamma x }{2} + c^T x, \Gamma^T=\Gamma метод наискорейшего градиентного поиска сходится из любой начальной точки x_0 со скоростью геометрической прогрессии (линейно) со знаменателем, не превосходящим значение q. При этом справедливы следующие оценки:

\exists a=a(x_0), T>0: 0 \le a \le q = \frac{\left ( \lambda_{min} / \lambda_{max} - 1 \right )^2}{\left ( \lambda_{min} / \lambda_{max} + 1 \right )^2},

f(x_k)<f(x^*) \le a^k (f(x_0)-f(x^*)) ,

\|x_k - x^* \| \le T a^{k/2} \| x_0 - x^* \|,

где \lambda_{min} и  \lambda_{max} - минимальное и максимальное собственные числа числа матрицы вторых производных \nabla^2 f(x) = \Gamma.

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

Пример[править | править вики-текст]

Применим градиентный метод к функции F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y). Тогда последовательные приближения будут выглядеть так:

Градиентный метод в действии. Иллюстрация для линий равного уровня.Градиентный метод в действии. Иллюстрация для поверхности.

Это типичный пример овражной функции. Градиентный метод "прыгает" с одного склона оврага на другой и обратно, иногда почти не двигаясь в нужном направлении, что существенно замедляет сходимость. Другим примером тестовой овражной функции является функция Розенброка.

Усовершенствования[править | править вики-текст]

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

Для функций близких к квадратичным эффективным является метод сопряжённых градиентов.

Метод наискорейшего спуска python 2.7[править | править вики-текст]

import numpy
import math
from pylab import *
from sympy import *
from scipy.optimize import minimize_scalar
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import axes3d, Axes3D
 
z_str = '3 * a[0] ** 2 + a[1] ** 2 - a[0] * a[1] - 4 * a[0]'
 
exec 'z = lambda a: ' + z_str
 
z_str = z_str.replace('a[0]', 'x')
z_str = z_str.replace('a[1]', 'y')
 
def z_grad(a):
    x = Symbol('x')
    y = Symbol('y')
 
    exec 'z_d =  ' + z_str
 
    yprime = z_d.diff(y)
    dif_y=str(yprime).replace('y', str(a[1]))
    dif_y=dif_y.replace('x', str(a[0]))
 
    yprime = z_d.diff(x)
    dif_x=str(yprime).replace('y', str(a[1]))
    dif_x=dif_x.replace('x', str(a[0]))
 
    return numpy.array([eval(dif_y), eval(dif_x)])
 
def mininize(a):
    l_min = minimize_scalar(lambda l: z(a - l * z_grad(a))).x
    return a - l_min * z_grad(a)
 
def norm(a):
    return math.sqrt(a[0] ** 2 + a[1] ** 2)
 
def grad_step(dot):
    return mininize(dot)
 
dot = [numpy.array([-150.0, 150.0])]
dot.append(grad_step(dot[0]))
 
eps = 0.0001
 
while norm(dot[-2] - dot[-1]) > eps: dot.append(grad_step(dot[-1]))
def makeData ():
    x = numpy.arange (-200, 200, 1.0)
    y = numpy.arange (-200, 200, 1.0)
    xgrid, ygrid = numpy.meshgrid(x, y)
    zgrid = z([xgrid, ygrid])
    return xgrid, ygrid, zgrid
 
xt, yt, zt = makeData()
 
fig = plt.figure()
ax = plt.axes(projection='3d')
 
ax.plot_surface(xt, yt, zt, cmap=cm.hot)
ax.plot([x[0] for x in dot], [x[1] for x in dot], [z(x) for x in dot], color='b')
 
plt.show()

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986. — С. 298-311.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
  7. С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. — Нижний Новгород: Издательство Нижегородского Университета, 2007. — С. 357-363.