Одна итерация метода

3. Растяжение. Если	, то вычисляем точку
растяжения xe,

Вычисляем . Если , то добавляем эту точку в набор и переходим к новой итерации. В противном случае () добавляемв набор точку xr.

Итерация закончена.

Одна итерация метода

• 4. Сжатие. Если		, то проводим
операцию сжатия между		и лучшей
точкой из	и :

•Внешнее. Если , то есть существенно лучше, то проводим внешнее сжатие:

•Вычисляем и добавляем в

набор, если

. Переходим к (п.5)

Одна итерация метода

• 4. Сжатие.

• Внутреннее. Если	, то проводим
внутреннее сжатие:

• Вычисляем	и добавляем точку	в
набор, если	.Переходим к глобальному
сжатию (п.5)

Одна итерация метода

• 5. Глобальное сжатие.

• Вычисляем значения функции f(x) в n точках

• . Новыми вершинами являются точки

Nelder and Mead’s Method

Отражение и растяжение

Nelder and Mead’s Method

Внешнее, внутреннее и глобальное сжатие

Simplex Steps

Reflection

Contraction

Expansion

Limitations

An interesting open problem concerns whether there exists any function f(x) in R2 for which the Nelder-Mead algorithm always converges to a minimizer. The natural candidate is f(x; y) = x2 + y2, which by ane-invariance is equivalent to all strictly convex quadratic functions in two dimensions. A complete analysis of Nelder-Mead for x2 + y2 remains an open problem.

Applications

•function Func(X : TeVector) : Extended;

•	begin
•	result := sqr(x[1]-1)+sqr(x[2]-1)+sqr(x[3]-1);
•	end;

•procedure TForm1.btCalculateClick(Sender: TObject);

•	var
•	X : TeVector; MaxIter, Iter: integer; F_min : extended;
•	begin

•setlength(x, 4);

•MaxIter:= 1500; // максимальное число итераций

•	x[1] := -0.1;	// начальное приближение
•	x[2] := 1.1;
•	x[3] := 2.1;

•Simplex(Func, X, 1, 3, MaxIter, 1.e-14, F_min, Iter, 0.1, 1.0e-8, nil, 0, '');

•Label1.Caption := floattostr(x[1])+'; '+floattostr(x[2])+'; '+floattostr(x[3]);

•Label2.Caption := Inttostr(Iter)+'; ';

•x := nil;

•end;

	function Simplex
•	function Simplex(Func: TFuncNVar; X: TeVector; Lbound, Ubound: Integer;
•	MaxIter: Integer; Tol: Extended;
•	var F_min: Extended; var Iter: Integer{Iteration count};
•	Step: Extended; {для задания начального многогранника: скорее процент от текущей координаты}
•	ZeroCoordinateValue: Extended; {ноль, при котором шаг следует брать специфическим}
•	SB: TStatusBar; PanelN: Integer; PrefixStr: string): Integer;
•	{ ----------------------------------------------------------------------

•Minimization of a function of severalvariables by the simplex method

•of Nelder and Mead

• ----------------------------------------------------------------------

•	Input parameters	: Func = objective function
•	X	= initial minimum coordinates
•	Lbound,
•	Ubound = indices of first and last variables
•	MaxIter = maximum number of iterations
•	Tol	= required precision
•	Step	= Step used to construct the initial simplex ~ 1.5
•	----------------------------------------------------------------------
•	Output parameters : X = refined minimum coordinates
•	F_min = function value at minimum

•Possible results : OPT_OK

•	OPT_NON_CONV
•	---------------------------------------------------------------------- }