10

14. Таха X. Введение в исследование операций.- М.: Мир, 1985. Кн. 1 и 2.

15.Карпелевич Ф., Садовский Л. Элементы линейной алгебры и линейного программирования.- М.: Наука, 1967.- 312с.

16.Калихман И.Л. Сборник задач по математическому программированию.- M.: Высш.шк, 1975.

17.Банди Б. Основы линейного программирования.- М.: Радио и связь, 1989.-

176с.

2.Курсовая работа

2.1. Общие методические указания

По дисциплине "Методы оптимизации" студенты выполняют курсовую рабо-

ту.

Курсовая работа предусматривает отработку навыков решения задач безус-

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

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

Каждая задача в курсовой работе должна содержать формулировку задачи

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

да решения.

Целевая функция для всех задач имеет вид

f(x1, x2) = (x1 - a)2 + (x2 - b)2 + x1 x2 .

Параметры а и b определяются двумя последними цифрами шифра зачетной книжки: а - последняя цифра шифра, b - предпоследняя цифра.

В качестве начальной выбирается точка х(0) с координатами х(0)=[-10, -10]T.

2.2. Теоретические основы алгоритмов

Методы поиска экстремума функции f(х), x = (x1, x2, …, xn)T можно разбить на два класса.

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

ции. К ним относятся методы Хука-Дживса, метод поиска по симплексу(метод Нелдера-Мида) и метод сопряженных направлений Пауэлла.

11 2. Градиентные методы, использующие в процедурах поиска информацию о

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

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

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

К методам первого порядка относятся методы Коши, сопряженных градиен-

тов, квазиньютоновский. К методам второго порядка относятся методы Мар-

квардта, Ньютона.

Ниже дано описание теоретических основ и алгоритмов перечисленных ме-

тодов.

2.2.1. Методы прямого поиска

Многомерные методы оптимизации, основанные на вычислении целевой функции f(x), можно разделить на эвристические и теоретические. В первых реа-

лизуются процедуры поиска с помощью интуитивных геометрических представ-

лений. Данные методы обеспечивают получение частных эмпирических резуль-

татов. Теоретические методы основаны на фундаментальных математических теоремах и обладают такими операционными свойствами как сходимость. К ка-

тегории эвристических относятся методы поиска по симплексу(s2-метод) и Ху-

ка-Дживса. К теоретическим - метод сопряженных направлений Пауэлла.

Метод поиска по симплексу

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

менных. Вершина, давшая наилучший результат, становится новой базовой точ-

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

В рассматриваемом методе таким экспериментальным образцом, содержа-

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

ном пространстве - тетраэдр.

12

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

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

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

1)если вершина с максимальным значениемf(x) построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции;

2)если вокруг одной из вершин начнется циклическое движение, то необхо-

димо уменьшить размеры симплекса.

Поиск заканчивается, когда размеры симплекса или разность значений целе-

вой функции становятся достаточно малыми.

Из элементарной геометрии известно, что при заданной базовой точкех(0) и

масштабном множителе a координаты остальныхN вершин симплекса вN-

мерном пространстве вычисляются по формуле

ìx x(i) = ïí

ïx

î

(j	0)	+d1	, если i = j;
(j	0)	+d2	, если i ¹ j,

где i, j = 1, 2, …, N.

				13
	Приращения δ1 и δ2 определяются по формулам
		é			+ N -1ù
	d			N +1					×a ,
		1 = ê						ú
				N × 2
		ë					û

		é		N + 1 - 1 ù
	d	2 = ê					ú ×a .
				N × 2
		ë				û

Величина a выбирается исследователем, исходя из характеристики решае-

мой задачи. При a = 1 ребро симплекса имеет единичную длину.

Вычисление центра тяжести. Если х(i)- точка, подлежащая отражению, то координаты центра тяжести определяются по формуле

xc	=	1	×åx(i ) .
		N i¹ j

Координаты новой вершины удовлетворяют уравнению

