Метод сопряженных градиентов реферат

Обновлено: 07.07.2024

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

1. Первый алгоритм метода

Пусть требуется решить систему линейных алгебраических уравнений

с положительно определенной матрицей A порядка n.
Рассмотрим функционал

представляющий многочлен второго порядка относительно x1, x2, …, xn. Обозначим через решение системы (1), т.е. . В силусимметричности и положительной определенности матрицы, имеем:

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

имеет наибольшее значение. Но

Но среди векторов постоянный длины достигает максимального значения, если имеет направление вектора или ему противоположное. Утверждениедоказано. Будем двигаться из точки в направлении вектора до тех пор, пока функция достигает минимального значения. Это будет при , т.е. при

и принимаем за новое приближение к решению.
В методе сопряженных градиентов следующее приближение находится так. Через точку проведем гиперплоскость (n-1) – го измерения

и через обозначим новую невязку системы

Векторнаправлен по нормали к поверхности в точке , а вектор параллелен касательной плоскости в этой точке. Поэтому

Гиперплоскость (7) проходит через точку , так как

При любом вектор параллелен некоторой нормальной плоскости к поверхности в точке . Найдем среди них тот, который лежит в гиперплоскости (7), т.е. ортогонален к . Из.

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

1. Метод ортогонализации
1.1 Метод ортогонализации в случае симметрической матрицы

(1)
порядка n. Чтобы избежать в дальнейшем путаницы, над векторами поставим черточки. Решение системы будем разыскивать в виде
, (2)
где – n векторов, удовлетворяющих условиям
при (3)
Здесь рассматривается обычное скалярное произведение векторов в n-мерном векторном пространстве, т.е. если и , то . Пусть такие векторы найдены. Как это делается, будет показано ниже. Рассмотрим скалярное произведение обеих частей системы (1) с
(4)
Используя (2) получим:

(5)
или, в силу выбора векторов ,
. (6)
Итак, для определения коэффициентов получили систему с треугольной матрицей. Определитель этой системы равен
. (7)
Следовательно, если , то возможно найти и находятся они без труда.
Особенно легко определятся , если матрица А симметрическая. В этом случае, очевидно,
(8)
и, следовательно,
=0 при . (9)
Тогда система для определения примет вид
(10)

и
. (11)
Метод можно обобщить. Пусть каким-то образом удалось найти систему 2n векторов так, что
=0 при . (12)
Умножая обе части равенства (1) на и используя представление через , как и ранее, получим:
. (13)
Опять получилась система линейных алгебраических уравнений с треугольной матрицей для определения . Несколько усложнив вычисления можно получить систему диагонального вида. Для этого построим три системы векторов , так что имеют место равенства:
(14)
(15)

, (17)
так как при i (18)
и при i>r
(19)
Таким образом,
(20)
Остановимся подробнее на первом из описанных методов. Рассмотрим случай, когда матрица А симметрическая и положительно определенная. Последнее означает, что для любого вектора квадратичная форма его компонент больше или равна нулю, причем равенство нулю возможно в том и только том случае, если вектор нулевой. Как мы видели ранее, нужно построить систему векторов , удовлетворяющих условиям

(26)
Далее поступаем также.
Процесс будет осуществим, так как все . Это же обеспечит нам разрешимость системы для определения коэффициентов . Заметим, что в нашем случае это будет процесс настоящей ортогонализации, если в пространстве векторов ввести новое скалярное произведение при помощи соотношения
. (26)
Нетрудно проверить, что введенное таким способом скалярное произведение будет удовлетворять всем требованиям, которые к нему предъявляются.
При решении системы n уравнений по настоящей схеме требуется произвести
(28)
операций умножения и деления.
1.2 Метод ортогонализации в случае несимметрической матрицы
В случае несимметрической матрицы процесс ортогонализации проводится точно также. Пусть векторы уже построены. Тогда ищется в виде

из которых и определяем и .
Остановимся еще на одном методе ортогонализации. Будем рассматривать строки матрицы А как векторы:
(34)
Ортонормируем эту систему векторов. Первое уравнение системы делим на . При этом получим
(35)
где
(36)
Второе уравнение системы заменится на
(37)
где
(38)
Аналогично поступаем дальше. Уравнение с номером i примет вид

(39)
где

(40)
Процесс будет осуществим, если система уравнений линейно независима. В результате мы придем к новой системе , где матрица С будет ортогональной, т.е. обладает свойством СС¢=I.
Таким образом, решение системы можно записать в виде
. (41)
Практически, вследствие ошибок округления, СС¢ будет отлична от единичной матрицы и может оказаться целесообразным произвести несколько итераций для системы .

