ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Модифицированный метод Ньютона

1 2 34

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

, .

Коэффициент (параметр шага) выбирают на каждом шаге так, чтобы , (как в методе Коши), это гарантирует, что .

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

Метод Марквардта

Метод Марквардта (1963 г.) является комбинацией методов Коши и Ньютона, сочетает положительные свойства обоих методов. Итерации выполняются по формуле

Направление поиска на каждой итерации определяется как

где – матрица Гессе; – единичная матрица.

В начале поиска значение >>1 (например, ), тогда

и направление поиска:

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

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

Недостаток алгоритма: необходимость вычисления матрицы Гессе и обращения матрицы .

Метод хорошо работает в задачах с целевой функцией вида

(например, задачи регрессионного анализа).

Квазиньютоновские методы

Квазиньютоновские методы оптимизации обладают положительными чертами метода Ньютона, но используют только первые производные. Все квазиньютоновские методы используют итерационную процедуру (4.1), в которой направление поиска задается в виде

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

где – корректирующая матрица, и в пределе становится равной обратному гессиану.

Метод Дэвидона-Флетчера-Пауэлла (ДФП). Один из наиболее широко применяемых градиентных методов – метод Дэвидона-Флетчера-Пауэлла (ДФП). Используются следующие обозначения

, или

Упрощенно алгоритм можно представить такими шагами

1. Задать начальную точку и начальную матрицу (обычно единичная матрица)

2. Минимизировать

3. Вычислить .

4. Обновить метрику

5. Вычислить

6. Если не выполнены условия окончания поиска, то присвоить , перейти на 2.

7. Конец алгоритма.

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

1 2 34