xновj = x j + l ×(xc - x( j ) ).

Для того, чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, то есть λ=2:

xновj = 2 × xc - x( j ) .

Если некоторая вершина симплекса не исключается на протяжении несколь-

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

Поиск завершается, когда размеры симплекса или разности между значения-

ми целевых функций становятся незначительными.

ПРИМЕР 1 Минимизировать f(x) = (1 – х1 )2 + (2 – x2)2 методом поиска по симплексу.

РЕШЕНИЕ Для построения исходного симплекса требуется задать началь-

ную точку и масштабный множитель. Пусть х(0)=[0,0]T и a = 2.

14

Тогда

		æ						ö
				3 +1
d	1	= ç						÷	× 2	= 1.9318 ,
		ç	2 ×		2			÷
		è						ø
		æ			-1			ö
				3
d	2	= ç						÷	× 2	= 0.5176 .
		ç	2 ×		2			÷
		è						ø

Вычислим координаты двух других вершин симплекса

х(1) = [0 + 0.5176; 0 + 1.9318]T = [0.5176; 1.9318]T;

х(2) = [0 + 1.9318; 0 +0.5176]T = [1.9318; 0.5176]T.

Значения целевой функции в этих вершинах соответственно равныf(х(1)) = 0,2374 и f(х(2)) = 3,0658. Так как f(х(0))=5, необходимо отразить точку х(0) относи-

тельно центра тяжести остальных вершин симплекса

xc = ½ (x(1)+x(2)).

x(3) = x(1)+x(2)-x(0);

x(3) = [2.4494; 2.4494]T.

В полученной точке f(x(3)) = 2,3027 , то есть наблюдается уменьшение целе-

вой функции. Новый симплекс образован вершинами х(1), x(2) и x(3), причем точке x(2) соответствует максимальное значение целевой функции. Следует отразить точку x(2) относительно центра тяжести точек х(1) и х(3).

Если вершина, которой соответствует наибольшее значение целевой функ-

ции, построена на предыдущей итерации, то вместо нее отбрасывается вершина,

которой соответствует следующее по величине значение целевой функции.

Метод поиска Хука-Дживса

Процедура Хука-Дживса представляет собой комбинацию"исследующего"

поиска с циклическим изменением переменных и ускоряющего поиска по най-

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

15

рагов". Полученная в результате исследующего поиска информация использует-

ся затем в процессе поиска по образцу при движении по "оврагам".

Исследующий поиск. Для проведения исследующего поиска необходимо за-

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

правлений и изменяться в процессе поиска. Поиск начинается в некоторой ис-

ходной точке. Делается пробный шаг вдоль одногоиз координатных направле-

ний. Если значение целевой функции в пробной точке меньше, чем в исходной,

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

нат исследующий поиск завершается. Полученную в результате точку называют базовой точкой.

Поиск по образцу. Заключается в реализации единственного шага из полу-

ченной базовой точки вдоль прямой, соединяющей эту точку с предыдущей ба-

зовой точкой. Новая точка образца определяется по формуле

x(pk +1) = x( k ) + (x( k ) - x(k -1) ).

Как только движение по образцу не приводит к уменьшению целевой функ-

x( k +1)

ции, точка p фиксируется в качестве временной базовой точки и выполняет-

ся исследующий поиск. Если в результате появилась точка с меньшим значени-

ем целевой функции, чем в точке x( k ) , то она рассматривается как новая базовая точка x(k +1) .

Если исследующий поиск неудачен, следует вернуться в точку x(k ) и провес-

ти исследующий поиск с целью выявления нового направления минимизации. В

конечном счете возникает ситуация, когда такой поиск не приводит к успеху. В

этом случае следует уменьшить величину шага и возобновить исследующий по-

иск. Поиск завершается, когда величина шага становится достаточно малой.

Последовательность точек, получаемую в результате реализации метода,

можно записать в следующем виде:

	16
