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

Сентябрь 2, 2022

Главная
Алгебра
Методы Переменной Метрики

Содержание

2. 09/02/2023 Недостатки и достоинства метода Ньютона Описанный в предыдущей лекции метод Ньютона на каждой итерации требует
3. 09/02/2023 Основные предпосылки С другой стороны привлекательной является идея адаптивного управления спуском к минимуму. Как известно,
4. 09/02/2023 Идея алгоритмов В рассмотренном ниже классе методов с переменной метрикой реализована идея адаптивного управления. Информация
5. 09/02/2023 Многообразие и перспективность алгоритмов Процесс обработки и накопления информации, получаемой на каждой новой итерации можно
6. 09/02/2023 Общий алгоритм методов с переменной метрикой Методами с переменной метрикой называется широкий класс эффективных градиентных
7. 09/02/2023 Сравните с методом Ньютона корректирующая матрица, рассчитываемая по результатам предыдущих спусков таким образом, чтобы обеспечить
8. 09/02/2023 Последовательность вычислений На 1-м шаге следует положить Н0=Е Делаем очередной одномерный спуск в направлении делается
9. 09/02/2023
10. 09/02/2023 Общая характеристика методов В результате методы получаются асимптотически второго порядка. Матрица Гессе не пересчитывается на
11. 09/02/2023 Рекомендация Обычно при реализации одномерного спуска используется метод кубической или квадратичной параболы. При этом, для
12. 09/02/2023 Метод ДАВИДОНА-ФЛЕТЧЕРА-ПАУЭЛЛА Один из первых и эффективных методов с переменной метрикой, на основе выше сформулированных
13. 09/02/2023 Поясним вычисление матрицы А на примере двух переменных Получается матрица Получается число
14. 09/02/2023 Вычисление матрицы А на примере двух переменных
15. 09/02/2023 Программная реализация вычисления матриц H+A Procedure PREOBR; var hu,uh,u,v: array[l..n] of real; vu,uhu,uh:real; begin vu:=0;for
16. 09/02/2023 Программная реализация (продолжение) for i:=1 to n do begin hu[i]:=0; uh[i]:=o; for k:=1 to n
17. 09/02/2023 Общий вид матрицы А В 1979г. Гринсдадт Дж. предложил общее выражение, задающее в зависимости от
18. 09/02/2023 Метод ГОЛЬДФАРБА (1970) Он более устойчив к ошибкам вычислений, чем ДФП
19. 09/02/2023 Метод ПРОЕКТИВНОГО ГРАДИЕНТА После N шагов матрица должна восстанавливаться: Н=Е. Метод менее громоздок
20. 09/02/2023 Метод МАК-КОРМИКА 1
21. 09/02/2023 Метод МАК-КОРМИКА 2
22. 09/02/2023 Метод ГРИНСТАДТА
23. 09/02/2023 Сравнение методов по эффективности Среди методов нулевого порядка наибольшей эффективностью обладают метод Розенброка и метод
25. Скачать презентацию

Слайд 2

09/02/2023
Недостатки и достоинства метода Ньютона
Описанный в предыдущей лекции метод Ньютона на

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

Слайд 3

09/02/2023
Основные предпосылки
С другой стороны привлекательной является идея адаптивного управления спуском к

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

Слайд 4

09/02/2023
Идея алгоритмов
В рассмотренном ниже классе методов с переменной метрикой реализована идея

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

Слайд 5

09/02/2023
Многообразие и перспективность алгоритмов
Процесс обработки и накопления информации, получаемой на каждой

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

Слайд 6

09/02/2023
Общий алгоритм методов с переменной метрикой
Методами с переменной метрикой называется широкий

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

Слайд 7

09/02/2023
Сравните с методом Ньютона
корректирующая матрица, рассчитываемая по результатам предыдущих спусков

таким образом, чтобы обеспечить сходимость

Слайд 8

09/02/2023
Последовательность вычислений
На 1-м шаге следует положить Н0=Е
Делаем очередной одномерный спуск

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

Слайд 9

09/02/2023

Слайд 10

09/02/2023
Общая характеристика методов
В результате методы получаются асимптотически второго порядка.
Матрица Гессе

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

Слайд 11

09/02/2023
Рекомендация
Обычно при реализации одномерного спуска используется метод кубической или квадратичной параболы.

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

