ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Константин Ловецкий

Октябрь 2012

1	Кафедра систем
	телекоммуникаций

Линейный поиск

Методика линейного поиска

Рассмотрим итеративные методы, останавливающиеся при выполнении некоторого критерия останова итеративного процесса. При этом предполагается, что условия,

определяющие(kнаправление) (						спуска,
T				k)				(k)
d f (x					) 0если				0,
							(f x )
	d	(k)	0если			(		(k)
							)f x0.

выполнены.
Практика показывает, что искать точное решение задачи о
минимуме функции	( ) f (x(k) d(k) )

не обязательно. Кажется, что(			достаточно добиться на каждой
	f (x	k 1)		) f (x	(k)	)
итерации выполнения условия
d (k )	x(k )			.
при фиксированных	и
2

Линейный поиск

Однако простейшая процедура, заключающаяся в выборе

достаточно	k	, которое затем
большого начального значения						(k)
		f (x	(k 1)	) f	(x		)
уменьшается (делением

пополам) до момента, пока не выполнится условие

,

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

Необходимо использование более строгих правил выбора параметра шага

для обеспечения сходимости метода.							k
M		(k 1)		1	(k)	(k)		(k)
Отметим, что0 приv	выбореx шагаf (xхочется) f (xпреодолетьd )								две
основные проблемы:				k

медленная скорость сходимостиf (xи(k)малая)T d (k) , величина шага.

Первая может(0,1/ 2)быть решена требованием выполнения 3 условия:

Линейный поиск

Это требование обеспечивает некую усредненную скорость спуска на очередной итерации не меньше определенной доли от величины, достигнутой на

предыдущей итерации.

Чтобы шаг метода не был слишком маленьким,

накладывается еще одно условие

(но так, чтобы

f (x(k)

d (k) T d

(k)

f (x(k) )T d (k) ,

удовлетворялось и предыдущее):

( ,1)

k

5

,10

1

1

,1/ 2

10

,

10

(**)

. На практике обычно выбирают

при

f (x(k) k d (k) )T d(k) f (x(k) )T d(k)

,

Иногда последнее неравенство заменяют более слабым:

(***)

f (x(k) )T d(k) 0,

d (k)

поскольку

-

(вспомним, что

направление спуска).

4

Линейный поиск

						f (x) M	x Rn
	Свойство. Предположим, что						для всех
	. Тогда существует				интервал
	I	c,C ,	0 c C						(***)
	такой, что в методе спуска условия (*) иk(**) или (*) и
							I	0,1 / 2
	удовлетворяются для любых						при
	,1
	и	.	k			можно обеспечить многими
	Выбор параметров
	способами, наиболее современной стратегией является
								0,1 / 2
					1			(0,1)
	перебор с возвратом
				k
	(backtracking technique): при фиксированном значении
	начиная со значения					уменьшаем его умножением
	на					x	x(k )
	до тех пор, пока не выполнится условиеf (*).								J
	Эта процедураd		приводится ниже. В качестве входных
	параметров используются текущее значение вектора ,
						x(k 1)
	содержащее
			, имена подпрограмм, вычисляющих
5	значение функции k					и ее якобиана	,
	вектор	, содержащий текущее направление поиска, а

также значения

Линейный поиск

6

Линейный поиск с возвратом

http://www.hbmeyer.de/backtrack/backtren.htm

Поиск с возвратом (англ. Backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором

множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.

Термин backtrack был введен в 1950 году американским математиком Дерриком Генри Лемером.

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

7 исследователями еще до его формального описания.

Методы оптимизации

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

Для методов спуска особый интерес представляют такие
функции, для				k		может быть вычислен точно.
которых параметр шага
Например,				f (x)	1	x	T		T
квадратичныеn n					2			Ax b x
			функции							b R	n
A R
где									x
	x		симметричная и положительно определенная
									Ax b 0
матрица и
В этом случае необходимое условие того, что										точка
				f (x Ax b r,					H (x) A.
минимума функции f(x),
это то, что		является решением системы								.
В самом деле, легко проверить, что

8

Как следствие, все итеративные методы решения систем

Методы спуска для квадратичных функций

		d (k)
В частности, при заданном направлении спуска
можно определить	k	, такую, что функция
оптимальную величину шага

достигает

минимумаdвдоль направления спуска.

f (x(k) d(k) ) d(k)T r(k) d(k)T Ad(k) 0,

Приравняем к нулю производнуюk вдольk направления спуска:d k

d(k)T r(k)

откуда следует, что минимумk достигается. при

d(k)T Ad (k)

9

Методы спуска для квадратичных функций

Отклонение от точного решения на

-м шаге процесса

минимизации

k

x(k 1)

x(k) k d(k) ,

можно вычислить по формуле:

x

(k 1)

*

2

(x

(k 1)

* T

A(x

(k 1)

*

)

x

A

x

)

x

x

(k)

*

2

2 k d

(k)

A(x

(k)

*

)

x

A

x

k2d (k)T Ad(k).

10