x( k ) - текущая базовая точка;
x( k -1)	- предыдущая базовая точка;
x(pk +1)	- точка, построенная при движении по образцу;
x( k +1)	- новая базовая точка.

Эта последовательность характеризует логическую структуру поиска по ме-

тоду Хука-Дживса.

Алгоритм метода

Шаг 1. Задать:

1)начальную точку x(0);

2)приращение ∆ i, i = 1, 2, ..., N;

3)коэффициент уменьшения шага α > 1;

4)параметр окончания поиска ε > 0.

Шаг 2. Произвести исследующий поиск.

Шаг 3. Был ли исследующий поиск удачным(найдена ли точка сменьшим значением целевой функции)?

Да: перейти к шагу 5.

Нет: продолжить.

Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство

D < e ?

Да: прекратить поиск.

Нет: уменьшить приращение по формуле

	Di	=	Di	, i =1, 2, ..., N .
			a

Перейти к шагу 2.

Шаг 5. Провести поиск по образцу

x(pk +1) = x( k ) + (x( k ) - x(k -1) ).

17

x( k +1)

Шаг 6. Провести исследующий поиск, используя p в качестве базовой

точки. Пусть x( k +1) - полученная в результате поиска точка.

Шаг 7. Выполняется ли f( x(k+1) ) < f( x(k) )?

Да: положить x ( k -1) = x (k ) ; x (k ) = x( k +1) ; перейти к шагу 5.

Нет: перейти к шагу 4.

ПРИМЕР 2 Найти точку минимума функции

f(x) = 8 x12 + 4x1 x2 + 5x22

методом Хука-Дживса, используя начальную точку x(0)=[-4; -4]T.

РЕШЕНИЕ Для того, чтобы применить данный метод необходимо задать следующие величины:

∆х = 1 - векторная величина приращения;

α = 2 - коэффициент уменьшения шага;

ε = 10 -2 - параметр окончания поиска.

Итерации начинаются с исследующего поиска вокруг точкиx{0), которой со-

ответствует значение функции f(x(0))=272.

Фиксируя x2, даем приращение переменной x1;

x2 = - 4;

x1 = - 4+1 → f(-3; -4) = 200 < f(x(0)) → успех.

Следовательно, необходимо зафиксировать х1 = - 3 и дать приращение пере-

менной x2:

x1 = - 3;

x2 = - 4+1 → f(-3; -3) = 153 < 200 → успех.

Таким образом, в результате исследующего поиска найдена точка

x(1) = [-3; -3]T; f(x(1))=153.

18

Поскольку исследующий поиск был удачным, переходим к поиску по образ-

цу:

x(p2) = x(1) + (x(1) - x(0) ) = [- 2; - 2]T ;

f (x(p2) ) = 68.

Далее проводился исследующий поиск вокруг точки x(p2) , который оказыва-

ется удачным при положительных приращениях x1 и x2..

В результате получаем точку

x(2) = [-1; -1]T; f(x(2))=17.

Поскольку f(x(2)) < f(x(1)), поиск по образцу следует считать успешным, и x(2)

становится новой базовой точкой при следующем проведении поиска по образ-

цу. Итерации продолжаются, пока уменьшение величины шага не укажет на окончание поиска в окрестности точки минимума х* = [0; 0]T.

Метод сопряженных направлений Пауэлла

Метод ориентирован на решение задач с квадратичными целевыми функция-

ми. Основная идея алгоритма заключается в том, что если квадратичная функция

N переменных приведена к виду суммы полных квадратов, то ее оптимум может быть найден в результате реализацииN одномерных поисков по преобразован-

ным координатным направлениям.

Процедура преобразования квадратичной функции

q(x) = а + bT x + ½ xT C x

к виду суммы полных квадратов эквивалентна нахождению такой матрицы, Т

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

Q(x) = xT C x

путем линейного преобразования

х = T . z

19

приводится к виду

Q(z) = zT TT C T z = zT D z ,

где D - диагональная матрица.