2. Метод сопряженных градиентов
2.1 Первый алгоритм метода
Пусть требуется решить систему линейных алгебраических уравнений
(1)
с положительно определенной матрицей A порядка n.
Рассмотрим функционал
, (2)
представляющий многочлен второго порядка относительно x₁, x₂, …, x_n. Обозначим через решение системы (1), т.е. . В силу симметричности и положительной определенности матрицы, имеем:

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

– вектор невязок системы. Покажем, что вектор невязок имеет направление нормали к поверхности в точке . В самом деле, направление нормали совпадает с направлением быстрейшего изменения функции в точке . Это направление мы найдем, если найдем среди векторов , для которых , такой вектор, что

имеет наибольшее значение. Но

Но среди векторов постоянный длины достигает максимального значения, если имеет направление вектора или ему противоположное. Утверждение доказано. Будем двигаться из точки в направлении вектора до тех пор, пока функция достигает минимального значения. Это будет при , т.е. при
. (5)
Вектор

(6)
и принимаем за новое приближение к решению.
В методе сопряженных градиентов следующее приближение находится так. Через точку проведем гиперплоскость (n-1) – го измерения
(7)
и через обозначим новую невязку системы
. (8)
Вектор направлен по нормали к поверхности в точке , а вектор параллелен касательной плоскости в этой точке. Поэтому
. (9)
Гиперплоскость (7) проходит через точку , так как
.
При любом вектор параллелен некоторой нормальной плоскости к поверхности в точке . Найдем среди них тот, который лежит в гиперплоскости (7), т.е. ортогонален к . Из условия ортогональности имеем:

,
или
. (10)
Вектор
(11)
имеет направление нормали к сечению поверхности гиперплоскости (7) в точке . Будем двигаться из точки в направлении вектора до тех пор, пока функция достигнет минимума. Это будет при
. (12)
Вектор

примем за новое приближение к решению системы. Вектор невязок
(13)

имеет направление нормали к поверхности в точке . Покажем, что он будет ортогонален к и . В самом деле, используя (9), (11), (12), (13), имеем:

Рассмотрим гиперплоскость (n-2) – х измерений
, (14)
проходящую через точку . Эта гиперплоскость содержит и , так как мы ранее видели, что , а
.
Вектор при любом параллелен гиперплоскости (7), так как
.
Подберем так, чтобы он был параллелен и гиперплоскости (14), т.е. потребуем ортогональности к вектору . Будем иметь:
,

или
(15)
Вектор
(16)
будет иметь направление нормали к сечению поверхности гиперплоскостью (14) в точке . Из точки сместимся в направлении этого вектора так, чтобы функция достигла минимального значения. Это будет при
, (17)
(18)
примем за новое приближение к . Новый вектор невязок будет:
. (19)
Продолжая процесс, получим последовательности векторов , , , определяемые рекуррентными соотношениями:

(20)
Для этих векторов имеют место следующие соотношения:
(21)
(22)
В самом деле, в силу самого построения при i¹j

Далее, при i>j

Если i=j+1, то правая часть равна нулю, в силу определения , если же i>j+1, то , по доказанному, и
.
Продолжая понижение индекса у вектора , через несколько шагов придем к скалярному произведению (по определению ). Таким образом, соотношения (21) доказаны. Для доказательства (22), в силу равноправия индексов i и j, предположим, что i>j. Тогда
.
Так как в n-мерном векторном пространства не может быть более n взаимно ортогональных векторов, то на некотором шаге получим , т.е. будет решением системы (1).
На рис. 1 показана геометрическая картина нашего построения при n=3.

Рис. 1
2.2 Второй алгоритм метода
Приведем другой алгоритм метода. Будем обозначать последовательные приближения к решению через и введем обозначения:
. (23)
Первые два приближения и возьмем так, чтобы

. (24)
Предположим, что уже известно приближение (i³1), вычислены и справедливо равенство
. (25)
Будем искать минимум функционала (2) на множестве векторов
. (26)
Приравнивая к нулю частные производные от по и для определения и , получим систему:
(27)
или, учитывая (25),
(28)
Обозначим через решение этой системы:

(29)
и за (i+1) – е приближение к решению примем:
(30)
Из системы (27) следует, что
, (31)
а так как

то из (31) следует:
(32)
Докажем, что если
(33)
то при всех i
(34)

