file_12171 / МОР Пособие

Шаг 4. Если	( >) − ( )| <	, перейти к шагу 5, иначе присвоить
счетчику итераций|		← + 1
	следующее значение	, и перейти к шагу 1.

Шаг 5. Оформление сводной таблицы с результатами вычислений.

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

В методе сопряженных градиентов лишь в стартовой точке при = 0 направление поиска совпадает с направлением наискорейшего спуска:

= − = −

H( )

(2.4a)

но во всех последующих

итерациях

при

направление поиска

скобки используются для

определяется по более сложной формуле (угловые ≥ 1

обозначения скалярного произведения):

,

= − +

(2.4b)

P,

P

P

Алгоритм 2.2. Поиск минимума функции многих переменных методом

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

Шаг 0. Задать точность

вычисления

минимума целевой

функции.

в

← 0.

Выбрать стартовую точку и присвоить счетчику итераций значение

.

Шаг 1. Вычислить текущее значение целевой функции

точке

Шаг 2. Определить направление поиска

в

соответствии с (2.4),

и

(

)

выбрать величину шага

согласно правилу (2.1). Найти следующую точку в

итерационной

последовательности по формуле:

> =

+в

.

Шаг 3. Вычислить значение целевой функции

новой точке.

Шаг 4. Если

шагу 5, иначе присвоить

, перейти к

(

>)

следующее значение

, и перейти к шагу 1.

счетчику итераций| (

>) − (

)| <

с результатами вычислений.

Шаг 5. Оформление сводной таблицы←

+ 1

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

11

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

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

( ) = +				+	1
			U		2	U	U	,
где коэффициенты	,	образуют симметричную матрицу:
		c1 1		c1 2 ..		c1 n
		c2 1		c2 2 ..		c1 n
		..		.. ..		..
		cn 1		cn 2 ..		cn n

(2.5)

(2.6)

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

В случае квадратичной целевой функции (2.5) легко вычисляются компоненты градиента:

= K = + , = 1,2, … (2.7)

U

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

Приведем без доказательства формулу, позволяющую для произвольной квадратичной целевой функции (2.5) найти величину шага, обеспечивающую минимум функции (2.1) при любом выборе направления поиска:

= −	U	U U	,	(2.8)
				12

Разумеется, при численной реализации метода наискорейшего спуска или метода сопряженных градиентов для поиска минимума целевой функции приходится использовать численные методы (например, комбинированный метод секущих и касательных). Мы можем позволить себе пользоваться формулой (2.8), поскольку перед нами стоит чисто учебная задача: сравнить эффективность двух методов поиска минимума в классе квадратичных функций. Именно в этом классе функций преимущества метода сопряженных градиентов проявляются наиболее ярко: если в методе наискорейшего спуска последовательные итерации постепенно и довольно медленно приближают нас к минимуму целевой функции, то метод сопряженных градиентов приводит точно к цели за конечное число итераций, равное размерности пространства, на котором определена целевой функции. Иллюстрацией могут служить графики на рис. 2.1 и 2.2, где показаны «траектории» поиска минимума квадратичной целевой функции в двумерном случае ( = 2). Траектории поиска минимума целевой функции получаются путем последовательного соединения точек, найденных в итерационном процессе, прямолинейными отрезками.

5
2.5
0
2.5
5	2.5	0	2.5	5
5

Рис.2.1. Типичная траектории поиска минимума квадратичной целевой функции при использовании метода наискорейшего спуска.

13

5
2.5
0
2.5
5	2.5	0	2.5	5
5

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

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

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

сцентром в точке минимума функции).

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

14

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

( , ) = −0.2 − 0.52 − 0.84 + 1.4 + 1.2 + 1.8 (2.9)

Рис. 2.3. График квадратичной целевой функции (2.9).

Компоненты градиента целевой функции (2.9):

K	= −0.52 + 2.8 + 1.2	(2.10 )
K
K	= −0.84 + 1.2 + 3.6	(2.10 )
K

Выберем стартовую точку с координатами x 8 = 0.5 и x 8 = 0.2, и зададим точность вычисления значения минимального значения целевой функции ε = 0.00001.

Ниже в таблице 2.1 приведены результаты поиска минимума целевой функции (2.9) методом наискорейшего спуска.

15

Таблица 2.1. Поиск минимума методом наискорейшего спуска.

			0			1	2	3			4	5	6
			0.5			0.20473	0.15049	0.11322			0.10637	0.10167	0.1008
			0.2			0.07345	0.2	0.18403			0.2	0.19798	0.2
			-1.12			-0.14138	-0.14138	-0.01785			-0.01785	-0.00225	-0.00225
			-0.48			0.32989	-0.06059	0.04164			-0.00765	0.00526	-0.00097
	L(	)	0.26364			0.3836	0.26364	0.3836			0.26364	0.3836	0.26364
			-0.086			-0.28172	-0.30643	-0.30955			-0.30994	-0.30999	-0.31
		В таблице 2.1 приведены координаты								,	точек	, получающихся в
ходе реализации алгоритма 2.1, координаты											направления поиска ,
выбранного в данной итерации, величина шага											, а, также очередное значение
целевой функции						.
		Как видно		из данных, приведенных в таблице 2.1, заданная точность
						L( )

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

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

Таблица 2.2. Поиск минимума методом сопряженных градиентов.

	0	1	2
	0.5	0.20473	0.1
	0.2	0.07345	0.2
	-1.12	-0.23855	0
	-0.48	0.28825	0
	0.26364	0.43902	0
L( )	-0.086	-0.28172	-0.31

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

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

16

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

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

17

Рекомендуемая литература

Метод секущих, метод касательных и комбинированный метод секущих и касательных

Березин И.С., Жидков Н.П. Методы вычислений, т. 2. – М.: Физматгиз, 1962.

Общая постановка задачи и методы поиска оптимальных решений

Беллман Р., Калаба Р. Квазилинеаризация и нелинейные краевые задачи. – М.: Мир, 1968.

Моисеев Н.Н. Численные методы в теории оптимальных систем. – М.: Наука, 1968.

Полак Э. Численные методы оптимизации. Единый подход. – М.: Мир, 1974.

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

Березин И.С., Жидков Н.П. Методы вычислений, т. 2. – М.: Физматгиз, 1962.

Общая концепция метода сопряженных направлений

Davidon W.C. Variable metric methods for minimization. AEC Research and Development Rept. ANL 5990 (Rev.), 1959.

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

Fletcher R., Reeves C.M. Function minimization by conjugate gradients. Comp. J., v.7, n.2, p.149-154, 1964.

Поляк Б.Т. Методы минимизации функций многих переменных. Экономика и математические методы, т3, №6, с.86-107, 1967.

Поляк Б.Т. Метод сопряженных градиентов в задачах на экстремум. Журнал ВМ и МФ, т.9, №4, с.807-821, 1969.

Klessig R., Polak E. Efficient implementations of the Polak-Rebiere conjugate gradient algorithm. Electronics Research Laboratory, Memo №279, University of California, Berkeley, 1970.

18