Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

к=0,i=0 , q j e j , j 1, n, q0 en , y0 x0 .

Шаг 1. Найти

yi 1 yi		i	qi ,
		i
где
i	arg min f ( yi			i	qi ).
i				i

Шаг 2. Проверить условие i=n .

а) Если оно выполняется, то выяснить успешность поиска по n последним направлениям. Если yn+1=y1, поиск завершить, полагая x*= yn+1.

b) Если i<n, положить i=i+1 и перейти к шагу 1. Шаг 3. Положить хk+1=yn+1 и проверить критерий останова

(например, \|\|x0-x1\|\|<	или	\|f(x0)-f(x1)\|< ).
Если он выполнен, то вычисления завершить, полагая
x*=xk+1 .
Шаг 4. Положить
________
q j q j 1 , j 1, n 1, q0		qn yn 1 y1 , y0 xk 1 ,

i 0, k k 1

и перейти к шагу 1. Пример 2. Решить задачу

f (x)		2x 2		x 2	x x	2	min
		1		2	1	2
методом сопряженных направлений.
Решение.
0. Выберем x0	(	1	,1) , положим
0. Выберем x0	(	2	,1) , положим
		2
q0	e2 , q1			e1 , q 2			e2 ,

		y0	x0	( 1 ,1)	.
				2	.
1.	y1	( 1 ,1)	0	(0,1)	( 1	,1		0	)	.
1.		2	0		2			0		.
	Решим задачу одномерной минимизации :
			( )	(1	)2		1	(1		) min
							2

											0								5						y1						(			1	,						1 )				.
											0								4															2							4				.
2. Так как i<2,											положим i=1 и перейдем к шагу 1.
3.	y 2		(			1 ,					1 )								1	(1,0)										(	1									1		,				1 )				.
3.						2					4								1												2									1						4				.
	Решим задачу одномерной минимизации :
											(				)				2 (					1						)2								1			( 1										)					min
																								2														4				2
											1								7							y 2								(	1				,				1 )
																		16								y 2								(	16				,				1 )				.
																		16																	16								4				.
4. Так как i<2,											положим i=2 и перейдем к шагу 1.
	y 3		(			1			,		1 )									2			(0,1)								(			1			,					2						1 )
5.	y 3		(			16			,		1 )												(0,1)								(			16			,											1 )			.
5.						16					4																							16														4			.
	Решим задачу одномерной минимизации :
									Ф(					)				(			1				)2								1		(					1							)					min
									Ф(					)				(		4					)2						16				(					4							)					min
																				4											16									4
															7									y3						(		1				,					1			).
										2														y3						(						,								).
										2					32																16									32
															32																16									32
6.	Так как i=2 и y3																		y1 , положим x1																							y3						(		1			,			1		) .
6.	Так как i=2 и y3																		y1 , положим x1																							y3						(					,					) .
																																																16								32
7.	Положим
	q1		e2 , q0														q 2							y 3							y1												(		7			,		7			),
	q1		e2 , q0														q 2							y 3							y1												(		16			,		32			),
	y0		(			1			,			1				)
	y0		(		16				,							)	,	i=0 , к=2
					16						32						,	i=0 , к=2
	и перейдем к шагу 1.
	y	1	(			1		,			1			)					0				(			7		,		7			)		(					1		7				0			,		1			7		0	)
8.	y		(	16				,			32			)									(		16			,		32			)		(							16							,				32				)		.


	Решим задачу одномерной минимизации :
	( )		2(				1		7		0		)		2				(			1		7	0		)		2					(	1			7				0	)(					1		7			0		)				min
	( )		2(						16				)						(				32				)							(	16								)(					32							)				min
									16														32												16													32
		0				1						y			1				(0,0)
						7						y							(0,0)								.


9. Так как i<2,											положим i=1 и перейдем к шагу 1.

10. y2	(0,0)				1 (0,1)					(0, 1 ) .
Решим задачу одномерной минимизации :
			(	)					2		min
			(	)							min
		1			0				y2		(0,0) .
11. Так как i<2,			положим i=2 и перейдем к шагу 1.
	y	3	(0,0)						2 (			7		,			7	)			(		7		2	,	7		2	)
	y		(0,0)						2 (			16		,			32	)			(			16		,		32		)	.
												16					32							16				32			.
Решим задачу одномерной минимизации :
(	) 2(		7		2		)	2	(	7	2		)		2				7		2	7			2				min
(	) 2(			16			)		(	32			)							16			32						min
				16						32										16			32
2	0		y3			(0,0) .
12. Так как i=2 и y3 = y1 , положим x*= y3 =(0,0).
Графическая					иллюстрация											решения									приведена на

рис.2.3.5.

Рисунок 2.3.5.

Ответ: x1* 0; x2* 0; fmin 0.

x k 1 имеет вид

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

Данный

метод

позволяет получать

сопряженные

направления p k для квадратичной функции f(x) с использованием

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

			_________
pk 1	f (xk 1)	k	pk , k 0, n 1,
		k
где
k	\|\| f (x k 1 ) \|\| 2 \|\| f (x k ) \|\| 2 .

Формула пересчета точки

хk+1=хk+ αk pk ,

причем шаг αk ищется по правилу наискорейшего спуска.

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

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

Шаг 0.	Задать параметр точности		, выбрать
	х0 Rn ,вычислить f(x0).
Шаг 1.	Положить к=0, p0= - f (x0 ) ;
Шаг 2.	Решить задачу одномерной минимизации
	Ф( ) f (x0	pk )	min ,
			0

т.е. найти αk. Шаг 3. Положить

хk+1=хk+ αk pk . .

Проверить критерий останова: || f (xk 1 ) ||< .

Если он выполнен, то вычисления завершить, полагая x*=xk+1, f*=f(xk+1) .

Шаг 4. Проверить условие к+1=n . Если оно выполняется, то положить

x0=xk+1, f(x0)=f(xk+1) и перейти к шагу 1 (обновление метода).

Шаг 5. Вычислить коэффициент

k	\|\|	f (x k 1 ) \|\| 2 \|\| f (x k ) \|\| 2
k
и найти новое направление поиска
pk+1= -		f (x k 1 ) + k pk .

Положить к=к+1 и перейти к шагу 2.

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

вкачестве интервала поиска α отрезок [0,1].

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

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

f (x) 4x		2	3x 2	4x x	2	x	,
	1		2	1	2	1	,
начав поиск с точки x0	(0, 0) .
Решение.
f (x) =(8x1-4x2+1;6x2-4x1).
Итерация 1
0. Зададим =0,01, x0=(0,0),				f (x0 ) = (1,0), \|\|			f (x0 ) \|\|=1.
1. Положим к=0, p0= -		f (x0 ) =(-1,0).
2. Решим задачу одномерной минимизации по α:
(	,0)	4	2	min .
α0=1/8.
3. Найдем
х1=х0+α0p0=(-1/8,0),			f (x1 )	(0,1/2),
\|\| f (x1 ) \|\|	1/2		.
			.
			52

Источник: https://studfile.net/preview/16565974/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)