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

Begin

f(x) grad(x) rvs(x,v,h,e)

x,e,h

v=grad(x)./norm(grad(x))

[xm,Fm]=rvs(x,v,h,e)

dx=xm-x

ndx=norm(dx)

x:=xm: Fx:=Fm

ndx>e

xmin,Fmin

End

	function
	[xm,Fm]=rvs(x,v,h,e)
	xm=x; Fm:=f(x)
	ІhІ<=e
	x=xm-h*v	End
	Fx:=f(x)
	Fx<Fm
	h:=-h/3	xm:=x
		Fm:=Fx
		11

function nspusk	function [xm,Fm,it]=rvs(x,v,h,e);
x=[2;2]; e = 0.01; h =1;	xm=x; Fm=f(xm);
Fx=f(x);	while abs(h)>e
while 1>0	x=xm-h*v;
v=grad(x)./norm(grad(x));	Fx=f(x);
[xm,Fm,itv]=rvs(x,v,h,eps);	if Fx<Fm
dx=xm-x;	xm=x; Fm=Fx;
ndx=norm(dx);	else
x=xm; Fx=Fm;	h=-h/3;
if abs(ndx)<eps break; end	end
end;	end
	function y=f(x);
	y=8*x(1)^2+4*x(1)*x(2)+5*x(2)^2;
	function g=grad(x);
	g=[16 * x(1) + 4 * x(2);
	10 * x(2) + 4 * x(1)];

Симплексный метод

Симплексом в n-мерном пространстве называется выпуклый многоугольник с n+1 вершиной.

n=2 треугольник

n=3 тетраэдр

12

			Алгоритм								(0)
1. Дана функция 2x переменных f ( x ), точность ε, параметр h, начальное приближение x
2. Вычисляем координаты вершин симплекса
(1)	(0)	(2)	(0)		h		(3)	(0)		0
x	x	x	x				x	x
					0					h

(1)

(2)

(3)

3. Вычисляем значения функции

F1 f ( x

)

F2 f ( x

) F3

f ( x

)

худ

4. Определяем худшую вершину

x

, Fхуд

и координаты отраженной вершины,

она будет лежать на прямой исходящей из худшей вершины и проходящей через

середину противоположной грани

отр

ср

ост1 ост2

ср

худ

ост1

x

x

x

0.5*( x

x

);

V x

x

ср

отр

худ

отр

ост1

ост2

худ

x

x

x

2

V;

x

x

x

x

худ

ост2

отр

x

Fотр

x

f ( x

)

13

5. Сравниваем значения функции

Fотр Fхуд

6. Условие выполняется. За новый симплекс принимаем симплекс с вершиной

отр	худ
x	вместо x	и повторяем с пункта 3

7.Условие не выполняется. Проверяем условие окончания h< ε

8.Условие окончания выполняется. Выводим координаты и значение функции лучшей вершины

(0)
9. Условие не выполняется. За x	принимаем лучшую вершину последнего

симплекса, уменьшаем длину грани h=h/3 и повторяем с пункта 2.

fxx=inline(‘8*x(1)^2+5*x(2)^2+4x(1)*x(2)')

[x,y,opt]=fminsearch(fxx,[0;0])

			1
пример: f (x1, x2 ) 8x12 4x1x2 5x22		x0
	h=1, eps=0.2			14
			1

№	x1	x2	f(x1,x2)		h	точки симплекса и примечания
1	1.00	1.00	17.0		1	симплекс т.1,2,3	т.2	худшая отражаем
2	2.00	1.00	45.0
3	1.00	2.00	36.0
4	0.00	2.00	20.0			удачно симплекс 1,3,4		т.3 худшая
						отражаем
5	0.00	1.00	5.00			удачно симплекс 1,4,5		т.4 худшая
						отражаем
6	1.00	0.00	8.00			удачно симплекс 1,5,6		т.1 худшая
						отражаем
7	0.00	0.00	0.00			удачно симплекс 5,6,7		т.6 худшая
						отражаем
8	-1.00	1.00	9.00			неудачно 1>0.2 h=h/3 = 0.33
1	0.00	0.00	0.00		0.33	симплекс т.1,2,3, т.2 худшая отражаем
2	0.333	0.00	0.889
3	0.00	0.333	0.556
4	-0.333	0.333	1.00			неудачно 0.33>0.2	h=h/3 = 0.11
1	0.00	0.00	0.00		0.11	симплекс т.1,2,3 т. 2 худшая отражаем
2	0.111	0.00	0.0988
3	0.00	0.111	0.0617
4	-0.111	0.111	0.111	0.00		неудача 0.11<0.2	ответ т. 1
								15
	Ответ:		x			f ( x ) 0.000
				0.00

20

36

x2

9

5

17 45

0.89

0	0.56	8
	1.00

x1

16