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

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

Сентябрь 2012

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

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

Говоря о задачах минимизации выделяют несколько общих моментов: f

Определяют некоторую «скалярную» меру качества –

целевую функцию

Определяют набор независимых переменных и формулируют условия,

которые характеризуют их приемлемые значения (размерность задачи и ее

ограничения).

Решение оптимизационной задачи – это приемлемый набор значений

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

2Под оптимальностью обычно понимают минимальность

целевой функции.

Методы спуска

Рассмотрим итерационные методы, являющиеся более изощренными

по сравнению с методами нулевого порядка.
Формулируются они					x(0) Rn				(k 0)
следующим образом:
Пусть дан вектор начального(k 1) (k ) приближения(k)									,
очередное			x	x	k d	,		k
d (k )
приближение рассчитывается по формуле
где	d (k )
	- подходящим образом выбранное направление
и	d (k )
	- шаг –
	(k)T			(k)		(k)
положительноеd число,f (x определяющее) 0если (f x )величину0,
смещения вдоль		d	(k)	0если	( )f	(k)
направления						x0.
		.
3 Направление			называется направлением спуска,

если

Методы спуска

Методами спуска называются методы рассмотренного выше типа, вd (k )

которых векторы являются векторами спуска.

Поскольку	k 0
рассматриваются дифференцируемые функции, то для них
всегда	f (x(k ) k d (k) ) f (x(k) ),
существует достаточно малое		, такое, что

Используя возможностьf (x(k) k d (k) ) разложенияf (x(k) ) k f целевой(x(k) )T d (k)функции, в ряд Тейлора,0при kи ее0.

непрерывность, можно записать:k 0

где
Как следствие, при достаточно малых		из
4	последнего равенства

Ньютон

Sir Isaac Newton - President of the Royal Society - (25 December 1642 – 20 March 1727 [NS: 4 January 1643 – 31 March 1727]) was an English physicist, mathematician, astronomer,

natural philosopher, alchemist , and theologian, has been "considered by many to be the greatest and most influential scientist who ever lived."

http://en.wikipedia.org/wiki/Isaac_Newton

5

Ньютон

В июне 1661 года 18-летний Ньютон приехал в Кембридж. Согласно уставу, ему устроили экзамен на знание латинского языка, после чего сообщили, что он принят в Тринити-колледж (Колледж святой Троицы) Кембриджского университета. С этим учебным заведением связаны более 30 лет жизни Ньютона.

Ньютона зачислили в разряд студентов-«сайзеров» ( англ. sizar), с которых не брали платы за обучение. Документальных свидетельств и воспоминаний об этом периоде его жизни сохранилось очень мало. В эти годы окончательно сложился характер Ньютона — научная дотошность, стремление дойти до сути, нетерпимость к обману, клевете и угнетению, равнодушие к публичной славе. У него по-прежнему не было друзей.

6 В апреле 1664 года Ньютон, сдав экзамены, перешёл в

более высокую студенческую категорию «школяров»

Ньютон

1664 год в жизни Ньютона был богат и другими событиями. Ньютон пережил творческий подъём, начал самостоятельную научную деятельность и составил масштабный список (из 45 пунктов) нерешённых проблем в природе и человеческой жизни (Вопросник,

лат. Questiones quaedam philosophicae).

В дальнейшем подобные списки не раз появляются в его рабочих тетрадях. В марте этого же года на недавно основанной (1663) кафедре математики колледжа начались лекции нового преподавателя, 34-летнего Исаака Барроу, крупного математика, будущего друга и учителя Ньютона. Интерес Ньютона к математике резко возрос. Он сделал первое значительное математическое открытие: биномиальное разложение для произвольного рационального показателя (включая отрицательные), а через неё пришел к своему главному математическому методу — разложению функции в бесконечный ряд. Наконец, в самом конце года Ньютон стал бакалавром.

7

Методы спуска

Различные способы выбора направлений спуска приводят к разным методам минимизации:

Метод Ньютона, в котором направление спуска определяется по

формуле		d(k) H 1(x(k) ) f (x(k) ),
		H
с положительно определенной матрицей				, что обеспечивает
значительную область сходимости;
Приближенный метод(k)Ньютона1 (,k)в котором(k)
	d	Bk (x	) f (x	),
B 1			H 1(x(k) )		;
где k	- подходящая аппроксимация матрицы

8

Методы спуска

Градиентный метод или метод скорейшего спуска,
соответствующий	d (k)	f (x(k) )	.
выбору направления спуска по формуле
Таким образом,			Bk I

этот метод является приближенным методом Ньютона, в котором

. d (k)T f (x(k) ) f (x(k) ) 2 .

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

	d (k) f (x(k) ) d (k 1) ,
Метод сопряженных градиентов, для которого
		k
k
где	- скалярная величина, подбираемая таким образом,
чтобы	d (k )

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

9

Методы спуска

(k )	недостаточен для полного задания
Выбор направленияd
метода спуска. Ведь остается еще проблемаk		определения

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

скорость сходимости, но в то же время сохранял бы условие
сходимости:	f (x(k) k d (k) ) f (x(k) )
	k			заключается в
Обычно метод выбора параметра
решении одномерной задачи минимизации:
			,	(минимизирующееk)
	Найти значение(k)
функцию	( ) f (x		d	).
Теорема. Если параметр		является решением задачи
	(k	1) (k)
одномерной минимизацииf (наx		каждом)d 0шаге, то метод спуска

обеспечивает сохранение условия ортогональности

10 каждом шаге метода.