что будет доказывать и сходимость, и конечность второго алгоритма.
В самом деле, при условиях (33)

и

т.е. условие (24) выполнено. Предположим, что уже доказаны равенства
(35)
и докажем равенство

При предположении (35) и, следовательно,

Но из соотношений (20) имеем:

т.е.

Докажем коллинеарность векторов
и (36)
Из (20) и (29) имеем:

а это и доказывает коллинеарность векторов (36).
Вектор дает минимум функционала в плоскости, проходящей через и натянутой на векторы и , а мы показали, что этот минимум лежит на прямой, проходящей через в направлении вектора . Но на этой прямой минимум функционала достигается на векторе . Это и означает, что
Это и доказывает справедливость (34) при всех i.
На первый взгляд кажется, что первый алгоритм лучше, так как на каждом шаге он требует лишь одного умножения матрицы А на вектор , а во втором алгоритме требуется два умножения матрицы А на вектор и , но опыт показал, что применение первого алгоритма приводит к быстрому накоплению ошибок округления, так что для матриц большого порядка возможно существенное отклонение от точного решения. Второй алгоритм менее чувствителен к ошибкам округления и поэтому требует меньшего количество шагов для получения хорошего приближенного решения.
Метод сопряженных градиентов целесообразно использовать для решения систем уравнений, в которых матрица А имеет много нулевых элементов. При решении системы по этому методу элементы матрицы участвуют в арифметических операциях лишь при умножении матрицы на вектор, а умножение матрицы на вектор можно организовать так, чтобы в арифметических операциях участвовали только ненулевые элементы.

Заключение
В данной работе были рассмотрены метод ортогонализации и метод сопряженных градиентов, а также представлена программа на языке программирования С++, реализующая метод ортогонализации на ЭВМ, и ее результаты работы.

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

Примечание от автора

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

Постановка задачи

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

Немного математики

Еще в 17 веке Пьером Ферма был придуман критерий, который позволял решать простые задачи оптимизации, а именно, еcли — точка минимума , то

где — производная . Этот критерий основан на линейном приближении

Чем ближе к , чем точнее это приближение. В правой части — выражение, которое при может быть как больше так и меньше — это основная суть критерия. В многомерном случае аналогично из линейного приближения (здесь и далее — стандартное скалярное произведение, форма записи обусловлена тем, что скалярное произведение — это то же самое, что матричное произведение вектор-строки на вектор-столбец) получается критерий

Величина — градиент функции в точке . Также равенство градиента нулю означает равенство всех частных производных нулю, поэтому в многомерном случае можно получить этот критерий просто последовательно применив одномерный критерий по каждой переменной в отдельности.

Стоит отметить, что указанные условия являются необходимыми, но не достаточными, самый простой пример — 0 для и

Этот критерий является достаточным в случае выпуклой функции, во многом из-за этого для выпуклых функций удалось получить так много результатов.

Квадратичные функции

Для экономии места (да и чтобы меньше возиться с индексами) такую функцию обычно записывают в матричной форме:

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

Зачем я об этом рассказываю? Дело в том, что квадратичные функции важны в оптимизации по двум причинам:

Они тоже встречаются на практике, например при построении линейной регрессии методом наименьших квадратов
Градиент квадратичной функции — линейная функция, в частности для функции выше

Или в матричной форме

Полезные свойства градиента

Хорошо, мы вроде бы выяснили, что если функция дифференцируема (у нее существуют производные по всем переменным), то в точке минимума градиент должен быть равен нулю. А вот несет ли градиент какую-нибудь полезную информацию в случае, когда он отличен от нуля?

Попробуем пока решить более простую задачу: дана точка , найти точку такую, что . Давайте возьмем точку рядом с , опять же используя линейное приближение . Если взять , то мы получим

Аналогично, если , то будет больше (здесь и далее ). Опять же, так как мы использовали приближение, то эти соображения будут верны только для малых . Подытоживая вышесказанное, если , то градиент указывает направление наибольшего локального увеличения функции.

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

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

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

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

Величина называется размером шага (в машинном обучении — скорость обучения). Пару слов по поводу выбора : если — очень маленькие, то последовательность медленно меняется, что делает алгоритм не очень эффективным; если же очень большие, то линейное приближение становится плохим, а может даже и неверным. На практике размер шага часта подбирают эмпирически, в теории обычно предполагается липшицевость градиента, а именно, если

для всех , то гарантирует убывание .

Анализ для квадратичных функций