Пусть tj – j-й столбец матрицы Т. Тогда можно представить векторх в виде линейной комбинации вектор-столбцов tj:

x = T z = t1 z1 + t2 z2 + … + tn zn .

По сути дела векторы t задают новую координатную систему, совпадающую с главными осями исходной квадратичной формы, поскольку матрица вновь по-

лученной квадратичной формы приведена к диагональному виду (см. рис.2).

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

тельными поисками точек экстремумов вдоль координатных осей. Такая система векторов tj, j = 1, 2 , ..., N называется системой сопряженных направлений. Та-

ким образом, проблема нахождения оптимума целевой функции сводится к по-

строению системы сопряженных направленийtj. Если матрицаС известна, то матрицу преобразований Т можно найти с помощью метода Гаусса-Жордана.

Этот метод позволяет представить матрицу С в виде произведения

C = PTDP ,

откуда

(p-1)TC(p-1) = D и T = (p-1).

20

Однако систему сопряженных направлений можно построить другим спосо-

бом. Если С- симметричная матрица порядка N . N, то направления s(1), s(2), …, s(r), r ≤ N называются С- сопряженными при линейной независимости этих на-

правлений и выполнения условия

s(i) T C s(j) = 0, для всех i ≠ j.

Можно показать, что этими свойствами обладают направленияd и (y(2)-y(1))

(см. рис.3):

(y(2) - y(1)) T C d = 0.

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

Шаг 1. Задать исходные точки x(1), x(2) и направление d. В частности, направ-

ление d может совпадать с направлением координатной оси.

Шаг 2. Произвести одномерный поиск из точкиx(1) в направлении d и полу-

чить точку у(1), являющуюся точкой экстремума на заданном направлении.

Шаг 3. Произвести поиск из точки x(2) в направлении d и получить точку у(2). Шаг 4. Вычислить направление (y(2) - y(1)).

Шаг 5. Провести одномерный поиск из точкиу(1) (либо у(2)) в направлении (y(2) - y(1)) с выходом в точку х*.

В данном случае, в отличие от предыдущего, сопряженные направления оп-

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

Задание исходных точек и направления не слишком удобно. Поэтому пред-

почтительнее строить систему сопряженных направлений, исходя из одной на-

чальной точки, а в качестве направлений поиска использовать координатные на-

правления. Рассмотрим данную процедуру (см. рис.4).

21

Первоначально осуществляется одномерный поиск из точкиx(0) вдоль коор-

динатного направления х1, в результате чего находится точках(1). Из этой точки осуществляется поиск экстремума вдоль направленияx2 и находится точках(2).

После этого из x(2) осуществляется поиск вдоль первоначального направлениях1

и находится точка х(3). В данном алгоритме направлениех1 адекватно направле-

нию d предыдущего метода. Таким образом, направления (x(3) –х(1)) и x1 оказы-

ваются сопряженными, и поэтому, поиск вдоль (х(3) – х(1)) дает искомый экстре-

мум в точке х*.

Данное построение может быть обобщено на случай задач более высокой размерности. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N2 одномерных поисков.

ПРИМЕР 3 Найти минимум функции

f(x) = 2 x13 + 4x1x23 – 10x1x2 + x12

с помощью метода сопряжённых направлений Пауэлла, если задана начальная точка x(0) = [5; 2]T, в которой

f(5; 2) = f(x(0)) = = 314.

РЕШЕНИЕ
Шаг 1. s(1) = [1; 0]T,	s(2) = [0; 1]T.

22

Шаг 2: а) найдём значение λ, при котором f(x) минимизируется в направле-

нии s(2), т.е.

f(x(0) + λs(2)) → min.

Произвольная точка на луче из точки x(0) в направлении s(2) определится как

x = x(0) + λs(2) = [5; 2]T + λ[0; 1]T,

откуда x1 = 5, x2 = 2+ λ. Подставляя эти значения в выражение целевой функции,

получаем

f(λ) = 2 . 53 + 4 . 5(2 + λ)3 – 10 . 5(2 + λ) + (2 + λ)2.

