Методы Переменной Метрики - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы Переменной Метрики. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Тема 16 Методы минимизации с переменной метрикой Исходные предпосылки Общий алгоритм методов с переменной метрикой Основные методы

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

Метод ДАВИДОНА-ФЛЕТЧЕРА-ПАУЭЛЛА Один из первых и эффективных методов с переменной метрикой, на основе выше сформулированных Давидоном принципов предложен Флетчером и Пауэллом (1963). Матрица Ак рассчитывается по формулам

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

Программная реализация вычисления матриц 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

Описание слайда:

Программная реализация (продолжение) 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

Описание слайда:

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

Слайд 18

Описание слайда:

Метод ГОЛЬДФАРБА (1970)

Слайд 19

Описание слайда:

Метод ПРОЕКТИВНОГО ГРАДИЕНТА

Слайд 20

Описание слайда:

Метод МАК-КОРМИКА 1

Слайд 21

Описание слайда:

Метод МАК-КОРМИКА 2

Слайд 22

Описание слайда:

Метод ГРИНСТАДТА

Слайд 23

Описание слайда:

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