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

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

4.	k	1	n
5.	0	\|\|	f (x1 ) \|\| 2 \|\| f (x0 ) \|\| 2			=1/4.
5.	0					=1/4.
	p1= -	f (x1 ) +		0 p0=(-1/4,-1/2).
Итерация 2.
2.	Решим задачу одномерной минимизации по α :
	Ф(	1/ 8	/ 4,	/ 2)	4(1/ 8	/ 4) 3(	/ 2)2
	4(1/ 8		/ 4)	/ 2 1/ 8	/ 4	min .
	α1 = 1/4.
3.	Найдем
		х2 = х1+ α1 p1 = (-3/16,-1/8).				f (x2 )	(0,0) –

получено оптимальное решение, x*=x2

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

2.3.2.6.Метод Ньютона
Если в результате преобразования x = zQ	матрица
квадратичной формы приводится к единичной (т. е. QT HQ	E ), то
метод наискорейшего спуска
z1=z0- α* f (z0 ) ,

получает решение за один шаг.

В пространстве переменных х данный переход запишется в

виде

х1	Q 1 =х0 Q 1 - α* f (x0 ) Q				или
1	0	- α*	f (x 0 ) Q Q	1
х	=х	- α*		.

Так как

Q 1 Q =H-1 ,

то

х1 =х0- α* f (x0 ) H-1.

Итеративный метод вида

xk 1 xk	k	f (xk )H 1
	k

носит название метода Ньютона.

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

матрицей Гессе применение метода Ньютона с шагом

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

Существенным недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации.

Алгоритм метода Ньютона

Шаг 0. Задать параметр точности , выбрать х0 Rn , вычислить f(x0).

Шаг 1. Найти f (x0 ) и проверить критерий останова:

|| f (x0 ) ||< .

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

Шаг 2. Положить х0=х0- f (x0 ) H-1, вычислить f(x0) и перейти к шагу 1.

Пример. Найти методом Ньютона точку минимума функции

f (x) 4x12 3x22 4x1 x2 x1 ,

начав поиск с точки x0 (0, 0) .

Решение. Посчитаем вектор-градиент функции f (x) =(8x1-4x2+1;6x2-4x1) .

Матрица вторых частных производных имеет вид

H	8	4 .
	4	6

Найдем обратную матрицу

		H 1	1	6	4		.
				4	8
			32
			32
0.	Выберем		=0.001,		x0		(0, 0) ,		f(x0)=0.
1.	Посчитаем		f (x0 ) =(1,0), \|\|					f (x0 ) \|\|=1> .
2.	Положим
	х0=х0-	f (x0 ) H-1=			1	(6, 4)		(	3/16, 1/ 8) ,
	х0=х0-	f (x0 ) H-1=			32	(6, 4)		(	3/16, 1/ 8) ,
					32
	f (x0 )	3 / 32

3.f (x0 ) =(0,0) -найдено оптимальное решение

x* ( 3 /16, 1/ 8). .

Целевая функция квадратичная, поэтому решение задачи получено за одну итерацию.

Ответ: x*		3	;	x*	1	; f		3	.
1	16			2	8		min	32
	16				8			32

2.3.2.7.Задачи для самостоятельного решения

2.3.1.Найти различными методами точку минимума следующих функций:

4) f (x)	exp(x2		x2 )	2x x		3x ,	x0		(0,0);	0.01.
		1	2	1	2	2
2.3.2. Показать, что для квадратичной функции в методе
Ньютона шаг	*	1.
2.3.3. Найти минимум следующих функций:
	1)	f (x)	3(x	4)2		5(x		3)2	7(2x	1)2 ;
			1			2			3
	2) f (x) 1 2x 2x 4x x 10x2									2x2 ;
				1		2	1	2	1	2

3) f (x) x4	x4	2x2 x2		4x 3;
1	2	1	2
4) f (x) (x2	x	11)2		(x	x2	7)2 ;
1	2			1	2

5) f (x) x13 x22 3x1 2x2 2.

3.УСЛОВНАЯ ОПТИМИЗАЦИЯ

3.1.Постановка задачи математического программирования

Рассмотрим следующую постановку задачи:

	f (x)		min ,	(1)
			x Rn
где x	(x1 ,..., xn ) -	n -мерный вектор,		f (x) - функция, называемая
функцией цели,		Rn - допустимое множество. Требуется найти
такой	вектор x*	из	множества	, которому соответствует

минимальное значение целевой функции на допустимом множестве:

	x*	arg min f (x)
		x		Rn
З а м е ч а н и е . В дальнейшем вектор понимается как вектор-
строка.
Задача поиска максимума функции						f (x)	сводится к задаче
поиска минимума путем умножения функции на -1:
	x*	arg min f (x) .
		x	Rn
Задача поиска минимума и максимума называется задачей
поиска экстремума:
	f (x)			extr
			x	Rn
Если	Rn ,		то имеет место задача безусловной
оптимизации. В противном случае, т.е.						если	Rn	– задача
условной оптимизации.
Определение		1.	Точка		x*	называется		точкой
глобального	минимума		функции		f (x)	на множестве		, если

функция достигает в этой точке своего наименьшего значения, т.е.

f (x* )

f (x),

Определение

Точка

называется

точкой

локального минимума

функции

f (x)

на

множестве

, если

0, такое что

x : (x

) (

) , справедливо

неравенство

f (x* )

f (x).

З а м е ч а н и е .

качестве

нормы

вектора

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

x 2 .

Определение 3.

Множество

называется выпуклым,

если оно содержит отрезок, соединяющий любые две точки из

множества	, т.е. если		x1 , x2	и	[0;1] справедливо:
	x1	(1	)x2	.
Определение 4. Функция f (x) , определенная на выпуклом
множестве	называется выпуклой, если
	f ( x1 (1		)x2 )	f (x1 ) (1 ) f (x2 )
	x1 ,	x2	,	[0;1].

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

f ( x1 (1	)x2 )	f (x1 ) (1 ) f (x2 ) .
Определение 5. Задача (1) называется задачей выпуклого
программирования (ЗВП), если	f (x)	- выпуклая функция, а	-

выпуклое множество.

Для задач безусловной оптимизации необходимое условие экстремума сформулировано в т е о р е м е Ферма.

Т е ор е м а 1 (Ферма). Если x* - точка локального экстремума непрерывно дифференцируемой в т. х* функции f (x) , то

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

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



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