Методы Переменной Метрики

алгоритм методов с переменной метрикой
Основные методы

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

производных. Их приходится вычислять на основе разделенных разностей, а это требует значительных затрат.


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

к минимуму. Как известно, система адаптивного управления имеет свойство накапливать

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

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

матрице Н, которая по мере накопления информации постепенно превращается в обратную матрицу Гессе


При этом матрица вторых производных на каждом шаге не пересчитывается.

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

день было предложено множество различных методов, которые мы рассмотрим ниже.
Следует так же отметить, что на сегодняшний день предложен метод сходящийся за меньшее число итераций, чем метод Ньютона, хотя и использующий только матрицу вторых производных Гессе.
[Хромова Л.Н. Об одном методе минимизации с кубической скоростью сходимости. – Вестник Моск. ун-та Сер. Вычислит. Матем. и кибернетика, 1980, №3].
Поэтому возможно построение методов с переменной метрикой имеющих кубическую скорость сходимости, т.е. значительно более быстрых, чем метод Ньютона.

широкий класс эффективных градиентных методов, в которых направление очередного спуска

вычисляется по формуле






Н - положительно определенная симметричная матрица

рассчитываемая по результатам предыдущих спусков таким образом, чтобы обеспечить сходимость

спуск в направлении


делается пересчет корректирующей матрицы


Если

то производится вычисление нового направления спуска Нk+1=Нk+Аk+1;

Гессе не пересчитывается на каждом спуске, и в результате вычислительные

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

параболы. При этом, для уменьшения вычислительных затрат, рекомендуется делать только

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

метрикой, на основе выше сформулированных Давидоном принципов предложен Флетчером и

Пауэллом (1963).
Матрица Ак рассчитывается по формулам

to n do begin
v[i]:=zm*d[i];
u[i]:=g1[i]-g0[i]; //
vu:=vu+v[i]*u[i]
end;
uhu:=0; for i:=1 to n do

begin
uh:=0;
for j:=1 t n do
uh:=uh+u[j]*H[j,i]; // uhu:=uhu+uh*u[i]
end;

k:=1 to n do begin hu[i]:=hu[i]+H[i,k]*u[k];
uh[i]:=uh[i]+u[k]*H[k,i];

end
end;
for i:=1 to n do
for j:=1 to n do begin
Aij:=v[i]*v[j]/vu-hu[i]*uh[j]/uhu;
H[i,j]:=H[i,j]+Aij;
end
end;

задающее в зависимости от выбираемой произвольной симметричной матрицы М семейство

методов с переменной метрикой




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

ДФП

Метод менее громоздок

метод Розенброка и метод Нелдера Мида
Если же функция гладкая, т.е.

имеет непрерывные производные, то наиболее эффективным себя зарекомендовали метод Гольдфарба и метод ДФП (они в 2-6 раз эффективнее по быстродействию чем метод Розенброка).
На самом деле многое зависит от вида конкретной оптимизируемой функции. Особенно если количество оптимизируемых переменных больше 4-5 нужно иметь в запасе несколько разнообразных методов, а процесс оптимизации строить на основе интерактивных программ.