lec_opt1

	Допустим что мы совершаем малое перемещение	х. В каком случае (в точке)
будет:	* больше, чем заданная: тогда, когда	угол – острый
f (x +	x)= f (x)+(gradf , x)+O(K)= 0 .

*- если под прямым углом, то не изменяется;

*- если под тупым углом, то приводит к уменьшению функции.

1. у = f (х1 , х2 )

строим поверхности

z

y

x

2. Идет построение в плоскости х1 и х2. Берут точку – определяющую значение аргумента. Находят точку в которой функция имеет тоже самое значение, в результате получаем линию в которой функция имеет постоянное значение – изолиния (линия уровня).

х2	z
х2	изолиния

х1 х1

- изолиния

y

x

Вектор grad составляет прямой угол с изолинией. Вернемся к формуле:

f (x + x	2	, x	2	+ x	2	)= f (x , x	2	)	+	∂f	x +	∂f		x	2	+ ∂2 f	(	x )2	+ ∂2 f	(	x	2	)2	+O(K)
1						1				∂x	1	∂x				∂x2		1	∂x2
						14243							2
						постоянный	член		1							1			2

11

Квадратичная аппроксимация

(или квадратичное приращение)

Линейное отображение:

L : Rm → Rn ; x Rm ;

y Rn

y = y(x)- линейное отображение, если:

1.свойство аддитивности - ϕ(x + y)=ϕ(x)+ϕ(y) ;

2.свойство однородности - ϕ(kx)= kϕ(x)

Линейное отображение можно задать матрицей:

y = Ax

	т
		y = A(Bx); C = AB ;
п		a j = ∑aik bkj - основная формула
		k

1
i			1
					j
A : Rn → Rn отображение				y = Ax			yi = ∑aij x j Z = By = (BA)x
								j
2 задачи:
- решение системы уравнений						(х)
	y = Ax − линейный		вектор

и обратное отображение – найти х А-1 – обратное отображение;

АА−1 = I = A−1 A следовательно строки матрицы ортогональны столбцам другой матрицы

-нахождение собственных значений

Используя матрицу можно найти более сложную функцию : Z = (Ax, x)-

квадратичная форма.

Z = Z (x)= Z (x1 , x2 ,K, xn ) - функция нескольких переменных Z = ∑∑aij xi x j .

i j

Рассмотрим подробнее.

12

Есть матрица:	2		3
	А =
		−1	4

Z = 2x1 x1 +3x1 x2 −1x2 x1 + 4x2 x2 - квадратичная форма

Z = 2x12 + 2x1 x2 + 4x22

2		2
A' =
	0	4

А и А/ определяют одну и ту же квадратичную форму следовательно значения этой формы не однозначно. Если по заданной квадратичной форме найдем симметрию, то она будет однозначная.

А = 12 (А+ АТ );

2		−1		;	1				2		1
АТ =							(А+ А)=
	3	4				2				1	4

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

Вернемся к квадратичной форме:

Z= (Ах, х)= ∑∑aij xi x j

ij

Рассмотрим функцию 2-го порядка:

Z = а11 x12 + 2а12 x1 x2 + а22 x22

Допустим, что а12 = 0 , матрица диагональная.

1. а11 , а22 > 0

x2

x1

Эллипсы 0

Эллиптический

парабалоид

2. а11 , а22 < 0

13

3. а11 > 0, а22 < 0

xx

x2

Гиперболы	Седло

Допустим, что а12 ≠ 0 . Тогда вся картина просто повернется на некоторый угол по оси Z.

Рассмотрим п-мерный случай.

Квадратичная форма называется положительно определенной областью если она не отрицательная.

1.(Ах, х)≥ 0 , причем обращается в ноль, в том случае если х = 0 ( (Ах, х)= 0 х = 0 ). Этот случай соответствует эллиптическому параболоиду.

2.(Ах, х)≤ 0 , (Ах, х)= 0 х = 0 .

3.Знаконеопределенность.

(Ах, х)<>0 соответствует п-мерному эллиптическому гиперболоиду (п-мерное

седло)

Рассмотрим 2-мерное пространство:

Z = 0x12 + x22