Дифференцируя последнее выражение поλ и приравнивая его к нулю, нахо-

дим λ* = -0.81, откуда

x(1) = [5; 2]T -0.81 [0; 1]T = [5; 1.19]T и f(x(1)) = 250;

б) аналогично	находим значениеλ,	при котором минимизируется f(x(1) +
λs(1)):
λ* = -3.26;	x(2) = [1.74; 1.19]T;	f(x(2)) = 1.1;

в) найдем значение λ, минимизирующее f(x(2)		+ λs(2)), т.е. вновь по направле-
нию s(2):
λ* = -0.098;	x(3) = [1.74; 1.092]T;	f(x(3)) = 0.72.

Шаг 3. Положим

s(3) = x(3) - x(1) = [-3.26; -0.098]T.

Направление s(3) оказывается сопряженным с направлениемs(2). Поскольку

N=2, то оптимизация вдоль направления s(3) дает искомый экстремум.

Шаг 4. Найдем такое значение λ, при котором f(x(3) + λs(3)) → min:

λ* = -0.734; x(4) = [1.006; 1.07]T; f(x(4)) = -2.86.

Эта точка и будет приближением к экстремуму. Если бы f(x) была квадратич-

23

ной, то x(4) являлась бы решением задачи. Для получения более точного решения

итерации следует продолжить.

2.2.2.Градиентные методы поиска экстремума функции N-переменных

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

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

точно высокой точностью вычислены численными методами.

Все далее рассматриваемые методы могут быть представлены следующей итерационной процедурой:

x(k+1) = x(k) + α (k) s(x(k)),

где x(k)- текущее значение аргумента исследуемой функции;

α(k) - параметр, характеризующий длину шага;

s(x(k)) = s (k) - направление поиска в N- мерном пространстве управляемых переменных.

Способ определения s и α связан с особенностями применяемого метода по-

иска. Как правило, выбор α(k) осуществляется нахождением экстремума функции f(x) в направлении s(k) .

Метод Коши

Если в качестве направления поиска s(x) взять направление антиградиента функции

s(x) = - Ñ f(x), где

		æ	¶f		¶f		¶f	öT
	Ñ f	= ç		;		; ... ;		÷	- градиент функции f(x),
		ç	¶x1		¶x 2			÷
		è					¶x n ø

то получим алгоритм

x(k+1) = x(k) - α (k) Ñ f(x(k))

24

метода наискорейшего спуска или метода Коши. Значение α(k) на каждой итера-

ции вычисляется путем решения задачи поиска экстремумаf(x) вдоль направле-

ния Ñ f(x(k)).

Если в качестве α (k) взять некоторое положительное число, то мы получим алгоритм простейшего градиентного метода

x(k+1) = x(k) - α Ñ f(x(k)).

Одним из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие (например, для задачи минимизации)

f(x(k+1)) ≤ f(x(k)).

Однако вблизи экстремума скорость сходимости алгоритма становится недо-

пустимо низкой. Это объясняется тем, что вблизи экстремума значение градиен-

та стремится к нулю.

ПРИМЕР 4

Найти минимум функции

f(x) = 8x12 + 4x1x2 + 5x22

с использованием метода Коши.

РЕШЕНИЕ Вычислим компоненты градиента

¶f = 16 x1 + 4 x 2 ;

¶x1

¶f = 10 x 2 + 4 x1 .

¶x 2

Зададим начальное приближение x(0) = [10; 10]T.

Новое приближение определим по формуле

x(1) = x(0) - α(0) Ñ f(x(0)).

Выбираем α(0) таким образом, чтобы минимизировать f(x(1)). Параметр α(0)

25

находится так же, как λ* в предыдущем примере. В качестве направления поиска выступает Ñ f(x(0)). Получаем α(0) = 0.056. Следовательно,

x(1) = [10; 10]T - 0.056 [200; 140]T = [-1.2; 2.16]T.

Далее найдем точку

