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

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

.

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

,

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

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

,

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

.

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

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

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

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

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

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

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

,

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

,

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

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

, или

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

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

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

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

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

5. Вычислить

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

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

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

4.3.6.Численная аппроксимация градиентов

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

Для получения числовых оценок элементов градиента используют аппроксимации градиента:

а) конечными разностями

,

б) центральными конечными разностями

,

где – шаг аппроксимируемой производной; – вектор, имеющий единицу в i-й позиции.

Аппроксимация элементов матрицы Гессе имеет вид

.

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

13