Если квадратная матрица называется положительно определенной, то и матрица положительно определенной.

Рассмотрим разложение функции 2-х переменных в ряд Тейлора:

f (x + x		, x		+ x		)= f (x	, x		)+	∂f	x +	∂f		x		+	∂2 f	(	x )2	+	∂2 f		х х
										∂x		∂x					∂x2				∂x ∂х
1	2		2		2	1		2			1		2		2				1			1		2
										1							1				1	2

+∂∂2 f ( x2 )2 +O(K)

x22

квадратичная матрица задается матрицей Н

f (x + x)= f (x)+(gradf , x)+(Н х, х)+O(K)= 0

матрица составленная из членов 2-го порядка

14

		∂	2	f
		∂x2
	Н =	∂2		f
				1
		∂x2 ∂x1

Матрица Н – матрица Гесса.

hij = ∂∂2∂f xi x j

	∂	2	f
	∂x1∂x2
					- матрица симметрична
	∂2		f
	∂x22

- определение матрицы Гесса

Если матрица (матрица Гесса) в точке локального экстремума положительно определена, то это точка – локального минимума, если матрица отрицательно определена, то это точка – локального максимума, а если не определена – седловые точки.

Локальный max или min

Седловая точка

Минимизируем:
f (x , x	2	)= 2x2 + cos x x						2	+3x2			→ min
1			1				1				2
Найти частные производные:
1.		∂f	= 4x		− x	2	sin x x			2	= 0 (grad = 0);
		∂x1	1						1
2.		∂f	= 6x	2	− x		sin x x			2	= 0
		∂x1				1			1

Эта система позволяет найти все точки экстремума:

∂f

∂x1∂f∂x1

=4x1 − x2 sin x1 x2

=6x2 − x1 sin x1 x2

те х1 и х2 которые удовлетворяют уравнениям и будет точками экстремума.

Допустим, что	х* = 3,5		х* = 2,7 . Надо составить функцию второго порядка и
		1	2
подставить х*	х*	и посмотреть их.
1	2

Необходимые условия – помогают охарактеризовать искомую точку: 1. grad f = 0

15

2. H = ∂f

∂xi ∂x j

Н≥ 0 – локальный минимум;

Н≤ 0 – локальный максимум;

Н– не определена – седловая точка.

Для поиска используют численные методы.

Постановка:

Требуется f (x)→ min , где х – вектор x = (x1 ,K, xn ) - т.к. нет ограничений

задача безусловной оптимизации.

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

Методы прямого поиска

x2

y1

y2

x0K

yn

	Должны	задать	начальное	приближение
	точки х0;
	хк - некоторое		приближение полученное
	после к – итераций;
	вычислить значение точки в окрестности
	точки хк ;
	Из данных точек выбрать точку в которой
	функция принимает наименьшее значение,
x1	выбираем	ее	и строим	вокруг нее
	окрестность.

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

В таком виде этот метод не эффективен.

Пример:

Шаг по х1 берем больше, а по х2 – сохраняем. Поскольку мы свободны в выборе точек, то можно менять шаг и направление.

Методы:

1.Хука-Дживса;

2.Нелдера-Мида (используется п-1 угольник)

Преимущества метода прямого поиска:

1.простота;

2.не нужны производные.

Недостатки:

1.плохая сходимость;

2.применим для небольшого числа переменных.

п≤ 10÷20

16

2п точек:

в случае 2-х переменных – 4 точки; в случае 3-х переменных – 6 точек.

Этот метод применим в простых случаях, когда эти недостатки себя не проявляют.

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

x2

		x(K +4)		Существует	приближенная			точка
				минимума. Минимизируя функцию по
				направлению	к	х1,	на	прямой
				используется	любой	метод	одномерной
	x(K +2)	x(K +3)
				минимизируют, х2 – фиксируют. Далее
				выполняют одномерную оптимизацию по
xK	x(K +1)			х2, фиксируя х1.

x1

Этот процесс повторяют до тех пор пока следующая точка не окажется близка к точке приближения.

Градиентные методы

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

Рассмотрим grad целевой функции.

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

– grad f.

x2

S

− gradf

gradf

x1