x(2) = x(1) - α(1) Ñ f(x(1)),

вычислив градиент в точке x(l) и проведя поиск вдоль прямой

x(2) = [-1.2; 2.16]T - α(1) [-10.56; 16.8] T .

Итерации продолжаются до получения требуемой точности.

Метод Ньютона

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

Метод Коши основывается на последовательной линейной аппроксимации целе-

вой функции и требует вычисления значения целевой функции и ее производных на каждом шаге. Для построения более общей стратегии необходимо привлечь информацию о вторых производныхf(x). Эта информация появляется при квад-

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

лора учитываются члены ряда до второго порядка включительно. Такая аппрок-

симация приводит к реализации метода Ньютона:

x(k+1) = x(k) - Ñ 2 f(x(k))-1 Ñ f(x(k)),

где

	é ¶ 2		f
	ê
		¶ x	2
	ê		1
	ê	¶	2		f
	ê
Ñ 2 f ( x ) =	ê	¶ x	2 ¶ x1
	ê
	ê	K
	ê
	ê	¶	2		f
	ê
	ê	¶ x	n	¶ x			1
	ë

		¶ 2 f			¶ 2				f
					K
¶ x1 ¶ x 2						¶ x1 ¶ x n
		¶ 2 f			¶ 2				f
					K
		¶ x 22					¶ x 2 ¶ x n
	K				K K
		¶ 2 f			¶ 2				f
					K
	¶ x n ¶ x 2							¶ x n2

ù

ú

ú

ú

úú - гессиан

ú

ú(матрица Гессе).

ú

ú

ú

ú

û

26

В случае, когда матрица Ñ 2 f(x) положительно определена, направле-

ние поиска по методу Ньютона оказывается направлением спуска.

ПРИМЕР 5 Рассмотрим функцию из предыдущего примера

f(x) = 8x12 + 4x1x2 + 5x22.

РЕШЕНИЕ

Ñ f(x) = [16x1 + 4x2; 10x2 + 4x1]T,

	é16	4ù
Ñ2	f (x) = ê	ú .
	ë4	10û

При x(0) = [10; 10]T из формулы

x(1) = x(0) - Ñ 2 f(x(0))-1 Ñ f(x(0))

получаем

x

( 2)

T

é16 4ù-1

T

T

1

é10 - 4ù

T

= [10; 10]

- ê

ú ×[200; 140]

= [10; 10]

-

× ê

ú ×[200; 140]

=

144

ê4

10ú

ê- 4 16ú

ë

û

ë

û

= [10; 10]T -

1

[1440; 1440]T

= [0; 0]T ,

144

что совпадает с точным решением.

Таким образом, задача минимизации квадратичной функции решается с по-

мощью одной итерации по методу Ньютона (при любой начальной точке).

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

Рассмотренный выше метод Коши эффективен при поиске на значительных расстояниях от точки минимумах* и плохо работает в окрестности этой точки.

Метод Ньютона не отличается высокой надежностью вдали от точки экстрему-

ма, однако весьма эффективен вблизи от х*. Далее рассматривается метод, обла-

дающий положительными свойствами методов Коши и Ньютона. Кроме того,

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

27

изводных исследуемой функции.

В случае использования при вычислениях недесятичных дробей метод обла-

дает квадратичной сходимостью, то есть

||e(k+1)|| ≤ C||e(k)||2,

ипозволяет для квадратичных целевых функций получить решение за N шагов.

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

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

f(x) = a + bTx + ½ xTCx.

Градиент квадратичной функции равен

Ñ f(x) = Ñ g(x) = Cx + b = g(x).

Изменение градиента при переходе от точки x(0) к точке x(1) обозначим как

∆g(x) = g(x(1)) – g(x(0)) = C (x(1) - x(0)),

∆g(x) = C ∆x.

В рассматриваемом методе операции аргумента проводятся по формуле

x(k+1) = x(k)

Направления формул:

s(k) = -g (k )

