Методы нулевого порядка

спуска
Особенности программной реализации
Метод ГАУССА-ЗЕЙДЕЛЯ
Метод ПАУЭЛЛА
Метод РОЗЕНБРОКА

Методы спуска с перебором направлений
Хука-Дживса и Нелдера-Мидта

покоординатного спуска:
Гаусса-Зейделя,
Пауэлла,
Дэвиса-Свена-Кемпи (ДСК),
Розенброка.
Алгоритм этих методов в общем

одинаков и описывается следующим образом:

начальный шаг h одномерного спуска .
2. Выбирается n линейно независимых

направлений



Обычно это единичные координатные орты (вообще их можно выбрать исходя из знания свойств целевой функции).

x1

x2

d1

d2

(i=1..n), т.е. находится zmi, доставляющий


пересчитывается точка


При нахождении

min используется либо метод последовательного перебора, если функция не гладкая, либо метод квадратичной параболы для гладких функций.
В результате выполнения этих спусков, называемых циклом, точка сдвинулась на вектор

x1

x2

d1

d2

zm1

zm2

В зависимости от полученной информации о функции, делается некоторое преобразование

выбранных направлений:


Процесс вычислений повторяется с новой точки

x1

x2

d1

d2

zm1

zm2

Δ

d1

d2

вычисления минимизируемой функции, например, для целевой функции, имеющей вид


const n=2;
type

mas=array[l..n] of real;
function F(х:mas): real;
begin
F:=sqr(x[1]+2*x[2])
end;

MPSP(F:fun;
var x0:mas;eps,h:real;var fm:real);
внутри которой следует ввести:
для координат векторов

направлений массив D[i,k] где помещается i-я координата вектора dk
var
D:array[1..n,1..n] of real
zm,x,a,b:array[1..n] of real;
рабочие массивы zm, x,
a и b в методе Розенброка, ДСК, Пауэлла;

real): real;
begin
for k:=1 to n do
x[k]=x0[k]+z*D[i,k];
F1:=F(x);
end;

repeat
repeat
z0:=z1; y0:=y1;

z1:=z0+h; y1:=F1(z1);
until y1>y0;
h:=-h/4;
until abs(h) Result:=y0;
end;

. . . .
D[i.k]=........
end;

Отличаются методы видом оператора преобразования ∏ направлений

после каждого цикла спуска

do D[i,i]:=1;
repeat
dl=0;
for i:=1 to n do //спуск по направлениям

begin
zm[i]:=MPP(0,h,h/5);
x0:=x;
dl:=dl+abs(zm[i]); //погрешность
end;
PREOBD; h:=h*0.5;
Until dlfm:=F(x0);
End;

и спуск все время производится вдоль осей координат
x1
x2
x0

спуска по координатам может сильно замедляться
Для исправления этого недостатка используют

различные методы преобразования исходных векторов di

begin a[k]=0;
for i=1 to n do

a[k]=a[k]+zm[i]*D[i,k]
end;
for i: =n downto 2 do
for k=1 to n do D[i,k]=D[i-1,k];
da=0; for k=l to n do
da=da+sqr(a[k]); da=sqrt(da);
for k=1 to n do D[1,k]=a[k]/da;
end;

i,j,k,l: integer;
begin
for i=l to n do
for k=l to n do

begin a[i,k]=0; for j:=i to n do
a[i,k]=a[i,k]+zm[j]*D[j,k]
end;
da=0; for k=l to n do da=aa+sqr(a[1,k]); da=sqrt(da);
for k=1 to n do D[1,k]=a[1,k]/da;
for i=2 to n do
begin for k=l to n do
begin c[k]=a[i,k];
for j=1 to i-1 do
begin ad=0 for l=1 to n do ad=ad+а[i,1]*D[j,1]
c[k]=c[k]-ad*D[j,k];
end;
end;
dс=0; for k=l to n do dc=dc+sqr(c[k]); dc=sqrt(dc);
for k=l to n do d[i,k]=c[k]/dc;
end
end;

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

Последовательного покоординатного перебора
Хука-Дживса
Нелдера-Мида

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

если удачно, то делаем шаг по диагонали
h
h
h
h
h