Для выбора расстояния нужно применить метод одномерной оптимизации. Прекратить поиск, когда величина grad f станет достаточно малой. Этот метод гарантирует, что найдена либо точка локального минимума, либо седловая точка.

17

Анализ метода.

Линии постояных значений целевой функции

Логический min

Вектор

антиградиен

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

Пусть мы выбрали начальное приближение. Отыскивая наименьшее значение по направлению траектории (наименьшее значение там где происходит касание grad f линии уровня).

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

x1

Траектория

x0

Если линии уровня Z = x12 + x22 - окружности, то приходим сразу в точку локального минимума.

18

f (x)= const(одночлен)

Метод Ньютона

1.

- один постоянный член любой точки данной функции

является оптимальным – тривиальный случай;

2.

линейная функция (двучлен)

f (x)= C1 x1 +C2 x2

+K+Cn xn +C0 = (C, x)+C0

gardf = f = C (возможно бесконечное уменьшение и увеличение)

1 и 2 не подходят для оптимизации.

3.

трехчлен

f (x)= (C1 x1 +C2 x2

+K+Cn xn )+C0 + ∑∑Sij xi x j

i

j

f (x)=

1

(Qx, x)+ (C, x)+C0 ;

2

(Qx, x)

= ∑y j x j = ∑∑qij xi xy

j

i

j

без ограничения общности можно положить что матрица q – симметричная

qij = q ji

Разложим функцию в ряд Тейлора (должно быть 3 члена). Чтобы найти

линейный член квадратичной функции, надо взять grad.

∂

∂

∂

∂

∑∑qij xi x j =

∑∑qij

(xi x j

)=∑∑qij

xi +

x j =∑qкi xi +

∂xк

∂xк

∂xк

∂хк

i

j

i

j

i j

i

∑qкj x j =∑qкj x j + ∑q jк x j = 2∑qкj x j = 2Qx

j

j

j

j

grad(Qx, x)= 2Qx ; gradf = Qx +C ; С = 0

Найдем матрицу Гесса (матрица вторых частных производных)

	∂2 f
H =			= Q
	∂xi ∂x j
элемент матрицы Гесса является элементом			функции Q. hij = qij (все частные

производные высших порядков равны 0).

Функция экстремальна, если grad в данной точке равен 0, gradf = Qx +C следовательно условие экстремальности Qx = −C - система.

Необходимое условие оптимальности:

Если Q > 0 решение данной системы существует и оно единственное

(совместная система).

Если Q < 0 решение данной системы существует и оно единственное, т.е. если Q знакоопределена, то существует решение и оно единственное.

Если имеем квадратичную функцию и матрица положительно определена, то линии уровня – эллипсы.

Собственные значения определяют оси эллипсов.

19

x2

x2*

x*	x
1	1

Чтобы определить координаты точки локального минимума, нужно решить систему Qx2 = −C .

Пусть f(x) – произвольная функция и надо найти точку локального минимума. Разложим функцию в ряд Тейлора в окрестности точки.

f (xк + хк )= f (хк + f хк )+ (Н хк , хк )+О(K)

Пусть функция не квадратичная, эллипсы примерно отражают кривизну линий

уровня и находятся в окрестности точки хк . В окрестности точки хк находим приближение и заменяем эту функцию квадратичной функцией, которая получается из разложения в ряд Тейлора. Далее решаем задачу минимизации.

Находим точку минимума и рассматриваем эту точку как следующее приближение и т.д.

Для нахождения точки минимума квадратичной функции (зависит от х )необходимо решить систему:

Н хк = − f (хк )

Окончательно следующее приближение хк+1 = хк + хк .

хк+1 = хк − Н−1 f (хк ) - формула Ньютона (обобщение формулы минимизации одной переменной)

Выполнение метода останавливается когда ≈ 0 , т.е. когда хк очень мало. Для получения практической точности достаточно выполнить 4 итерации метода Ньютона.

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

Недостатки:

1.на каждом шаге итерации надо находить решение системы Н хк = − f (хк );

2.С ростом числа итераций Н – разрежается, т.е. большое число членов становится равными 0.

Все формулы безусловной минимизации можно записать в общую схему:

1.выбор направления;

2.выбор шага.

20