+ α (k) s(x(k)).

поиска на каждой итерации определяются с помощью следующих

+ åg (i) s(i ) ,	s(0) = -g (0) ,	g (i ) =			g (i +1)					2	.
					g (i )			2

Флетчер и Ривс предложили рекуррентную формулу для определенияна правления на k-м шаге

28

s(k) = -g ( k ) +			g (i+1)			2	s (k-1) .
			g (i)		2

В этом случае направлениеs(k) будет С - сопряжено со всеми построенными ранее направлениями поиска.

Если функция f(x1, x2, ..., хN) квадратичная, то для нахождения точки экстре-

мума требуется определить N-I таких направлений и провести поиска вдоль ка-

ждой прямой. Если f(x) не является квадратичной, количество поисков возраста-

ет.

ПРИМЕР 6 Найти точку минимума функции

f(x) =4x12 + 3x22 - 4x1x2 + x1 .

Поиск будем осуществлять из точки x(0) = [0; 0]T .

РЕШЕНИЕ

Шаг 1.

Ñ f(x) =[8x1 - 4x2 + 1; 6x2 - 4x1 ] T ,

s(0) = – g(0) = - Ñ f(x(0)) = -[1; 0] T .

Шаг 2. Поиск вдоль прямой:

x(1) = x(0) - α(0) Ñ f(x(0)) → α(0) = 1/8;

x(1) =[0; 0] T – 1/8 [1; 0] T = [-1/8; 0] T.

Шаг 3. k = 1:

æ 1

ö2

2

ç

g

(1)

é

1

ù

T

2

÷

é

1

1

ù

T

(1)

(1)

(0)

è

ø

T

s

= -g

+

s

= -

ê0;

ú

-

×[1;0 ] =

ê-

;-

ú .

g (0)

2

2

1

2

4

2

ë

û

ë

û

Шаг 4. Поиск вдоль прямой:

x(2) = x(1) - α(1) s(1)

→ α(1) = 1/4;

29

x(2) =[-1/8; 0] T – 1/4 [1/4; 1/2] T = [-3/16; -1/8] T,

Ñ f(x(2)) = [0; 0] T.

Таким образом, x(2) = x* . Решение получено в результате проведения двух одномерных поисков, поскольку целевая функция квадратичная, а ошибки ок-

ругления отсутствуют.

Метод оказывается весьма эффективным при решении задач большой размерности.

Квазиньютоновский метод

Рассматриваемый метод обладает положительными чертами метода Ньюто-

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

Приближение к очередной точке в пространстве оптимизируемых парамет-

ров задается также формулой(1), в которой направление поиска определяется выражением

s(x(k)) = -A(k) Ñ f(x(k)),

(1)

где A(k)- матрица порядка N*N, носящая название метрики. Методы поиска на-

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

тод переменной метрики представляет собой квазиньютоновский метод, если перемещение пробной точки удовлетворяет соотношению

∆x = С-1 ∆g .

(2)

Матрица А, обратная матрице Гессе, аппроксимируетcя следующим выраже-

нием:

A(k+1) = A(k) + AС(k) ,

(3)

где AС(k)- корректирующая матрица. Задача заключается в том, чтобы построить

A(k) таким образом, чтобы последовательность A(0) , A(1) , …, A(л+1) давала при-

ближение H-1 = Ñ 2 f(x*)-1.

30

Предположим, что между матрицей С квадратичной формы (1) и матрицей А существует связь вида

С-1 = β A(k) ,

где β – скалярная величина. Тогда в соответствии с выражением(2) можно по-

требовать, чтобы новое приближение удовлетворяло формуле

∆x(k) = β A(k+1) ∆g(k) ,

(4)

где ∆x(k) = x(k+1) - x(k) ,

∆g(k) = g(k+1) - g(k) .

Подставляя равенство (3) в выражение (4), получаем формулу вида

AС(k) ∆g(k) = 1/ β ∆x(k) - A(k) ∆g(k) .

(5)

