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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р, р, ..., р. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f’(x[k])+k-1p, k >= 1; p = -f’(x).

Величины k-1 выбираются так, чтобы направления p[k], р были H-сопряженными:

(p[k], Hp)= 0.

В результате для квадратичной функции

итерационный процесс минимизации имеет вид

x =x[k] +akp[k],

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

f(х[k] + аkр[k]) = f(x[k] + ар [k]).

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f’(x).

2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х.

3. Вычисляются величины f(x) и f’(x).

4. Если f’(x) = 0, то точка х является точкой минимума функции f(х). В противном случае определяется новое направление p из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x = x[k] +akp[k],

p[k] = -f’(x[k])+k-1p, k >= 1;

f(х[k] + akp[k]) = f(x[k] + ap[k];

Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 1.19). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р, то f’(х) ортогонален вектору р. Затем отыскивается вектор р , H-сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

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

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

Численные методы безусловной оптимизации второго порядка, варианты алгоритмов метода Ньютона

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

Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:

Разложение f’(х) в окрестности точки х[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде

f"(x) f’(x[k]) + f"(x[k]) (х - х[k]) 0.

Здесь f"(x[k]) Н(х[k]) - матрица вторых производных (матрица Гессе) минимизируемой функции. Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции f(x) описывается выражением

x x[k] - H-1(x[k]) f’(x[k]) ,

где H-1(x[k]) - обратная матрица для матрицы Гессе, а H-1(x[k])f’(x[k]) р[k] - направление спуска.

Полученный метод минимизации называют методом Ньютона. Очевидно, что в данном методе величина шага вдоль направления р[k] полагается равной единице. Последовательность точек {х[k]}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции f(x). Если матрица Гессе Н(х*) положительно определена, точка х* будет точкой строгого локального минимума функции f(x). Последовательность x[k] сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.

Если функция f(x) является квадратичной, то, независимо от начального приближения х и степени овражности, с помощью метода Ньютона ее минимум находится за один шаг. Это объясняется тем, что направление спуска р[k] H-1(x[k])f’(x[k]) в любых точках х всегда совпадает с направлением в точку минимума х*. Если же функция f(x) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации. При минимизации овражных функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами. В таком случае вектор р[k] не указывает направление в точку минимума функции f(x), однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент.

Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения х. Если х находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска р[k] H-1(x[k])f’(x[k]), но и величины шага а вдоль этого направления. Соответствующий алгоритм называют методом Ньютона с регулировкой шага. Итерационный процесс в таком случае определяется выражением

x x[k] - akH-1(x[k])f’(x[k]).

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

f(x[k] – ak H-1(x[k])f’(x[k]) (f(x[k] - aH-1(x[k])f’(x[k])).

Такой вариант алгоритма называют также методом Ньютона-Рафсона. Графическая интерпретация этого варианта метода Ньютона представлена на рис. 1.20. На выносных элементах рисунка приведены графики одномерных функций, подлежащих оптимизации с целью определения шага.

Рис. 1.20. Геометрическая интерпретация метода Ньютона-Рафсона

Алгоритм метода Ньютона-Рафсона состоит в следующем. Часть действий выполняется до начала итерационного процесса. А именно необходимо получить вектор формул, составляющих градиент f’([x]) (т.е. вектор первых частных производных) и матрицу формул, составляющих матрицу Гессе H(x) (т.е. матрицу вторых частных производных). Далее в итерационном цикле в эти формулы подставляются значения компонент вектора х и эти массивы становятся массивами чисел.

1. В начальной точке х вычисляется вектор, определяющий направление спуска p - H-1(x)f’(). Тем самым задача многомерная сводится к задаче одномерной оптимизации.

2. На k-й итерации определяется шаг аk (по схеме, изображенной на рис. 1.20, для этого решается задача одномерной оптимизации) и точка х.

3. Вычисляется величина f(х).

4. Проверяются условия выхода из подпрограммы, реализующей данный алгоритм. Эти условия аналогичны условиям выхода из подпрограммы при методе наискорейшего спуска. Если эти условия выполняются, осуществляется прекращение вычислений. В противном случае вычисляется новое направление

р –H-1(x[k])f’([k])

и осуществляется переход к следующей итерации, т. е. на шаг 2.

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

В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ньютона. В начале процесса минимизации, когда точка х находится далеко от точки экстремума х*, можно применять какой-либо вариант градиентных методов. Далее, при уменьшении скорости сходимости градиентного метода можно перейти к методу Ньютона. Или вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается H-1(x[k]) Е, где Е - единичная матрица. Итерация при этом осуществляется по методу наискорейшего спуска.

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

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

При использовании метода наискорейшего спуска на каждой итерации величина шага а 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.2

Правила ввода функций :

Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение . Два n -мерных вектора х и у называют сопряженными по отношению к матрице A (или A-сопряженными), если скалярное произведение (x, Aу) = 0 . Здесь A - симметрическая положительно определенная матрица размером n х n .

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

Метод Флетчера-Ривса

Алгоритм метода Флетчера-Ривса

Сходимость метода

Пример . Найти минимум функции методом сопряженных градиентов: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
Решение. В качестве направления поиска выберем вектор градиент в текущей точке:

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

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

Два вектора 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 и т.д.

Это и есть окончательный вид алгоритма Флетчера-Ривса.

Как было замечено ранее, он найдет минимум квадратичной функции не более чем за n шагов.

Минимизация неквадратичной целевой функции.

Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x 0 на x n +1 , а счет заканчивается при ||f "(x k+1)|| £ ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.

Схема алгоритма для неквадратичных целевых функций.

Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых β k = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.

Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

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

1. 26. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.