Метод наискорейшего спуска
При использовании метода наискорейшего спуска на каждой итерации величина шага а
k
выбирается из условия минимума функции f(x)
в направлении спуска, т. е.
f(x
[k
] -a
k
f"(x
[k
]))
= f(x
[k] - af"(x
[k
]))
.
Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x)
убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а
функции
j(a)
= f(x
[k
] - af"(x
[k
])) .
Алгоритм метода наискорейшего спуска состоит в следующем.
1. Задаются координаты начальной точки х .
2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f"(x [k ]) .
3. Определяется величина шага a k , путем одномерной минимизации по а функции j(a) = f(x [k ] - af"(x [k ])).
4. Определяются координаты точки х [k+ 1]:
х i [k+ 1] = x i [k ] - а k f" i (х [k ]), i = 1 ,..., п.
5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.
В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции ц(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:
d j(a)/da = -f"(x [k+ 1]f"(x [k ]) = 0.
Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)
мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения
Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются, а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.
Метод сопряженных градиентов
Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию
f(x) = (х, Нх) + (b, х) + а
с симметрической положительно определенной матрицей Н за конечное число шагов п, равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.
По определению, два n -мерных вектора х и у называют сопряженными по отношению к матрице H (или H -сопряженными), если скалярное произведение (x , Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером п хп.
Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x [k ]) в направление p [k ], H -сопряженное с ранее найденными направлениями р , р , ..., р [k -1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.
Направления р [k ] вычисляют по формулам:
p [k ] = -f"(x [k ]) +b k-1 p [k -l], k >= 1;
p = -f "(x ) .
Величины b k -1 выбираются так, чтобы направления p [k ], р [k -1] были H -сопряженными:
(p [k ], Hp [k- 1])= 0.
В результате для квадратичной функции
итерационный процесс минимизации имеет вид
x [k +l] =x [k ] +a k p [k ],
где р [k ] - направление спуска на k- м шаге; а k - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(х [k ] + а k р [k ]) = f(x [k ] + ар [k ]) .
Для квадратичной функции
Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.
1. В точке х вычисляется p = -f"(x ) .
2. На k- м шаге по приведенным выше формулам определяются шаг а k . и точка х [k+ 1].
3. Вычисляются величины f(x [k +1]) и f"(x [k +1]) .
4. Если f"(x ) = 0, то точка х [k +1] является точкой минимума функции f(х). В противном случае определяется новое направление p [k +l] из соотношения
и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+ 1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х [п +1] , а вычисления заканчиваются при, где - заданное число. При этом применяют следующую модификацию метода:
x [k +l] = x [k ] +a k p [k ],
p [k ] = -f"(x [k ])+ b k- 1 p [k -l], k >= 1;
p = -f"(x );
f(х [k ] + a k p [k ]) = f(x [k ] + ap [k ];
Здесь I - множество индексов: I = {0, n, 2п, Зп, ...} , т. е. обновление метода происходит через каждые п шагов.
Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x ). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р , то f"(х ) ортогонален вектору р . Затем отыскивается вектор р , H -сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.
Рис. 2.11.
Методы сопряженных направлений являются одними из наиболее эффективных для решения задач минимизации. Однако следует отметить, что они чувствительны к ошибкам, возникающим в процессе счета. При большом числе переменных погрешность может настолько возрасти, что процесс придется повторять даже для квадратичной функции, т. е. процесс для нее не всегда укладывается в п шагов.
Метод предназначен для решения задачи (5.1) и принадлежит классу методов первого порядка. Метод представляет собой модификацию метода наискорейшего спуска (подъема) и автоматически учитывает особенности целевой функции, ускоряя сходимость.
Описание алгоритма
Шаг 0 . Выбирается точка начального приближения , параметр длины шага , точность решения и вычисляется начальное направление поиска .
Шаг k . На k -м шаге находится минимум (максимум) целевой функции на прямой, проведенной из точки по направлению . Найденная точка минимума (максимума) определяет очередное k -е приближение , после чего определяется направление поиска
Формула (5.4) может быть переписана в эквивалентном виде
.
Алгоритм завершает свою работу, как только выполнится условие ; в качестве решения принимается значение последнего полученного приближения .
Метод Ньютона
Метод предназначен для решения задачи (5.1) и принадлежит классу методов второго порядка. В основе метода лежит разложение Тейлора целевой функции и то, что в точке экстремума градиент функции равен нулю, то есть .
Действительно, пусть некоторая точка лежит достаточно близко к точке искомого экстремума . Рассмотрим i -ю компоненту градиента целевой функции и разложим ее в точке по формуле Тейлора с точностью до производных первого порядка:
. (5.5)
Формулу (5.5) перепишем в матричной форме, учитывая при этом, что :
где матрица Гессе целевой функции в точке .
Предположим, что матрица Гессе невырождена. Тогда она имеет обратную матрицу . Умножая обе части уравнения (5.6) на слева, получим , откуда
. (5.7)
Формула (5.7) определяет алгоритм метода Ньютона: пересчет приближений на k
Алгоритм заканчивает свою работу, как только выполнится условие
,
где заданная точность решения; в качестве решения принимается значение последнего полученного приближения .
Метод Ньютона-Рафсона
Метод является методом первого порядка и предназначен для решения систем n нелинейных уравнений c n неизвестными:
В частности, этот метод может быть применен при поиске стационарных точек целевой функции задачи (5.1), когда необходимо решить систему уравнений из условия .
Пусть точка есть решение системы (5.9), а точка расположена вблизи . Разлагая функцию в точке по формуле Тейлора, имеем
откуда (по условию ) вытекает
, (5.11)
где матрица Якоби вектор-функции . Предположим, что матрица Якоби невырождена. Тогда она имеет обратную матрицу . Умножая обе части уравнения (5.11) на слева, получим , откуда
. (5.12)
Формула (5.12) определяет алгоритм метода Ньютона-Рафсона: пересчет приближений на k -й итерации выполняется в соответствии с формулой
В случае одной переменной, когда система (5.9) вырождается в единственное уравнение , формула (5.13) принимает вид
, (5.14)
где значение производной функции в точке .
На рис. 5.2 показана схема реализации метода Ньютона-Рафсона при поиске решения уравнения .
Замечание 5.1. Сходимость численных методов, как правило, сильно зависит от начального приближения.
Замечание 5.2. Методы Ньютона и Ньютона-Рафсона требуют большого объема вычислений (надо на каждом шаге вычислять и обращать матрицы Гессе и Якоби).
Замечание 5.3. При использовании методов обязательно следует учитывать возможность наличия многих экстремумов у целевой функции (свойство мультимодальности ).
ЛИТЕРАТУРА
1. Афанасьев М.Ю. , Суворов Б.П. Исследование операций в экономике: Учебное пособие. – М.: Экономический факультет МГУ, ТЕИС, 2003 – 312 с.
2. Базара М, Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. – М.: Мир, 1982 – 583 с.
3. Берман Г .Н . Сборник задач по курсу математического анализа: Учебное пособие для вузов. – СПб: «Специальная Литература», 1998. – 446 с.
4. Вагнер Г. Основы исследования операций: В 3-х томах. Пер. с англ. – М.: Мир, 1972. – 336 с.
5. Вентцель Е. С. Исследование операций. Задачи, принципы, методология – М.: Наука, 1988. – 208 с.
6. Демидович Б.П. Сборник задач и упражнений по математическому анализу. – М.: Наука, 1977. – 528 с.
7. Дегтярев Ю.И. Исследование операций. – М.: Высш. шк., 1986. – 320 с.
8. Нуреев Р.М. Сборник задач по микроэкономике. – М.: НОРМА, 2006. – 432 с.
9. Солодовников А. С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. – М.:Финансы и статистика, 1999. – 224 с.
10. Таха Х. Введение в исследование операций, 6-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912 с.
11. Химмельблау Д. Прикладное нелинейное программирование: Пер. с англ. – М.: Мир, 1975 – 534 с.
12. Шикин Е. В., Шикина Г.Е. Исследование операций: Учебник – М.: ТК Велби, Изд-во Проспект, 2006. – 280 с.
13. Исследование операций в экономике : Учебн. пособие для вузов/ Н.Ш.Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; Под ред. проф. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с.
14. Матрицы и векторы : Учебн. пособие/ Рюмкин В.И. – Томск: ТГУ, 1999. – 40 с.
15. Системы линейных уравнений : Учебн. пособие / Рюмкин В.И. – Томск: ТГУ, 2000. – 45 с.
ВВЕДЕНИЕ……………………………………................................... | |
1. ОСНОВЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ………………... | |
1.1. Постановка задачи математического программирования............................... | |
1.2. Разновидности ЗМП…………….………….......................................... | |
1.3. Базовые понятия математического программирования................................ | |
1.4. Производная по направлению. Градиент…………......................................... | |
1.5. Касательные гиперплоскости и нормали………….......................................... | |
1.6. Разложение Тейлора……………………………............................................... | |
1.7. ЗНЛП и условия существования ее решения................................................... | |
1.8. Задачи ……………..……................................................................................... | |
2. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БЕЗ ОГРАНИЧЕНИЙ................................................................................................................ | |
2.1. Необходимые условия решения ЗНЛП без ограничений............................... | |
2.2. Достаточные условия решения ЗНЛП без ограничений................................. | |
2.3. Классический метод решения ЗНЛП без ограничений................................... | |
2.4. Задачи…………….............................................................................................. | |
3. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ОГРАНИЧЕНИЯХ-РАВЕНСТВАХ................................................................................. | |
3.1. Метод множителей Лагранжа…………………………................................... | |
3.1.1. Назначение и обоснование метода множителей Лагранжа…………… | |
3.1.2. Схема реализации метода множителей Лагранжа……………………... | |
3.1.3. Интерпретация множителей Лагранжа………………………………… | |
3.2. Метод подстановки……………………………................................................. | |
3.3. Задачи………………………….......................................................................... | |
4. РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ОГРАНИЧЕНИЯХ-НЕРАВЕНСТВАХ……………………………………………….. | |
4.1. Обобщенный метод множителей Лагранжа………………………………… | |
4.2. Условия Куна-Таккера………………………….............................................. | |
4.2.1. Необходимость условий Куна-Таккера………………………………… | |
4.2.2. Достаточность условий Куна-Таккера………………………………….. | |
4.2.3. Метод Куна-Таккера………………………............................................... | |
4.3. Задачи………………………….......................................................................... | |
5. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …………………………...…………………………………… | |
5.1. Понятие алгоритма………………………….................................................... | |
5.2. Классификация численных методов………………………………………… | |
5.3. Алгоритмы численных методов……………………………………………... | |
5.3.1. Метод наискорейшего спуска (подъема)………………………………… | |
5.3.2. Метод сопряженных градиентов…………………………......................... | |
5.3.3. Метод Ньютона…………………………..................................................... | |
5.3.4. Метод Ньютона-Рафсона………………………………………………... | |
ЛИТЕРАТУРА……………………………….............................................................. |
Определения линейной и нелинейной функций см. в разделе 1.2
Термин "метод сопряженных градиентов" – один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.
Несколько слов об обозначениях, используемых далее.
Скалярное произведение двух векторов записывается x T y и представляет сумму скаляров: . Заметим, что x T y = y T x. Если x и y ортогональны, то x T y = 0. В общем, выражения, которые преобразуются к матрице 1х1, такие как x T y и x T Ax, рассматриваются как скалярные величины.
Первоначально метод сопряженных градиентов был разработан для решения систем линейных алгебраических уравнений вида:
Ax = b (1)
где x – неизвестный вектор, b – известный вектор, а A – известная, квадратная, симметричная, положительно–определенная матрица. Решение этой системы эквивалентно нахождению минимума соответствующей квадратичной формы.
Квадратичная форма – это просто скаляр, квадратичная функция некого вектора x следующего вида:
f(x) = (1/2)x T Ax-b T x+c (2)
Наличие такой связи между матрицей линейного преобразования A и скалярной функцией f(x) дает возможность проиллюстрировать некоторые формулы линейной алгебры интуитивно понятными рисунками. Например, матрица А называется положительно-определенной, если для любого ненулевого вектора x справедливо следующее:
x T Ax > 0 (3)
На рисунке 1 изображено как выглядят квадратичные формы соответственно для положительно-определенной матрицы (а), отрицательно-определенной матрицы (b), положительно-неопределенной матрицы (с), неопределенной матрицы (d).
Рис. 1. Квадратичные формы для положительно-определенной матрицы, отрицательно-определенной матрицы, положительно-неопределенной матрицы, неопределенной матрицы.
То есть, если матрица А – положительно-определенная, то вместо того, чтобы решать систему уравнений 1, можно найти минимум ее квадратичной функции. Причем, метод сопряженных градиентов сделает это за n или менее шагов, где n – размерность неизвестного вектора x. Так как любая гладкая функция в окрестностях точки своего минимума хорошо аппроксимируется квадратичной, этот же метод можно применить для минимизации и неквадратичных функций. При этом метод перестает быть конечным, а становится итеративным.
Рассмотрение метода сопряженных градиентов целесообразно начать с рассмотрения более простого метода поиска экстремума функции – метода наискорейшего спуска. На рисунке 2 изображена траектория движения в точку минимума методом наискорейшего спуска. Суть этого метода:
- в начальной точке x(0) вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция;
- в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении;
- процесс повторяется до достижения точки минимума.
Рис. 2. Траектория движения в точку минимума методом наискорейшего спуска.
В данном случае каждое новое направление движения ортогонально предыдущему. Не существует ли более разумного способа выбора нового направления движения? Существует, и он называется метод сопряженных направлений. А метод сопряженных градиентов как раз относится к группе методов сопряженных направлений. На рисунке 3 изображена траектория движения в точку минимума при использовании метода сопряженных градиентов.
Рис. 3. Траектория движения в точку минимума при использовании метода сопряженных градиентов
Определение сопряженности формулируется следующим образом: два вектора x и y называют А-сопряженными (или сопряженными по отношению к матрице А) или А–ортогональными, если скалярное произведение x и Ay равно нулю, то есть:
x T Ay = 0 (4)
Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А – единичная матрица, в соответствии с равенством 4, векторы x и y – ортогональны. Можно и иначе продемонстрировать взаимосвязь понятий ортогональности и сопряженности: мысленно растяните рисунок 3 таким образом, чтобы линии равного уровня из эллипсов превратились в окружности, при этом сопряженные направления станут просто ортогональными.
Остается выяснить, каким образом вычислять сопряженные направления. Один из возможных способов – использовать методы линейной алгебры, в частности, процесс ортогонализации Грамма–Шмидта. Но для этого необходимо знать матрицу А, поэтому для большинства задач (например, обучение многослойных нейросетей) этот метод не годится. К счастью, существуют другие, итеративные способы вычисления сопряженного направления, самый известный – формула Флетчера-Ривса:
(6)
Формула 5 означает, что новое сопряженное направление получается сложением антиградиента в точке поворота и предыдущего направления движения, умноженного на коэффициент, вычисленный по формуле 6. Направления, вычисленные по формуле 5, оказываются сопряженными, если минимизируемая функция задана в форме 2. То есть для квадратичных функций метод сопряженных градиентов находит минимум за n шагов (n – размерность пространства поиска). Для функций общего вида алгоритм перестает быть конечным и становится итеративным. При этом, Флетчер и Ривс предлагают возобновлять алгоритмическую процедуру через каждые n + 1 шагов.
Можно привести еще одну формулу для определения сопряженного направления, формула Полака–Райбера (Polak-Ribiere):
(7)
Метод Флетчера-Ривса сходится, если начальная точка достаточно близка к требуемому минимуму, тогда как метод Полака-Райбера может в редких случаях бесконечно циклиться. Однако последний часто сходится быстрее первого метода. К счастью, сходимость метода Полака-Райбера может быть гарантирована выбором . Это эквивалентно рестарту алгорима по условию . Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.
Из приведенного алгоритма следует, что на шаге 2 осуществляется одномерная минимизация функции. Для этого, в частности, можно воспользоваться методом Фибоначчи, методом золотого сечения или методом бисекций. Более быструю сходимость обеспечивает метод Ньютона–Рафсона, но для этого необходимо иметь возможность вычисления матрицы Гессе. В последнем случае, переменная, по которой осуществляется оптимизация, вычисляется на каждом шаге итерации по формуле:
Несколько слов об использовании метода сопряженных направлений при обучении нейронных сетей. В этом случае используется обучение по эпохам, то есть при вычислении целевой функции предъявляются все шаблоны обучающего множества и вычисляется средний квадрат функции ошибки (или некая ее модификация). То же самое – при вычислении градиента, то есть используется суммарный градиент по всему обучающему набору. Градиент для каждого примера вычисляется с использованием алгоритма обратного распространения.
В заключение приведем один из возможных алгоритмов программной реализации метода сопряженных градиентов. Сопряженность в данном случае вычисляется по формуле Флетчера–Ривса, а для одномерной оптимизации используется один из вышеперечисленных методов. По мнению некоторых авторитетных специалистов скорость сходимости алгоритма мало зависит от оптимизационной формулы, применяемой на шаге 2 приведенного выше алгоритма, поэтому можно рекомендовать, например, метод золотого сечения, который не требует вычисления производных.
Вариант метода сопряженных направлений, использующий формулу Флетчера-Ривса для расчета сопряженных направлений.
K:= 0
// Цикл поиска (выход по счетчику или ошибке)
// Цикл одномерной минимизации (спуск по направлению d) R: = -f"(x) // антиградиент целевой функции в новой точке If (k = n) or (r T * d <= 0) then // Рестарт алгоритма I: = i + 1 |
Метод сопряженных градиентов является методом первого порядка, в то же время скорость его сходимости квадратична. Этим он выгодно отличается от обычных градиентных методов. Например, метод наискорейшего спуска и метод координатного спуска для квадратичной функции сходятся лишь в пределе, в то время как метод сопряженных градиентов оптимизирует квадратичную функцию за конечное число итераций. При оптимизации функций общего вида, метод сопряженных направлений сходится в 4-5 раз быстрее метода наискорейшего спуска. При этом, в отличие от методов второго порядка, не требуется трудоемких вычислений вторых частных производных.
Литература
- Н.Н.Моисеев, Ю.П.Иванилов, Е.М.Столярова "Методы оптимизации", М. Наука, 1978
- А.Фиакко, Г.Мак-Кормик "Нелинейное программирование", М. Мир, 1972
- У.И.Зангвилл "Нелинейное программирование", М. Советское радио, 1973
- Jonathan Richard Shewchuk "Second order gradients methods", School of Computer Science Carnegie Mellon University Pittsburg, 1994
Правила ввода функций :
Например, x 1 2 +x 1 x 2 , записываем как x1^2+x1*x2Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение
. Два n -мерных вектора х и у называют сопряженными
по отношению к матрице A (или A-сопряженными), если скалярное произведение (x, Aу) = 0 . Здесь A - симметрическая положительно определенная матрица размером n х n .
Схема алгоритма метода сопряженных градиентов
Положить k=0.Ш. 1 Пусть x 0 - начальная точка; ,
d 0 =-g 0 ; k=0.
Ш. 2 Определить x k +1 =x k +λ k d k , где
.
Затем d k+1 =-g k+1 +β k d k ,
,
β k находится из условия d k +1 Ad k =0 (сопряжены относительно матрицы A).
Ш. 3 Положить k=k+1 → Ш. 2.
Критерий останова одномерного поиска вдоль каждого из направлений d k записывается в виде: .
Значения выбираются таким образом, чтобы направление d k было A-сопряжено со всеми построенными ранее направлениями.
Метод Флетчера-Ривса
Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {x k }, k=0, 1, 2, ... таких, что f(x k +1) < f(x k), k=0, 1, 2, ...Точки последовательности {x k } вычисляются по правилу:
x k +1 =x k -t k d k , k = 0, 1, 2,…
d k = ▽f(x k) + b k -1 ▽f(x k -1)
Величина шага выбирается из условия минимума функции f(х) по t в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(x k -t k d k) → min (t k >0)
В случае квадратичной функции f(x)= (х, Нх) + (b, х) + а направления d k , d k -1 будут H-сопряженными, т.е. (d k , Hd k -1)=0
При этом в точках последовательности {x k } градиенты функции f(x) взаимно перпендикулярны, т.е. (▽f(x k +1),▽f(x k))=0, k =0, 1, 2…
При минимизации неквадратичных функций метод Флетчера-Ривса не является конечным. Для неквадратичных функций используется следующая модификация метод Флетчера-Ривса (метод Полака-Рибьера), когда величина b k -1 вычисляется следующим образом:
Здесь I- множество индексов: I = {0, n, 2n, 3n, ...}, т. е. метод Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов с заменой x 0 на x n +1 .
Построение последовательности{x k } заканчивается в точке, для которой |▽f(x k)|<ε.
Геометрический смысл метода сопряженных градиентов состоит в следующем. Из заданной начальной точки x 0 осуществляется спуск в направлении d 0 = ▽f(x 0).В точке x 1 определяется вектор-градиент ▽f(x 1).Поскольку x 1 является точкой минимума функции в направлении d 0 , то▽f(x 1) ортогонален вектору d 0 . Затем отыскивается вектор d 1 , H-сопряженный к d 0 . Далее отыскивается минимум функции вдоль направления d 1 и т. д.
Алгоритм метода Флетчера-Ривса
Начальный этап.Задать x 0 , ε > 0.
Найти градиент функции в произвольной точке
k=0.
Основной этап
Шаг 1. Вычислить ▽f(x k)
Шаг 2. Проверить выполнение критерия останова |▽f(x k)|< ε
а) если критерий выполнен, расчет окончен,x * =x k
б) если критерий не выполнен, то перейти к шагу 3, если k=0, иначе к шагу 4.
Шаг 3. Определить d 0 = ▽f(x 0)
Шаг 4. Определить или в случае неквадратичной функции
Шаг 5. Определить d k = ▽f(x k) + b k -1 ▽f(x k -1)
Шаг 6. Вычислить величину шага t k из условия f(x k - t k d k) → min (t k >0)
Шаг 7. Вычислить x k+1 =x k -t k d k
Шаг 8. Положить k= k +1 и перейти к шагу 1.
Сходимость метода
Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на R n , то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов.Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на R m , а ее градиент удовлетворяет условию Липшица . Тогда при произвольной начальной точке для метода Полака-Рибьера имеем
Теорема 2 гарантирует сходимость последовательности {x k } к стационарной точке x * , где ▽f(x *)=0. Поэтому найденная точка x * нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {x k } к точке минимума только для сильно выпуклых функций.
Оценка скорости сходимости получена только для сильно выпуклых функций , в этом случае последовательность {x k } сходится к точке минимума функции f(x) со скоростью: |x k+n – x*| ≤ C|x k – x*|, k = {0, n, 2, …}
Пример
. Найти минимум функции методом сопряженных градиентов: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
Решение. В качестве направления поиска выберем вектор градиент в текущей точке:
|
Термин "метод сопряженных градиентов" – один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.
Несколько слов об обозначениях, используемых далее.
Скалярное произведение двух векторов записывается $x^Ty$ и представляет сумму скаляров: $\sum_{i=1}^n\, x_i\,y_i$. Заметим, что $x^Ty = y^Tx$. Если x и y ортогональны, то $x^Ty = 0$. В общем, выражения, которые преобразуются к матрице 1х1, такие как $x^Ty$ и $x^TA_x$, рассматриваются как скалярные величины.
Первоначально метод сопряженных градиентов был разработан для решения систем линейных алгебраических уравнений вида:
где x – неизвестный вектор, b – известный вектор, а A – известная, квадратная, симметричная, положительно–определенная матрица. Решение этой системы эквивалентно нахождению минимума соответствующей квадратичной формы.
Квадратичная форма – это просто скаляр, квадратичная функция некого вектора x следующего вида:
$f\,(x) = (\frac{1}{2})\,x^TA_x\,-\,b^Tx\,+\,c$, (2)
Наличие такой связи между матрицей линейного преобразования A и скалярной функцией f(x) дает возможность проиллюстрировать некоторые формулы линейной алгебры интуитивно понятными рисунками. Например, матрица А называется положительно-определенной, если для любого ненулевого вектора x справедливо следующее:
$x^TA_x\,>\,0$, (3)
На рисунке 1 изображено как выглядят квадратичные формы соответственно для положительно-определенной матрицы (а), отрицательно-определенной матрицы (b), положительно-неопределенной матрицы (с), неопределенной матрицы (d).
То есть, если матрица А – положительно-определенная, то вместо того, чтобы решать систему уравнений 1, можно найти минимум ее квадратичной функции. Причем, метод сопряженных градиентов сделает это за n или менее шагов, где n – размерность неизвестного вектора x. Так как любая гладкая функция в окрестностях точки своего минимума хорошо аппроксимируется квадратичной, этот же метод можно применить для минимизации и неквадратичных функций. При этом метод перестает быть конечным, а становится итеративным.
Рассмотрение метода сопряженных градиентов целесообразно начать с рассмотрения более простого метода поиска экстремума функции – метода наискорейшего спуска. На рисунке 2 изображена траектория движения в точку минимума методом наискорейшего спуска. Суть этого метода:
- в начальной точке x(0) вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция;
- в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении;
- процесс повторяется до достижения точки минимума.
В данном случае каждое новое направление движения ортогонально предыдущему. Не существует ли более разумного способа выбора нового направления движения? Существует, и он называется метод сопряженных направлений. А метод сопряженных градиентов как раз относится к группе методов сопряженных направлений. На рисунке 3 изображена траектория движения в точку минимума при использовании метода сопряженных градиентов.
Определение сопряженности формулируется следующим образом: два вектора x и y называют А-сопряженными (или сопряженными по отношению к матрице А) или А–ортогональными, если скалярное произведение x и Ay равно нулю, то есть:
$x^TA_y\,=\,0$, (4)
Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А – единичная матрица, в соответствии с равенством 4, векторы x и y – ортогональны. Можно и иначе продемонстрировать взаимосвязь понятий ортогональности и сопряженности: мысленно растяните рисунок 3 таким образом, чтобы линии равного уровня из эллипсов превратились в окружности, при этом сопряженные направления станут просто ортогональными.
Остается выяснить, каким образом вычислять сопряженные направления. Один из возможных способов – использовать методы линейной алгебры, в частности, процесс ортогонализации Грамма–Шмидта. Но для этого необходимо знать матрицу А, поэтому для большинства задач (например, обучение многослойных нейросетей) этот метод не годится. К счастью, существуют другие, итеративные способы вычисления сопряженного направления, самый известный – формула Флетчера-Ривса:
$d_{(i+1)} = d_{(i+1)}\,+\,\beta_{(i+1)}\,d_i$ , (5)
$\beta_{(i+1)} = \frac{r_{(i+1)}^T}{r_{i}^T}\,\frac{r_{(i+1)}}{r_{(i)}}$, (6)
Формула 5 означает, что новое сопряженное направление получается сложением антиградиента в точке поворота и предыдущего направления движения, умноженного на коэффициент, вычисленный по формуле 6. Направления, вычисленные по формуле 5, оказываются сопряженными, если минимизируемая функция задана в форме 2. То есть для квадратичных функций метод сопряженных градиентов находит минимум за n шагов (n – размерность пространства поиска). Для функций общего вида алгоритм перестает быть конечным и становится итеративным. При этом, Флетчер и Ривс предлагают возобновлять алгоритмическую процедуру через каждые n + 1 шагов.
Можно привести еще одну формулу для определения сопряженного направления, формула Полака–Райбера (Polak-Ribiere):
$\beta_{(i+1)} = \frac{r_{(i+1)}^T\,(r_{(i+1)}\,-\,r_{(i)})}{r_{i}^T\,r_{(i)}}$, (7)
Метод Флетчера-Ривса сходится, если начальная точка достаточно близка к требуемому минимуму, тогда как метод Полака-Райбера может в редких случаях бесконечно циклиться. Однако последний часто сходится быстрее первого метода. К счастью, сходимость метода Полака-Райбера может быть гарантирована выбором $\beta = \max \{\beta;\,0\}$. Это эквивалентно рестарту алгорима по условию $\beta \leq 0$. Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.
- Вычисляется антиградиент в произвольной точке x (0) .
$d_{(0)} = r_{(0)} = -\,f"(x_{(0)})$
- Осуществляется спуск в вычисленном направлении пока функция уменьшается, иными словами, поиск a (i) , который минимизирует
$f\,(x_{(i)}\,+\,a_{(i)}\,d_{(i)})$
- Переход в точку, найденную в предыдущем пункте
$x_{(i+1)} = x_{(i)}\,+\,a_{(i)}\,d_{(i)}$
- Вычисление антиградиента в этой точке
$r_{(i+1)} = -\,f"(x_{(i+1)})$
- Вычисления по формуле 6 или 7. Чтобы осуществить рестарт алгоритма, то есть забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска, для формулы Флетчера–Ривса присваивается 0 через каждые n + 1 шагов, для формулы Полака-Райбера – $\beta_{(i+1)} = \max \{\beta_{(i+1)},\,0\}$
- Вычисление нового сопряженного направления
$d_{(i+1)} = r_{(i+1)}\,+\,\beta_{(i+1)}\,d_{(i)}$
- Переход на пункт 2.
Из приведенного алгоритма следует, что на шаге 2 осуществляется одномерная минимизация функции. Для этого, в частности, можно воспользоваться методом Фибоначчи, методом золотого сечения или методом бисекций. Более быструю сходимость обеспечивает метод Ньютона–Рафсона, но для этого необходимо иметь возможность вычисления матрицы Гессе. В последнем случае, переменная, по которой осуществляется оптимизация, вычисляется на каждом шаге итерации по формуле:
$$a = -\,\frac{{f"}^T\,(x)\,d}{d^T\,f""(x)\,d}$$
$f""(x)\,= \begin{pmatrix} \frac{\partial^2\,f}{\partial x_1\,\partial x_1}&\frac{\partial^2\,f}{\partial x_1\,\partial x_2}&\cdots&\frac{\partial^2\,f}{\partial x_1\,\partial x_n}& \\ \frac{\partial^2\,f}{\partial x_2\,\partial x_1}&\frac{\partial^2\,f}{\partial x_2\,\partial x_2}& \cdots&\frac{\partial^2\,f}{\partial x_2\,\partial x_n}& \\ \vdots&\vdots&\ddots&\vdots &\\ \frac{\partial^2\,f}{\partial x_n\,\partial x_1}& \frac{\partial^2\,f}{\partial x_n\,\partial x_2}&\cdots&\frac{\partial^2\,f}{\partial x_n\,\partial x_n} \end{pmatrix}$
Матрица Гессе
Несколько слов об использовании метода сопряженных направлений при обучении нейронных сетей. В этом случае используется обучение по эпохам, то есть при вычислении целевой функции предъявляются все шаблоны обучающего множества и вычисляется средний квадрат функции ошибки (или некая ее модификация). То же самое – при вычислении градиента, то есть используется суммарный градиент по всему обучающему набору. Градиент для каждого примера вычисляется с использованием алгоритма обратного распространения (BackProp).
В заключение приведем один из возможных алгоритмов программной реализации метода сопряженных градиентов. Сопряженность в данном случае вычисляется по формуле Флетчера–Ривса, а для одномерной оптимизации используется один из вышеперечисленных методов. По мнению некоторых авторитетных специалистов скорость сходимости алгоритма мало зависит от оптимизационной формулы, применяемой на шаге 2 приведенного выше алгоритма, поэтому можно рекомендовать, например, метод золотого сечения, который не требует вычисления производных.
Вариант метода сопряженных направлений, использующий формулу Флетчера-Ривса для расчета сопряженных направлений.
r:= -f"(x) // антиградиент целевой функции
d:= r // начальное направление спуска совпадает с антиградиентом
Sigma new: = r T * r // квадрат модуля антиградиента
Sigma 0: = Sigma new
// Цикл поиска (выход по счетчику или ошибке)
while i < i max and Sigma new > Eps 2 * Sigma 0
begin
j: = 0
Sigma d: = d T * d
// Цикл одномерной минимизации (спуск по направлению d)
repeat
a: =
x: = x + a
j: = j + 1
until (j >= j max) or (a 2 * Sigma d <= Eps 2)
R: = -f"(x) // антиградиент целевой функции в новой точке
Sigma old: = Sigma new
Sigma new: = r T * r
beta: = Sigma new / Sigma old
d: = r + beta * d // Вычисление сопряженного направления
k: = k + 1
If (k = n) or (r T * d <= 0) then // Рестарт алгоритма
begin
d: = r
k: = 0
end
I: = i + 1
end
Метод сопряженных градиентов является методом первого порядка, в то же время скорость его сходимости квадратична. Этим он выгодно отличается от обычных градиентных методов. Например, метод наискорейшего спуска и метод координатного спуска для квадратичной функции сходятся лишь в пределе, в то время как метод сопряженных градиентов оптимизирует квадратичную функцию за конечное число итераций. При оптимизации функций общего вида, метод сопряженных направлений сходится в 4-5 раз быстрее метода наискорейшего спуска. При этом, в отличие от методов второго порядка, не требуется трудоемких вычислений вторых частных производных.
Литература
- Н.Н.Моисеев, Ю.П.Иванилов, Е.М.Столярова "Методы оптимизации", М. Наука, 1978
- А.Фиакко, Г.Мак-Кормик "Нелинейное программирование", М. Мир, 1972
- У.И.Зангвилл "Нелинейное программирование", М. Советское радио, 1973
- Jonathan Richard Shewchuk "Second order gradients methods", School of Computer Science Carnegie Mellon University Pittsburg, 1994