Если — симметричная обратимая матрица, , то для квадратичной функции точка является точкой минимума (UPD. при условии, что этот минимум вообще существует — не принимает сколько угодно близкие к значения только если положительно определена), а для метода градиентного спуска можно получить следующее

где — единичная матрица, т.е. для всех . Если же , то получится

Выражение слева — расстояние от приближения, полученного на шаге градиентного спуска до точки минимума, справа — выражение вида , которое сходится к нулю, если (условие, которое я писал на в предыдущем пункте как раз это гарантирует). Эта базовая оценка гарантирует, что градиентный спуск сходится.

Модификации градиентного спуска

Теперь хотелось бы рассказать немного про часто используемые модификации градиентного спуска, в первую очередь так называемые

Инерционные или ускоренные градиентные методы

Они практически не усложняют обычный градиентный спуск в вычислительном плане.
При аккуратном подборе такие методы на порядок быстрее, чем обычный градиентный спуск даже с оптимально подобранным шагом.

Метод тяжелого шарика — самый простой инерционный метод, но не самый первый. При этом, на мой взгляд, самый первый метод довольно важен для понимания сути этих методов.

Метод Чебышева

Да да, первый метод такого типа был придуман еще Чебышевым для решения систем линейных уравнений. В какой-то момент при анализе градиентного спуска было получено следующее равенство

где — некоторый многочлен степени . Почему бы не попробовать подобрать таким образом, чтобы было поменьше? Один уз универсальных многочленов, которые меньше всего отклоняются от нуля — многочлен Чебышева. Метод Чебышева по сути заключается в том, чтобы подобрать параметры спуска так, чтобы был многочленом Чебышева. Есть правда одна небольшая проблема: для обычного градиентного спуска это просто невозможно. Однако для инерционных методов это оказывается возможным. В основном это происходит из-за того, что многочлены Чебышева удовлетворяют рекуррентному соотношению второго порядка

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

Метод сопряженных градиентов

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

Если бы мы могли подбирать размер шага в градиентном спуске так, чтобы получать именно этот обнуляющий многочлен, то градиентный спуск сходился бы за фиксированное число итерации не большее размерности . Как уже выяснили — для градиентного спуска мы так делать не можем. К счастью, для инерционных методов — можем. Описание и обоснование метода довольно техническое, я ограничусь сутью:на каждой итерации выбираются параметры, дающие наилучший многочлен, который можно построить учитывая все сделанные до текущего шага измерения градиента. При этом

Одна итерация градиентного спуска (без учета вычислений параметров) содежит одно умножение матрицы на вектор и 2-3 сложения векторов
Вычисление параметров также требует 1-2 умножение матрицы на вектор, 2-3 скалярных умножения вектор на вектор и несколько сложений векторов.

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

Метод Нестерова

при этом не предполагается какого-то сложного подсчета как в методе сопряженных градиентов, в целом поведение метода похоже на метод тяжелого шарика, но при этом его сходимость обычно гораздо надежнее как в теории, так и на практике.

Стохастический градиентный спуск

Единственное формальное отличие от обычного градиентного спуска — использование вместо градиента функции такой, что ( — математическое ожидание по случайной величине ), таким образом стохастический градиентный спуск имеет вид

— это некоторый случайный параметр, на который мы не влияем, но при этом в среднем мы идем против градиента. В качестве примера рассмотрим функции

Если принимает значения равновероятно, то как раз в среднем — это градиент . Этот пример показателен еще и следующим: сложность вычисления градиента в раз больше, чем сложность вычисления . Это позволяет стохастическому градиентному спуску делать за одно и то же время в раз больше итераций. Несмотря на то, что стохастический градиентный спуск обычно сходится медленней обычного, за счет такого большого увеличения числа итераций получается улучшить скорость сходимости на единицу времени. Насколько мне известно — на данный момент стохастический градиентный спуск является базовым методом обучения большинства нейронных сетей, реализован во всех основных библиотеках по ML: tensorflow, torch, caffe, CNTK, и т.д.

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

Субградиентный спуск

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

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

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

Допустим мы начали из точки .
Шаг субградиентного спуска:

Где обычно или . На практике я часто видел успешное применение шагов , хоть и для таких шагов вообще говоря не будет сходимости.

Proximal методы

Заключение

