Разделы презентаций


Численные методы оптимизации_11.pptx

Содержание

Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего спуска и другие методы сопряженных градиентов в различных задачах. Изначально считалось, что LMA – это

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

Слайд 1ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Константин Ловецкий
Ноябрь 2011
Кафедра систем телекоммуникаций
Оптимизация. Обращение матриц.

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИКонстантин ЛовецкийНоябрь 2011Кафедра систем телекоммуникацийОптимизация.  Обращение матриц.

Слайд 2Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации.

Он превосходит по производительности метод наискорейшего спуска и другие методы

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

Метод Левенберга—Марквардта

08.11.2011



Алгоритм Левенберга—Марквардта (Levenberg-Marquardt Algorithm, LMA) является наиболее распространенным алгоритмом оптимизации. Он превосходит по производительности метод наискорейшего спуска

Слайд 3Таким образом, алгоритм Левенберга представляется в
виде последовательности действий:

1. Вычислить

параметр на очередной итерации по правилу
2. Оценить невязку в

новом векторе параметров.
3. Если в результате вычисления параметра невязка увеличилась, вернуться на шаг назад (т.е. восстановить прежние значения весов) и увеличить в 10 раз. Затем повторить выполнение, начиная с шага 1.
4. Если в результате вычисления параметра невязка уменьшилась, принять текущий шаг (т.е. оставить новые значения весов) и уменьшить в 10 раз.

Метод Левенберга—Марквардта

08.11.2011



Таким образом, алгоритм Левенберга представляется ввиде последовательности действий: 1. Вычислить параметр на очередной итерации по правилу

Слайд 4Формула Шермана-Моррисона-Вудбери.
08.11.2011
Обращение матриц

Пусть A – невырожденная nxn матрица и пусть

U и V – mxn матрицы, причем m≤n. Тогда










обратима тогда

и только тогда, когда обратима

и

Доказательство.

Формула Шермана-Моррисона-Вудбери.08.11.2011Обращение матрицПусть A – невырожденная nxn матрица и пусть U и V – mxn матрицы, причем

Слайд 5Формула Шермана-Моррисона-Вудбери
08.11.2011
Рассмотрим важный специальный случай, когда m=1; U и V

являются в этом случае векторами - столбцами размерности n (u

и v) и формула Шермана-Моррисона-Вудбери принимает вид









There are different versions. The first one goes directly back to Woodbury:
(1)
There is also a more general form, which can be expressed in two different ways.
The first one is easier to be understood, while the second one is more general.
(2)
The ladder results also in a special version, which I think is very nice.
(3)

REFERENCES:
Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins, p. 50, 1996.

Формула Шермана-Моррисона-Вудбери08.11.2011Рассмотрим важный специальный случай, когда m=1; U и V являются в этом случае векторами - столбцами

Слайд 6Формула Шермана-Моррисона-Вудбери
08.11.2011

Обратим матрицу







используя формулу Шермана-Моррисона-Вудбери:

Формула Шермана-Моррисона-Вудбери08.11.2011Обратим матрицуиспользуя формулу Шермана-Моррисона-Вудбери:

Слайд 7Далее используем и второй столбец для


определения

, где ,

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

тогда

08.11.2011



Формула Шермана-Моррисона-Вудбери


Далее используем   и второй столбец   для определения

Слайд 8Пример. Найдем обратную к матрице
Формула Шермана-Моррисона-Вудбери
08.11.2011







Пусть

тогда
Пример. Найдем обратную к матрицеФормула Шермана-Моррисона-Вудбери08.11.2011Пусть

Слайд 908.11.2011
Формула Шермана-Моррисона-Вудбери





08.11.2011Формула Шермана-Моррисона-Вудбери

Слайд 10Формула Шермана-Моррисона-Вудбери
08.11.2011





Формула Шермана-Моррисона-Вудбери08.11.2011

Слайд 11This identity is useful in certain numerical computations where A−1

has already been computed and it is desired to compute

(A + UCV)−1. With the inverse of A available, it is only necessary to find the inverse of C−1 + VA−1U in order to obtain the result using the right-hand side of the identity. If C has a much smaller dimension than A, this is more efficient than inverting A + UCV directly.