Введем в рассмотрение произвольные векторы у и z. В этом случае матрица

1

ì

Dx

(k )

× y

T

ü

(k )

×Dg

( k )

× z

T

A(k ) =

í

ý -

A

b

zT ×Dg (k )

C

î yT ×Dg(k )

þ

будет являться решением выра-

жения (5).

Если положить

y = ∆x(k)

и z = A(k) ∆g(k)

,

то получим формулу, реализующую метод Девидона-Флетчера-Пауэлла (ДФП):

A	( k )	= A	( k -1 )		Dx ( k -1) × Dx ( k -1) T		A ( k -1) × Dg ( k -1) × Dg ( k -1)T × A	( k -1)
				+		-			.
					Dx ( k -1) T × Dg ( k -1)		Dg ( k -1) T × A ( k -1 ) × Dg ( k -1)

Эта рекуррентная формула сохраняет свойства симметрии и положительной определенности матриц. Очень удобно выбирать A(0) = I, где I- единичная матри-

ца размерности N*N .

Алгоритм обеспечивает убывание целевой функции от итерации к итерации,

то есть отличается устойчивостью.

31

ПРИМЕР 7 С помощью метода ДФП найти точку минимума функции

f(x) = 4x12 + 3x22 - 4x1x2 + х1, если х(0) = [0; 0]T.

РЕШЕНИЕ

Шаг 1. Положим s(0) = - Ñ f(x(0)) = -[1; 0]T.

Шаг 2. Поиск вдоль прямой приводит к результату, полученному в преды-

дущем примере x(1)= [-1/8; 0] T.

Шаг 3. k =1, A(1)= A(0) + AС(0),

é1	0ù
A(0) = I = ê	ú;
ê0	1ú
ë	û

∆x(0) =[-1/8; 0] T - [0:0]T =[-1/8; 0] T;

∆g(0)=[0; 1/2] T - [1; 0]T =[-1; 1/2] T;

( 0 )

Dx ( 0 )

× Dx ( 0 )T

A ( 0 ) × Dg

( 0 ) × Dg ( 0 )T × A ( 0 )

AС

=

-

=

Dx ( 0 )T × Dg ( 0 )

Dg ( 0 )T

× A ( 0 ) × Dg ( 0 )

é- 1 / 8 ù

[- 1 / 8 0

]

é1 0 ù é - 1 ù

é1 0 ù

ê

0

ú ×

ê

0 1

ú × ê

ú × [- 1 1 / 2 ]× ê

ú

=

ë

û

-

ë

û ë1 / 2

û

ë0 1 û

=

é - 1 ù

[- 1 / 8 0 ]×

é1 0 ù é - 1 ù

ê

ú

[- 1 1 / 2 ]× ê

ú × ê

ú

ë1 / 2 û

ë0 1 û ë1 / 2

û

é1 / 64 0ù é 1

-1 / 2ù

ê

0

ú

ê

1 / 2

1 / 4

ú

é1 / 8 0ù

é 4 / 5

- 2 / 5ù

é- 27 / 40

2 / 5 ù

=

ë

0û

ë-

û

=

-

ê

ú -

ê

ú =

ê

ú

;

1 / 8

5 / 4

2 / 5

-1 / 5

ë 0

0û

ë- 2 / 5

1 / 5 û

ë

û

A(1) = A(0)

+ A(0) =

é1

0ù

+ é- 27 / 40

2 / 5 ù

= é13 / 40

2 / 5ù

;

C

ê

ú

ê

2 / 5

ú

ê

ú

ë0 1û ë

-1/ 5û ë 2 / 5

4 / 5û

é-13/ 40 - 2 / 5ù é 0 ù

= -[1/ 5

2 / 5]T .

s(1) = -A(1)Ñf (x(1) ) = ê

- 2 / 5

ú

× ê

ú

ë

- 4 / 5û ë1/ 2û

Шаг 4. Поиск вдоль прямой

x(2) = x(1) + α(1) s(1)