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

градиенту
Метод сопряженных градиентов

тем более эффективно можно достичь минимума, если этой информацией правильно

распорядиться
Методы нулевого порядка фактически не располагают никакой информацией о функции (это черный ящик). Правда в процессе спуска они ее накапливают и используют для очередного спуска (например метод Розенброка осуществляет поворот координат в зависимости от результатов предыдущего спуска)
В методах первого порядка при выборе следующего направления спуска используется градиент функции в текущей точке и в предыдущей

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

Это свойство в основном и используется для построения методов минимизации первого порядка.
При этом направление наискорейшего убывания в данной точке не всегда оказывается наилучшим для спуска к минимуму.
Поэтому для повышения эффективности вводят различные поправки.
При выборе очередного направления используют накопленную информацию о функции из предыдущих спусков.
Множество возможностей введения таких поправок определяет многообразие различных методов первого порядка.

склоне и отпускаем круглый камень.
По какой траектории он будет

катиться? Видимо по такой которая здесь показана
Траектория задается функцией координат от времени



От чего зависит эта траектория?

∇f(x1,x2)

x1

x2

тяжести шарика
- сила трения шарика
уравнение движения шарика

новую точку
Подставляем

получаем и т.д.

Можно использовать разные методы решения этой задачи Коши
Мы используем то, что вам уже знакомо

x,dF:mas;n:byte);
Begin
df[1]:=6*x[1];
df[2]:=-2*x[2];
End;

невозможно просто вычислить
Function F(var x:mas,n:byte):real;
Begin
f:=sqr(x[1]-x[2])+2*sqr(x[1])
End;

То пишем подпрограмму
Procedure gradF(var

x,dF:mas,n:byte,h:real);
Begin
df[1]:=(F(x[1]+h,x[2])-F(x[1]-h,x[2]))/(2*h);
df[2]:=(F(x[1],x[2]+h)-F(x[1],x[2]-h))/(2*h);
End;

решения задачи Коши то метод шарика может конкурировать с методами

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

и начальный шаг h одномерного спуска .
2.

Вычисляется


3.Выбирается направление

x1

x2

d

g0

найти zm доставляющее


5. Перейти в новую точку

x1
x2
d
g0



zm

оно выполнено, то минимум достигнут в текущей точке, иначе повторяем

с п.2

x1

x2

d

g0

g1

спуска по градиенту может сильно замедляться
Т.е. он имеет точно те

же недостатки что и метод спуска по координатам.
Ломанная траектория идет по перпендикулярам к предыдушей

x,dF:mas,n:byte,h:real);
Begin
df[1]:=(F(x[1]+h,x[2])-F(x[1]-h,x[2]))/(2*h);
df[2]:=(F(x[1],x[2]+h)-F(x[1],x[2]-h))/(2*h);
End;
Var d:mas;

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

n do D[i]:=-dF[i];
zm:=MPP(0,h,h/5);
x0:=x;
dl:=zm;
for i:=1 to n

do
dl:=dl+abs(dF[i]);
end;
Until dlfm:=F(x0);
End;

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

G если


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

минимум

матрицей G в каждой точке x0 можно построить набор n

сопряженных (относительно ее матрицы) векторов, последовательный спуск по которым приведет точно в минимум
Вопрос в том, как их построить, если не знать G

и делаем спуск в точку х1
Вблизи точки х0 выбираем точку

х01
Из нее также делаем спуск в направлении d1 до точки х11
Вектор d2 проведенный через точки х1 х11 является сопряженным к d1

и начальный шаг h одномерного спуска , вычисляется.

Повторяем n раз:
2.

Делаем спуск zm

3. Переходим в новую точку

4. Вычисляем

5. Выбирается направление

6. Пересылаем
Конец повтора

Если zm<ε повторим с п.1