Слайд 12

09/02/2023
Метод ДАВИДОНА-ФЛЕТЧЕРА-ПАУЭЛЛА
Один из первых и эффективных методов с переменной метрикой,

на основе выше сформулированных Давидоном принципов предложен Флетчером и Пауэллом (1963).
Матрица Ак рассчитывается по формулам

Слайд 13

09/02/2023
Поясним вычисление матрицы А на примере двух переменных
Получается матрица
Получается число

Слайд 14

09/02/2023
Вычисление матрицы А на примере двух переменных

Слайд 15

09/02/2023
Программная реализация вычисления матриц H+A
Procedure PREOBR;
var
hu,uh,u,v: array[l..n] of real;
vu,uhu,uh:real;
begin
vu:=0;for i:=1 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;

Слайд 16

09/02/2023
Программная реализация (продолжение)
for i:=1 to n do begin
hu[i]:=0; uh[i]:=o;
for 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;

Слайд 17

09/02/2023
Общий вид матрицы А
В 1979г. Гринсдадт Дж. предложил общее выражение, задающее

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

Слайд 18

09/02/2023
Метод ГОЛЬДФАРБА (1970)
Он более устойчив к ошибкам вычислений, чем ДФП

Слайд 19

09/02/2023
Метод ПРОЕКТИВНОГО ГРАДИЕНТА
После N шагов матрица должна восстанавливаться: Н=Е.
Метод

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

Слайд 20

09/02/2023
Метод МАК-КОРМИКА 1

Слайд 21

09/02/2023
Метод МАК-КОРМИКА 2

Слайд 22

09/02/2023
Метод ГРИНСТАДТА

Слайд 23

09/02/2023
Сравнение методов по эффективности
Среди методов нулевого порядка наибольшей эффективностью обладают метод

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

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

Содержание

09/02/2023Недостатки и достоинства метода НьютонаОписанный в предыдущей лекции метод Ньютона на

09/02/2023Основные предпосылкиС другой стороны привлекательной является идея адаптивного управления спуском к

09/02/2023Идея алгоритмовВ рассмотренном ниже классе методов с переменной метрикой реализована идея

09/02/2023Многообразие и перспективность алгоритмовПроцесс обработки и накопления информации, получаемой на каждой

09/02/2023Общий алгоритм методов с переменной метрикойМетодами с переменной метрикой называется широкий

09/02/2023Сравните с методом Ньютона корректирующая матрица, рассчитываемая по результатам предыдущих спусков

09/02/2023Последовательность вычисленийНа 1-м шаге следует положить Н0=Е Делаем очередной одномерный спуск

09/02/2023

09/02/2023Общая характеристика методовВ результате методы получаются асимптотически второго порядка. Матрица Гессе

09/02/2023РекомендацияОбычно при реализации одномерного спуска используется метод кубической или квадратичной параболы.

09/02/2023Метод ДАВИДОНА-ФЛЕТЧЕРА-ПАУЭЛЛА Один из первых и эффективных методов с переменной метрикой,

09/02/2023Поясним вычисление матрицы А на примере двух переменныхПолучается матрицаПолучается число

09/02/2023Вычисление матрицы А на примере двух переменных

09/02/2023Программная реализация вычисления матриц H+AProcedure PREOBR;varhu,uh,u,v: array[l..n] of real;vu,uhu,uh:real;beginvu:=0;for i:=1 to

09/02/2023Программная реализация (продолжение)for i:=1 to n do begin hu[i]:=0; uh[i]:=o; for k:=1

09/02/2023Общий вид матрицы АВ 1979г. Гринсдадт Дж. предложил общее выражение, задающее

09/02/2023Метод ГОЛЬДФАРБА (1970) Он более устойчив к ошибкам вычислений, чем ДФП

09/02/2023Метод ПРОЕКТИВНОГО ГРАДИЕНТА После N шагов матрица должна восстанавливаться: Н=Е. Метод

09/02/2023Метод МАК-КОРМИКА 1

09/02/2023Метод МАК-КОРМИКА 2

09/02/2023Метод ГРИНСТАДТА

09/02/2023Сравнение методов по эффективностиСреди методов нулевого порядка наибольшей эффективностью обладают метод

Похожие презентации