На этом заканчиваются основные известные мне вариации градиентного метода. Пожалуй под конец я бы отметил, что все указанные модификации (кроме разве что метода сопряженных градиентов) могут легко взаимодействовать друг с другом. Я специально не стал включать в эту перечень метод Ньютона и квазиньютоновские методы (BFGS и прочие): они хоть и используют градиент, но при этом являются более сложными методами, требуют специфических дополнительных вычислений, которые обычно более вычислительно затратны, нежели вычисление градиента. Тем не менее, если этот текст будет востребован, я с удовольствием сделаю подобный обзор и по ним.

Лекции

Лабораторные

Справочники

Эссе

Вопросы

Стандарты

Программы

Дипломные

Курсовые

Помогалки

Графические

Доступные файлы (2):

курсовик.doc

Введение в метод 7

Метод градиентного спуска 8

Критерий останова 9

Сходимость градиентного спуска с постоянным шагом 9

Выбор оптимального шага 10

Градиентный метод с дроблением шага 12

Метод наискорейшего спуска 13

Числовые примеры 14

Метод градиентного спуска с постоянным шагом 14

Градиентный метод с дроблением шага 14

Метод наискорейшего спуска 15

Рекомендации при программировании 16

Введение в метод 17

Постановка задачи оптимизации 17

Метод сопряжённых градиентов для квадратичного функционала 18

Изложение метода 18

Анализ метода 19

Численный пример 21

Метод сопряжённых градиентов в общем случае 21

Анализ метода 22

Числовой пример 24

Рекомендации при программировании 25

Используя градиентные методы, можно найти решение любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X(k) осуществляется последовательный переход к некоторым другим точкам, до тех пор, пока не выявляется приемлемое решение исходной задачи.
^

Введение в метод

В работе рассматривается задача поиска минимума функции , записываемая в виде:

Пусть функция такова, что можно вычислить ее градиент. Тогда можно применить метод градиентного спуска, описанный в данной статье.

Метод градиентного спуска с постоянным шагом
Метод градиентного спуска с дроблением шага
Метод наискорейшего спуска

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

Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в раз".
^

Идея метода

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

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

Алгоритм

Критерий останова

Сходимость градиентного спуска с постоянным шагом

Пусть , функция дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.

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

Определение. Дифференцируемая функция называется сильно выпуклой (с константой ), если для любых и из справедливо

Теорема 2 о сходимости метода градиентного спуска с постоянным шагом.

Пусть функция дифференцируема, сильно выпукла с константой . Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.
^

Выбор оптимального шага

Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.

Константа , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага . Нетрудно видеть, что величина минимальна, если шаг выбирается из условия , т. е. если .

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

В качестве и могут выступать равномерные по x оценки сверху и снизу собственных значений оператора . Если , то и метод сходится очень медленно. Геометрически случай соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на , задаваемая формулой:

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

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

Градиентный метод с дроблением шага

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

где - некоторая заранее выбранная константа.

Процедуру нахождения такого обычно оформляют так. Выбирается число и некоторый начальный шаг . Теперь для каждого k полагают и делают шаг градиентного метода. Если с таким условие (2) выполняется, то переходят к следующему k. Если же (2) не выполняется, то умножают на ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (2) не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному .

Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора на каждом шаге, заменяя ее на проблему выбора параметров и , к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
^

Метод наискорейшего спуска

Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L.

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче :

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

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

В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
^

Числовые примеры

Метод градиентного спуска с постоянным шагом

Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:

Начальное приближение - точка (10,10). Использован критерий останова:

Результаты эксперимента отражены в таблице:

Значение шага	Достигнутая точность	Количество итераций
0.1	метод расходится
0.01	2e-4	320
0.001	2e-3	2648
0.0001	1e-2	20734

Из полученных результатов можно сделать вывод, что при слишком большом чаге метод расходится, при слишком малом сходится медленно и точчность хуже. Надо выбирать шаг наибольшим из тех, при которых метод сходится.
^

Градиентный метод с дроблением шага

Для исследования сходимости метода градиентного спуска с дроблением шага (2) была выбрана функция:

Начальное приближение - точка (10,10). Использован критерий останова:

Метод наискорейшего спуска

Для исследования сходимости метода наискорейшего спуска была выбрана функция:

Начальное приближение - точка (10,10). Использован критерий останова:

Для решения одномерных задач оптимизации использован метод золотого сечения .

Метод получил точность 6e-8 за 9 итераций.

Отсюда можно сделать вывод, что метод наискорейшего спуска сходится быстрее, чем градиентный метод с дроблением шага и метод градиентного спуска с постоянным шагом.

Недостатком методом наискорейшего спуска явлляется необходимость решать одномерную задачу оптимизации.
^