Метод предназначен для решения задачи (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 и y называют Н - сопряженными (или сопряженными по отношению к матрице Н) или Н - ортогональными, если
(x, H·y) = 0. (9)
f (x) = a + (x,b) + ½ (x, H·x). (10)
с положительно определенной n·n матрицей. Оказывается, что квадратичная функция (10) может быть минимизирована методом сопряженных направлений не более чем за n шагов.
Чтобы воспользоваться этим методом минимизации квадратичной функции (10) нужно знать n - взаимно сопряженных направлений S 0 , S 1 ,…,S n-1 . Эффективность таких направлений – самостоятельная проблема. Существует много взаимно сопряженных направлений S 0 , S 1 ,…,S n-1 и способов их построения. Ниже излагается метод сопряженных градиентов Флетчера - Ривса, в котором выбор Н - сопряженных направлений осуществляется совместно с одномерной минимизацией f (х) по α..
Метод Флетчера – Ривса.
Этот метод использует последовательность направлений поиска, каждая из которых является линейной комбинацией антиградиента в текущей точке и предыдущего направления спуска. Метод изменяется к квадратичной целевой функции f (x) = a + (x,b) + ½ (x, H·x).
При минимизации ее методом Флетчера - Ривса векторы S k вычисляются по формулам
S 0 = – f " (x 0), S k = – f "(x k) + β k-1 ·S k-1 , при k ≥ 1.
Величины β k-1 выбираются так, чтобы направления S k , S k-1 были Н – сопряженными.
Точка х k-1 ,определяется в результате минимизации функции f (х) в направлении S k , исходящем из точки x k , т.е.
х k+1 = x k + α k ·S k , где α k доставляет минимум по α k функции f (x k , α ·S k).
Итак, предлагаемая процедура минимизации функции f (x) выглядит следующим образом. В заданной точке x 0 вычисляется антиградиент
S 0 = – f " (x 0). Осуществляется одномерная минимизация в этом направлении и определяется точка x 1 . В точке x 1 сново вычисляется антиградиент – f " (x 1). Так как эта точка доставляет минимум функции f (x) вдоль направления S 0 = – f " (x 0), вектор f " (x 1) ортогонален f " (x 0). Затем по известному значению f " (x 1) по формуле (11) вычисляется вектор S 1 , который за счет выбора β 0 будет Н – сопряженным к S 0 . Далее отыскивается минимум функции f (х) вдоль направления S 1 и т.д.
шаг 4:Это и есть окончательный вид алгоритма Флетчера-Ривса.
Как было замечено ранее, он найдет минимум квадратичной функции не более чем за n шагов.
Минимизация неквадратичной целевой функции.
Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x 0 на x n +1 , а счет заканчивается при ||f "(x k+1)|| £ ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.
Схема алгоритма для неквадратичных целевых функций.
Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых β k = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:
Еще по теме Метод сопряженных градиентов:
- 26. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.
Метод Ньютона и квазиньютоновские методы, обсуждавшиеся в предыдущем параграфе, весьма эффективны как средство решения задач безусловной минимизации. Однако они предъявляют довольно высокие требования к объему используемой памяти ЭВМ. Это связано с тем, что выбор направления поиска требует решения систем линейных уравнений, а также с возникающей необходимостью хранения матриц типа Поэтому при больших использование этих методов может оказаться невозможным. В существенной степени от этого недостатка избавлены методы сопряженных направлений.
1. Понятие о методах сопряженных направлений.
Рассмотрим задачу минимизации квадратичной функции
с симметричной положительно определенной матрицей А Напомним, что для ее решения требуется один шаг метода Ньютона и не более чем шагов квазиньютоновского метода Методы сопряженных направлений также позволяют найти точку минимума функции (10.33) не более чем за шагов. Добиться этого удается благодаря специальному выбору направлений поиска.
Будем говорить, что ненулевые векторы являются взаимно сопряженными (относительно матрицы А), если для всех
Под методом сопряженных направлений для минимизации квадратичной функции (10.33) будем понимать метод
в котором направления взаимно сопряжены, а шаги
получаются как решение задач одномерной минимизации:
Теорема 10.4. Метод сопряженных направлений позволяет найти точку минимума квадратичной функции (10 33) не более чем за шагов.
Методы сопряженных направлений отличаются один от другого способом построения сопряженных направлений. Наиболее известным среди них является метод сопряженных градиентов
2. Метод сопряженных градиентов.
В этом методе направления строят правилу
Так как то первый шаг этого метода совпадает с шагом метода наискорейшего спуска. Можно показать (мы этого делать не будем), что направления (10.34) действительно являются
сопряженными относительно матрицы А. Более того, градиенты оказываются взаимно ортогональными.
Пример 10.5. Применим метод сопряженных градиентов для минимизации квадратичной функции - из примера 10.1. Запишем виде где
Возьмем начальное приближение
1-й шаг метода совпадает с первым шагом метода наискорейшего спуска. Поэтому (см. пример 10.1)
2-й шаг. Вычислим
Так как то и решение оказалось найденным за два шага.
3. Метод сопряженных градиентов для минимизации неквадратичных функций.
Для того чтобы указанный метод можно было применить для минимизации произвольной гладкой функции формулу (10.35) для вычисления коэффициента преобразуют к виду
или к виду
Преимущество формул (10 36), (10.37) в том, что они не содержат явным образом матрицу А.
Минимизацию функции методом сопряженных градиентов производят в соответствии с формулами
Коэффициенты вычисляют по одной из формул (10.36), (10.37).
Итерационный процесс здесь уже не оканчивается после конечного числа шагов, а направления не являются, вообще говоря, сопряженными относительно некоторой матрицы.
Решение задач одномерной минимизации (10.40) приходится осуществлять численно. Отметим также то, что часто в методе сопряженных градиентов при коэффициент не вычисляют по формулам (10.36), (10.37), а полагают равным нулю. При этом очередной шаг производят фактически методом наискорейшего спуска. Такое "обновление" метода позволяет уменьшить влияние вычислительной погрешности.
Для сильно выпуклой гладкой функции при некоторых дополнительных условиях метод сопряженных градиентов обладает высокой сверхлинейной скоростью сходимости. В то же время его трудоемкость невысока и сравнима с трудоемкостью метода наискорейшего спуска. Как показывает вычислительная практика, он незначительно уступает по эффективности квазиньютоновским методам, но предъявляет значительно меньшие требования к используемой памяти ЭВМ. В случае, когда решается задача минимизации функции с очень большим числом переменных, метод сопряженных градиентов, по-видимому, является единственным подходящим универсальным методом.
Термин "метод сопряженных градиентов" – один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.
Несколько слов об обозначениях, используемых далее.
Скалярное произведение двух векторов записывается $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
f (x )
f (xk ) = f(x0 ) + ∑ α i Api . | |||||
i= 1 | |||||
обе части | этого равенства скалярно на p k | учитывая | |||
исчерпывающего спуска по направлению p k :(f (x k ), p k ) = 0 | и A −ортогональность |
||||
векторов, получаем | |||||
(f (x 0 ),p k )+ α k (Ap k ,p k )= 0. | |||||
A положительно определена, | квадратичная | ||||
(Ap k , p k ) > 0 и для величины шагаα k получаем выражение (5.17). | |||||
Последовательный исчерпывающий спуск | A –ортогональным |
||||
направлениям (5.16) приводит к точке минимума квадратичной формы не более чем за n шагов.
□ Доказать самостоятельно. Предположить, что существуют u k ≠ α k , и
получить, что они совпадают. ■
Вопрос о нахождении базиса из A –ортогональных векторов в пространствеE n
решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A . Однако их поиск приn > 2 представляет собой самостоятельную и довольно сложную задачу.
и без предварительного построения векторов p 1 , ..., p n , последовательно находя их в процессе минимизации, как это было сделано выше в примере с минимизацией функции двух переменных. И в этом случае для квадратичной функции с положительно определенной матрицейA для нахождения минимума достаточно конечное число шагов. Если не является квадратичной функцией или
вспомогательные задачи одномерной минимизации решаются приближенно, потребуются дополнительные вычисления.
Метод сопряженных направлений, рассмотренный выше, относится к числу наиболее эффективных методов минимизации выпуклых квадратичных функций. Его недостатком является необходимость решать довольно большое количество задач одномерной минимизации.
5.6. Метод сопряженных градиентов
При использовании методов градиентного и наискорейшего спуска в итерационной процедуре
антиградиента: p k = − f (x k ). Однако такой выбор направления убывания не всегда бывает удачным. В частности, для плохо обусловленных задач минимизации направление антиградиента в точкеx k может значительно отличаться от направления к точке минимумаx . В результате траектория приближения к точке минимума имеет зигзагообразный характер. Воспользуемся другим подходом, идея которого была изложена при построении метода сопряженных направлений. Будем определять направления спускаp k не только через вектор антиградиента− f (x k ) ,
в котором величина шага α k находится из условия исчерпывающего спуска по
направлению p k . Далее, | после вычисления очередной точки x k + 1 , | k = 0, 1, ..., новое |
|||||
направление поиска p k + 1 | находится по формуле, отличной от антиградиента: |
||||||
pk + 1 = − f(xk + 1 ) + β k pk , | k = 0, 1, ..., | ||||||
где коэффициенты | выбираются так, чтобы при минимизации квадратичной |
||||||
функции f (x ) с | положительно определенной | матрицей | A получалась |
||||
последовательность | A −ортогональных | векторов | p 0 ,p 1 , .... | Из условия |
|||
(Ap k + 1 ,p k )= 0имеем: | |||||||
β k= | (A f (x k + 1 ),p k ) | ||||||
(Ap k ,p k ) | |||||||
Ранее, при обсуждении метода сопряженных направлений было показано, что
для квадратичной функции шаг исчерпывающего спуска по направлению p k равен
α k = − | (f (x k ),p k ) | ||
(Ap k ,p k ) |
|||
Утверждение . Итерационный процесс | (5.19)−(5.22) минимизации |
||
квадратичной функции с положительно определенной симметрической матрицей
f (x )
A дает точки | x 0 , ...,x k | и векторы p 0 , ..., p k такие, что если | f (x i )≠ 0при |
||||
0
≤i
| то векторы | p 0 , ..., | A −ортогональны, | градиенты |
|||
f (x 0 ), ...,f (x i ) | взаимно ортогональны. | ||||||
Так как направления | являются A −ортогональными, | ||||||
гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за n шагов.
С учетом взаимной ортогональности градиентов f (x i ) и условий
исчерпывающего спуска по направлениям p k можно упростить выражения (5.21) и
(5.22) для α k | и β k . В результате получим, | что итерационный процесс метода |
||||||||||||||
сопряженных градиентов описывается соотношениями | ||||||||||||||||
x k+ 1 | X k +α k | p k ,k = 0, 1, ...; | x0 En , | p0 = − f(x0 ) , | ||||||||||||
f (x k + α k p k )= minf (x k | + αp k ), | k = 0, 1, ..., | ||||||||||||||
α> 0 | ||||||||||||||||
p k+ 1 | = − f (x k + 1 ) +β k | p k ,k = 0, 1, ..., | ||||||||||||||
β k= | f (xk + 1 ) | k = 1, 2, ... | ||||||||||||||
f (xk ) | ||||||||||||||||
Следует отметить, что выражение для коэффициента β k не содержит в явном виде матрицуA квадратичной формы. Поэтому метод сопряженных градиентов может применяться для минимизации неквадратичных функций.
Итерационный процесс (5.23)−(5.26) может не приводить к точке минимума неквадратичной функции за конечное число итераций. Более того, точное
определение α k из условия (5.22) возможно лишь в редких случаях, а вектораp k
на образуют, вообще говоря, A −ортогональную систему относительно какой-либо матрицыA . Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к
тому, что векторы p k перестанут указывать направление убывания функции и
сходимость метода может нарушаться. Поэтому в методе сопряженных градиентов применяется практический прием − через каждые N шагов производят обновление метода, полагаяβ m N = 0, m = 1, 2, ... . Номераm N называют моментами
обновления метода, или рестарта . Часто полагаютN = n − размерности пространстваE n . ЕслиN = 1 , то получается частный случай метода сопряженных градиентов − метод наискорейшего спуска.
Вблизи точки минимума дважды дифференцируемая функция с положительно определенной матрицей Гессе H (x ) , как правило, достаточно хорошо
аппроксимируется квадратичной функцией. Поэтому можно надеяться на хороший результат применения метода сопряженных градиентов для функций такого вида.
Пример 5.7. Методом сопряженных градиентов найти точку минимума
функции f (x ) = 4 x 2 + 3 x 2 − 4 x x | из начальной точки x 0 = (0, 0) T . |
|||||||||||
□ Итерация 1. | ||||||||||||
Шаг 1. Положим ε = 0,01, | = (0, 0)T , | и найдем f (x 0 ) = (1, 0) T . Перейдем к |
||||||||||
Шаг 2. Положим k = 0, | = − f (x 0 ) = (− 1, 0) T . Перейдем к шагу 3. |
|||||||||||
f (x0 | + α p 0 )→ min.Получим |
|||||||||||
α 0 = 1/ 8 . – Здесь применили формулуα 0 = − | (f (x 0 ),p 0 ) | (Ax 0 + b ,p 0 ) | Перейдем |
|||||||||
(Ap 0 ,p 0 ) | (Ap 0 ,p 0 ) |
|||||||||||
Шаг 4. Найдем | x 1= x 0 | + α 0 p 0 = (− 1/ 8, | и f (x 1 ) = (0, 1/ 2) T . Точность не |
|||||||||
достигнута, прейдем к шагу 5. | ||||||||||||
Шаг 5. Условие k + 1 = n не выполняется (нет рестарта), перейдем к шагу 6. |
||||||||||||
Шаг 6. Найдем коэффициент β 0 = 1/ 4 и новое направление спуска |
||||||||||||
p 1 = − f (x 1 ) + β 0 p 0 = (− 1/ 4, − 1/ 2) T . Перейдем к следующей итерации. |
||||||||||||
Поскольку x 1 , f (x 1 ) иp 1 | = − f (x 1 ) +β 0 | уже вычислены на итерации 1, то |
||||||||||
итерацию 2 начинаем с шага 3. | ||||||||||||
Итерация 2. | ||||||||||||
Шаг 3. Решим задачу одномерной минимизации | f (x 1 + α p 1 ) → min . Получим |
|||||||||||
α = 1/ 4 . Перейдем к шагу 4. | ||||||||||||
Шаг 4. Найдем x 2 | X 1 +α 1 | p 1 = (− 3 /16,− 1/ 8)T и f (x 2 )= (0, 0)T − задача решена |
||||||||||