Метод градиентного спуска
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad1.PNG" \o "Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, \"уменьшенному в раз\"." INCLUDEPICTURE "http://www.machinelearning.ru/wiki/images/thumb/f/f6/Grad1.PNG/500px-Grad1.PNG" \* MERGEFORMATINET 
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad1.PNG" \o "Увеличить" INCLUDEPICTURE "http://www.machinelearning.ru/wiki/skins/common/images/magnify-clip.png" \* MERGEFORMATINET 
Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda" \* MERGEFORMATINET раз".
Идея метода
Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?-\\nabla%20f" \* MERGEFORMATINET :
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x%5e%7b%5bk+1%5d%7d=x%5e%7b%5bk%5d%7d-\\lambda%5e%7b%5bk%5d%7d\\nabla%20f(x%5e%7b%5bk%5d%7d)%20" \* MERGEFORMATINET
где INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET выбирается
постоянной, в этом случае метод может расходиться;
дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
наискорейшим спуском: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d=\\arg\\min_%7b\\lambda%7d%20\\,f(x%5e%7b%5bk%5d%7d-\\lambda\\nabla%20f(x%5e%7b%5bk%5d%7d))%20" \* MERGEFORMATINET
Алгоритм
Вход: функция INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f:%20\\mathbb%7bR%7d%5en%20\\to%20\\mathbb%7bR%7d" \* MERGEFORMATINET
Выход: найденная точка оптимума INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x" \* MERGEFORMATINET
Повторять:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x%5e%7b%5bk+1%5d%7d=x%5e%7b%5bk%5d%7d-\\lambda%5e%7b%5bk%5d%7d\\nabla%20f(x%5e%7b%5bk%5d%7d)%20" \* MERGEFORMATINET , где INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET выбирается одним из описанных выше способов
если выполен критерий останова, то возвращаем текущее значение INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x%5e%7b%5bk+1%5d%7d" \* MERGEFORMATINET
Критерий останова
Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||x%5e%7b%5bk+1%5d%7d-x%5e%7b%5bk%5d%7d||\\leq\\eps" \* MERGEFORMATINET
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f(x%5e%7b%5bk+1%5d%7d)-f(x%5e%7b%5bk%5d%7d)||\\leq\\eps" \* MERGEFORMATINET
Здеcь INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x%5e%7b%5bk%5d%7d%20\\in%20\\mathbb%7bR%7d%5en" \* MERGEFORMATINET - значение, полученное после INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?k" \* MERGEFORMATINET -го шага оптимизации. INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\eps" \* MERGEFORMATINET - наперед заданное положительное число.
Сходимость градиентного спуска с постоянным шагом
Теорема 1 о сходимости метода градиентного спуска спуска с постоянным шагом.
Пусть INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d=\\lambda=const" \* MERGEFORMATINET , функция INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f" \* MERGEFORMATINET дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f'(x)" \* MERGEFORMATINET : INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f'(x)-f'(y)||%20\\leq%20L%20||x-y||" \* MERGEFORMATINET . Пусть INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?0%3c\\lambda%3c2/L" \* MERGEFORMATINET .
Тогда INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lim_%7bk%20\\to%20\\infty%7df'(x%5e%7b%5bk%5d%7d)%20=%200,%20\\;%20f(x%5e%7b%5bk+1%5d%7d)%3cf(x%5e%7b%5bk%5d%7d)%20" \* MERGEFORMATINET при любом выборе начального приближения.
В условиях теоремы градиентный метод обеспечивает сходимость INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\%7b%20x%5e%7b%5bk%5d%7d%20\\%7d" \* MERGEFORMATINET либо к точной нижней грани INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\inf_x%20f(x)" \* MERGEFORMATINET (если функция INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x)" \* MERGEFORMATINET не имеет минимума) либо к значению INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x*):%20\\;\\lim_%7bk%20\\to%20\\infty%7dx%5e%7b%5bk%5d%7d%20=%20x*,\\;%20f'(x*)=0." \* MERGEFORMATINET Существуют примеры, когда в точке INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x*" \* MERGEFORMATINET реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.
Определение. Дифференцируемая функция INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f" \* MERGEFORMATINET называется сильно выпуклой (с константой INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\Lambda%3e0" \* MERGEFORMATINET ), если для любых INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x" \* MERGEFORMATINET и INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?y" \* MERGEFORMATINET из INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\mathbb%7bR%7d%5en" \* MERGEFORMATINET справедливо
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x+y)\\geq%20f(x)+%20\\langle%20f'(x)%20,y%20\\rangle%20+%20\\Lambda||y||%5e2/2%20." \* MERGEFORMATINET
Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.
Пусть функция INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f" \* MERGEFORMATINET дифференцируема, сильно выпукла с константой INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\Lambda" \* MERGEFORMATINET . Пусть выполняется условие Липшица для градиента INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f'(x)" \* MERGEFORMATINET : INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f'(x)-f'(y)||%20\\leq%20L%20||x-y||" \* MERGEFORMATINET . Пусть INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?0%3c\\lambda%3c2/L" \* MERGEFORMATINET .
Тогда INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lim_%7bk%20\\to%20\\infty%7dx%5e%7b%5bk%5d%7d%20=%20x*,%20\\;%20||x%5e%7b%5bk%5d%7d-x*||\\leq%20q%5ek%20||x%5e%7b%5b0%5d%7d-x*||,%20\\;%20q%20=%20\\max\\%7b|1-\\lambda\\Lambda|,%20|1-\\lambda%20L%20|\\%7d" \* MERGEFORMATINET при любом выборе начального приближения.
Выбор оптимального шага
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad3.PNG" \o "Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо." INCLUDEPICTURE "http://www.machinelearning.ru/wiki/images/thumb/f/ff/Grad3.PNG/500px-Grad3.PNG" \* MERGEFORMATINET 
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad3.PNG" \o "Увеличить" INCLUDEPICTURE "http://www.machinelearning.ru/wiki/skins/common/images/magnify-clip.png" \* MERGEFORMATINET 
Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.
Константа INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?q" \* MERGEFORMATINET , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda" \* MERGEFORMATINET . Нетрудно видеть, что величина INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?q=q(\\lambda)=\\max\\%7b|1-\\lambda\\Lambda|,%20|1-\\lambda%20L%20|\\%7d" \* MERGEFORMATINET минимальна, если шаг INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda" \* MERGEFORMATINET выбирается из условия INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?|1-\\lambda\\Lambda|%20=%20|1-\\lambda%20L%20|" \* MERGEFORMATINET , т. е. если INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?%20\\lambda%20=%20\\lambda*%20=%202/(\\Lambda%20+%20L)" \* MERGEFORMATINET .
При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?q=q*=\\frac%7bL-\\Lambda%7d%7bL+\\Lambda%7d" \* MERGEFORMATINET .
В качестве INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\Lambda" \* MERGEFORMATINET и INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?L" \* MERGEFORMATINET могут выступать равномерные по x оценки сверху и снизу собственных значений оператора INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f''(x)" \* MERGEFORMATINET . Если INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%20%3c%3c%20\\Lambda" \* MERGEFORMATINET , то INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?q*\\approx%201" \* MERGEFORMATINET и метод сходится очень медленно. Геометрически случай INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%20%3c%3c%20\\Lambda" \* MERGEFORMATINET соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?%20\\mathbb%7bR%7d%5e2%20" \* MERGEFORMATINET , задаваемая формулой:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x_1,x_2)=\\Lambda%20x_1%5e2%20+%20L%20x_2%5e2,%20\\;%20\\Lambda%20%3c%3c%20L" \* MERGEFORMATINET .
Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\mu%20=%20L/\\Lambda%20" \* MERGEFORMATINET (характеризующее, грубо говоря, разброс собственных значений оператора INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f''(x)" \* MERGEFORMATINET ) называют числом обусловленности функции INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f" \* MERGEFORMATINET . Если INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\mu%20%3e%3e%201" \* MERGEFORMATINET , то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Далее будут описаны два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.
Градиентный метод с дроблением шага
В этом варианте градиентного метода величина шага INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET на каждой итерации выбирается из условия выполнения неравенства
(2)
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x%5e%7b%5bk+1%5d%7d)%20=%20f(x%5e%7b%5bk%5d%7d-\\lambda%5e%7b%5bk%5d%7d%20f'(x%5e%7b%5bk%5d%7d))%20\\leq%20f(x%5e%7b%5bk%5d%7d)-\\eps%20\\lambda%5e%7b%5bk%5d%7d||f'(x%5e%7b%5bk%5d%7d)||%5e2%20" \* MERGEFORMATINET ,
где INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\eps%20\\in%20(0,%201)%20" \* MERGEFORMATINET - некоторая заранее выбранная константа.
Процедуру нахождения такого INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET обычно оформляют так. Выбирается число INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\delta%20\\in%20(0,%201)" \* MERGEFORMATINET и некоторый начальный шаг INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5b0%5d%7d" \* MERGEFORMATINET . Теперь для каждого k полагают INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d=\\lambda%5e%7b%5b0%5d%7d" \* MERGEFORMATINET и делают шаг градиентного метода. Если с таким INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET условие HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0" \l "eq:2#eq:2" \o "" (2) выполняется, то переходят к следующему k. Если же HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0" \l "eq:2#eq:2" \o "" (2) не выполняется, то умножают INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET на INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\delta" \* MERGEFORMATINET ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0" \l "eq:2#eq:2" \o "" (2) не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET .
Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET на каждом шаге, заменяя ее на проблему выбора параметров INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?%20\\eps,\\;\\delta" \* MERGEFORMATINET и INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5b0%5d%7d" \* MERGEFORMATINET , к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
Метод наискорейшего спуска
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad2.PNG" \o "Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L." INCLUDEPICTURE "http://www.machinelearning.ru/wiki/images/thumb/3/34/Grad2.PNG/500px-Grad2.PNG" \* MERGEFORMATINET 
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:Grad2.PNG" \o "Увеличить" INCLUDEPICTURE "http://www.machinelearning.ru/wiki/skins/common/images/magnify-clip.png" \* MERGEFORMATINET 
Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET выбирается так, чтобы следующая итерация была точкой минимума функции INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f" \* MERGEFORMATINET на луче L.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?x%5e%7b%5bk%5d%7d" \* MERGEFORMATINET будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?L=\\%7bx=x%5e%7b%5bk%5d%7d-\\lambda%20f'(x%5e%7b%5bk%5d%7d);\\;%20\\lambda%20\\leq%200%7d%20" \* MERGEFORMATINET :
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d%20=%20\\arg\\min_%7b%20\\lambda\\in%20%5b0,%20\\infty)%7d%20f(x%5e%7b%5bk%5d%7d-\\lambda%20f'(x%5e%7b%5bk%5d%7d))" \* MERGEFORMATINET .
Другими словами, INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda%5e%7b%5bk%5d%7d" \* MERGEFORMATINET выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Числовые примеры
Метод градиентного спуска с постоянным шагом
Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x_1,x_2)=10*x_1%5e2+x_2%5e2" \* MERGEFORMATINET .
Начальное приближение - точка (10,10). Использован критерий останова: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f(x%5e%7b%5bk+1%5d%7d)-f(x%5e%7b%5bk%5d%7d)||\\leq%2010%5e%7b-5%7d" \* MERGEFORMATINET
Результаты эксперимента отражены в таблице:
Из полученных результатов можно сделать вывод, что при слишком большом чаге метод расходится, при слишком малом сходится медленно и точчность хуже. Надо выбирать шаг наибольшим из тех, при которых метод сходится.
Градиентный метод с дроблением шага
Для исследования сходимости метода градиентного спуска с дроблением шага HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0" \l "eq:2#eq:2" \o "" (2) была выбрана функция:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x_1,x_2)=10*x_1%5e2+x_2%5e2" \* MERGEFORMATINET .
Начальное приближение - точка (10,10). Использован критерий останова: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f(x%5e%7b%5bk+1%5d%7d)-f(x%5e%7b%5bk%5d%7d)||\\leq%2010%5e%7b-5%7d" \* MERGEFORMATINET
Результаты эксперимента отражены в таблице:
Из полученных результатов можно сделать вывод об оптимальном выборе параметров: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?%20\\eps%20=0.1,\\;%20%20\\delta=0.95,\\;%20%20\\lambda%5e%7b%5b0%5d%7d=1%20" \* MERGEFORMATINET , хотя метод не сильно чувствителен к выбору параметров.
Метод наискорейшего спуска
Для исследования сходимости метода наискорейшего спуска была выбрана функция:
INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?f(x_1,x_2)=10*x_1%5e2+x_2%5e2" \* MERGEFORMATINET .
Начальное приближение - точка (10,10). Использован критерий останова: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?||f(x%5e%7b%5bk+1%5d%7d)-f(x%5e%7b%5bk%5d%7d)||\\leq%2010%5e%7b-5%7d" \* MERGEFORMATINET
Для решения одномерных задач оптимизации использован HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F._%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B" \o "Метод золотого сечения. Симметричные методы" метод золотого сечения.
Метод получил точность 6e-8 за 9 итераций.
Отсюда можно сделать вывод, что метод наискорейшего спуска сходится быстрее, чем градиентный метод с дроблением шага и метод градиентного спуска с постоянным шагом.
Недостатком методом наискорейшего спуска явлляется необходимость решать одномерную задачу оптимизации.
Рекомендации программисту
При программировании методов градиентного спуска следует аккуратно относится к выбору параметров, а именно
Метод градиентного спуска с постоянным шагом: шаг INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?\\lambda" \* MERGEFORMATINET следует выбирать меньше 0.01, иначе метод расходится (метод может расходится и при таком шаге в зависимости от исследуемой функции).
Градиентный метод с дроблением шага не очень чувствителен к выбору параметров. Один из вариантов выбора параметров: INCLUDEPICTURE "http://www.machinelearning.ru/mimetex/?%20\\eps%20=0.1,\\;%20%20\\delta=0.95,\\;%20%20\\lambda%5e%7b%5b0%5d%7d=1%20" \* MERGEFORMATINET
Метод наискорейшего спуска: в качестве метода одномерной оптимизации можно использовать HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F._%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B" \o "Метод золотого сечения. Симметричные методы" метод золотого сечения (когда он применим).
Заключение
Методы градиентного спуска являются достаточно мощным инструментом решения задач оптимизации. Главным недостатком методов является ограниченная область применимости.
Ссылки
HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%BC_%D0%9C%D0%9C%D0%9F_%D0%92%D0%9C%D0%9A%2C_4%D0%B9_%D0%BA%D1%83%D1%80%D1%81%2C_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C_2008" \o "Практикум ММП ВМК, 4й курс, осень 2008" Практикум ММП ВМК, 4й курс, осень 2008
HYPERLINK "http://www.machinelearning.ru/wiki/images/0/0d/GradientDescent.zip" \o "GradientDescent.zip" Код методов градиентного спуска, ZIP [2Кб]
Список литературы
Н.Н.Калиткин.  Численные методы. Москва «Наука», 1978.
Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов. Методы оптимизации. 2000.
Р.Р.Ахмеров.  Методы оптимизации гладких функций.
Источник — « HYPERLINK "http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0" http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0»