This is applied, e.g., in the Kalman filter and recursive least squares methods, to replace the parametric solution, requiring inversion of a state vector sized matrix, with a condition equations based solution.

In case of the Kalman filter this matrix has the dimensions of the vector of observations, i.e., as small as 1 in case only one new observation is processed at a time. This significantly speeds up the often real time calculations of the filter.

Формула Шермана-Моррисона-Вудбери

08.11.2011




This identity is useful in certain numerical computations where A−1 has already been computed and it is

Слайд 12Ключевой момент был замечен Марквардтом. Он заменил
единичную матрицу в формуле

на диагональ гессиана, получив
таким образом следующее правило:



Matrix inversion

plays a significant role in computer graphics, particularly in 3D graphics rendering and 3D simulations. Examples include screen-to-world ray casting, world-to-subspace-to-world object transformations, and physical simulations.


Метод Левенберга—Марквардта

08.11.2011



Ключевой момент был замечен Марквардтом. Он заменилединичную матрицу в формуле на диагональ гессиана, получив таким образом следующее

Слайд 13Конструирование ящика.
Задача оптимизации часто заключается в отыскании
конструктивных параметров, при которых

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

поверхности которого минимальна при
заданном объеме сосуда

Примеры задач

08.11.2011

Такая конструкция минимизирует, например, потери тепла.
Ящик открытый (без крышки).

Конструирование ящика.Задача оптимизации часто заключается в отысканииконструктивных параметров, при которых целевая функция достигает минимума.Рассмотрим задачу создания ящика

Слайд 14Конструирование (открытого) ящика.
Объем и площадь поверхности вычисляются по формулам


и задача

может быть сформулирована так:
Минимизировать


при условии, что
Это задача оптимизации с

тремя искомыми параметрами и
ограничении – равенстве.
Однако задачу можно слегка упростить, заметив, что
условие ограничения объема позволяет исключить один
параметр:

Примеры задач

08.11.2011

Конструирование (открытого) ящика.Объем и площадь поверхности вычисляются по формулами задача может быть сформулирована так:		Минимизировать		при условии, что Это

Слайд 15Конструирование (открытого) ящика.
Теперь задача может быть переформулирована в виде задачи

без
ограничений:
Минимизировать


Это задача безусловной минимизации с двумя искомыми параметрами.

Оптимальное

решение исходной задачи может быть получено и в
том, и в другом случае.

Правда, надо отметить, что в исходной постановке задачи мы не
учли тот факт, что отрицательные искомые параметры не имеют
практического смысла.

Примеры задач

08.11.2011

Конструирование (открытого) ящика.Теперь задача может быть переформулирована в виде задачи без ограничений:		Минимизировать	Это задача безусловной минимизации с двумя

Слайд 16Конструирование (открытого) ящика.
Формулировка задачи должна содержать условие
положительности переменных, что

приводит к введению
ограничений – неравенств.
Минимизировать



или
Примеры задач
08.11.2011

Конструирование (открытого) ящика.Формулировка задачи должна содержать условие положительности переменных, что приводит к введению ограничений – неравенств.Минимизировать илиПримеры

Слайд 17Конструирование (открытого) ящика.
В том случае, когда формулировка кажется сложной, можно

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

с квадратным дном,
то есть добавить условие .
Объем и площадь поверхности вычисляются по формулам


Задача минимизации (функции одной переменной) теперь
выглядит так:
Минимизировать



Примеры задач

08.11.2011

Конструирование (открытого) ящика.В том случае, когда формулировка кажется сложной, можно пойтина некоторое упрощение исходных условий. Предположим, чтоможно

Слайд 18Площадь как функция от при заданном

объеме .


Минимум достигается при

08.11.2011

Примеры задач

Площадь как функция от     при заданном объеме

Слайд 19M. Bartholomew-Biggs, Nonlinear Optimization with Engineering Applications, Springer Science+Business Media,

LLC 2008
Alfio Quarteroni, Riccardo Sacco, Fausto Saleri. Numerical mathematics. 2000,

Springer-Verlag New York, Inc.

Литература

08.11.2011

M. Bartholomew-Biggs, Nonlinear Optimization with Engineering Applications, Springer Science+Business Media, LLC 2008Alfio Quarteroni, Riccardo Sacco, Fausto Saleri.

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика