Метод сопряженных градиентов пример решения. Умножение разреженных матриц

21.09.2019

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

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 и 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. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.

Метод предназначен для решения задачи (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

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

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

Алгоритм получается таким (модификация I):

А. Начальный шаг.

1) Находится градиент функции в произвольной точке ;

2) полагается ;

3) находится точка , доставляющая максимум функции на прямой ( – параметр).

Б. Общий шаг. Пусть уже найдены точки .

1) находится градиент функции в точке .

2) полагается

В. Останов алгоритма. Процесс обрывается в тот момент, когда градиент обратится в нуль, т. е. достигается максимум на всем пространстве .

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

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

Чтобы придать алгоритму более «конструктивную» форму, найдем формулу, определяющую точку максимума квадратичной формы на прямой .

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

где – градиент в точке . Максимизируя по , получим

и соответственно

. (16.16)

Таким образом, вычисление в пункте 3) алгоритма может быть осуществлено по формуле

2. Более известна модификация метода, при которой для вычисления очередного направления используются векторы и вместо и .

Рассмотрим систему векторов , коллинеарных соответственно векторам (т. е. при некоторых действительных ). Для векторов и сохраняется условие -ортогональности

При . (16.17)

Кроме того, из (16.11) следует, что

При . (16.18)

Наконец, остается в силе соотношение типа (16.9)

. (16.19)

Умножая правую и левую части (16.19) на и учитывая (16.17) и (16.18), получим при

откуда при . При получим

. (16.20)

Соотношение (16.20) определяет с точностью до произвольного множителя через и ц. При выводе (16.20) использовались лишь соотношения (16.17), (16.18), (16.19). Поэтому процесс построения векторов может рассматриваться как процесс -ортогонализации векторов .

Полагая в (16.20) и , получим конкретную систему векторов , коллинеарных . Каждый вектор задает направление прямой, исходящей из , на которой лежит . Алгоритм, таким образом, примет следующий вид (модификация II).

А. Начальный шаг, такой же как и в модификации I.

Б. Пусть уже найдены точка и направление .

1) Находится градиент функции в точке ;

2) полагается

; (16.21)

3) находится точка , доставляющая условный максимум на прямой

по формуле

. (16.22)

Формулы (16.21) и (16.22) могут быть преобразованы. Так, полагая

имеем из (16.22)

откуда получаем, применяя (16.12),

. (16.23)

С другой стороны, поскольку

из (16.21) имеем

и, таким образом,

Наконец, из (16.21), (16.23) и (16.24) получаем

Таким образом, формулы (16.21) и (16.22) могут быть записаны в виде

. (16.26)

Совпадение результатов действия по формулам (16.21) и (16.22), с одной стороны, и (16.25), (16.26), с другой, может служить критерием правильности вычислений.

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

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

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

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

где все и некоторые из . При этом функция имеет максимум, если выполнено условие: когда , то и . Легко видеть, что максимум в этом случае достигается на целом гиперпространстве. А именно, пусть, например, при , меняющемся от 1 до , , а при , меняющемся от до , и . Тогда максимум достигается в точках с координатами при и с произвольными значениями при . Они образуют гиперпространство размерности .

Если же при некоторых , a , то функция не имеет максимума и возрастает неограниченно. В самом деле, пусть, например, и ; тогда, если положить при и устремить к , то, очевидно, и будет возрастать до бесконечности.

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

В исходной системе координат функция имеет вид

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

Рассмотрим применение метода сопряженных градиентов в форме II в этом случае. Здесь приходится изменить условие остановки, т. е. теперь возможно, что при вычислении длины шага

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

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

Следовательно, останов обязательно произойдет при .

Метод сопряженных градиентов (в англ. литературе «conjugate gradient method») - это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:

- это значения аргумента функции (управляемые параметры) на вещественной области.

В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:

где i, j,…, n - единичные векторы, параллельные координатным осям.

Градиент в базовой точке строго ортогонален к поверхности, а его направление показывает направление наискорейшего возрастания функции, а противоположное направление (антиградиент), соответственно, показывает направление наискорейшего убывания функции.

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

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции.

Единичный вектор сопряженных направлений, который определяется по формуле:

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

В качестве первого способа рассматривают определение весового коэффициента по формуле Флетчера-Ривса (Fletcher–Reeves):

- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента соответственно.

В качестве второго способа рассматривают определение весового коэффициента по формуле Полака–Райбера (Polak-Ribiere):

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

Траектория спуска в методе сопряженных градиентов (поиск минимума)

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

Траектория движения к точке экстремума при использовании метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная).

Следует отметить, что через каждые n + 1 шагов необходимо выполнять рестарт алгоритмической процедуры (n – размерность пространства поиска). Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.

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

Другими словами, величину шага определяют при решении данного уравнения:

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

Траектория поиска остается в малой окрестности текущей точки поиска:

Приращение целевой функции не меняется:

Градиент целевой функции в точке локального минимума обращается в нуль:

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

Методика расчета

1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции

2 шаг : Задаем начальное приближение

3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.

4 шаг : Вычисление координат единичного вектора по формуле, полученной на шаге 1, и определение координат новой точки при движении по направлению единичного вектора как функция от шага расчета.

Вычисление весового коэффициента и единичного вектора сопряженных направлений на текущем шаге расчета (формула Флетчера-Ривса):