Методы Оптимизации Систем Автоматизированного Проектирования

Модификации метода Ньютона. Метод Ньютона-Рафсона.

Стратегия поиска.Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения . Если находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Для ослабления влияния начальной точки на сходимость метода используется метод Ньютона-Рафсона. Стратегия метода Ньютона-Рафсона состоит в построении последовательности точек , k=0, 1, ... таких, что , k=0, 1, ...
Точки последовательности вычисляются по правилу:

где – задается пользователем, а направление спуска вычисляется по формуле:

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

и матрицу Гессе H(x)
Положить k=0.
Основной этап
Шаг 1. Вычислить
Шаг 2. Проверить выполнение критерия останова
а) если критерий выполнен, расчет окончен,
б) если критерий не выполнен, то перейти к шагу 3.
Шаг 3. Вычислить матрицу Гессе
Шаг 4. Найти обратную матрицу
Шаг 5. Проверить положительную определенность матрицы

Шаг 6. Найти
Шаг 7. Найти величину шага из условия
Шаг 8. Вычислить
Шаг 9. Положить k= k +1 и перейти к шагу 1

Сходимость метода.

Теорема 5. Пусть функция f(x) дважды непрерывно дифференцируемая сильно выпуклая функция на , а ее матрица Гессе H(X) удовлетворяет условию Липшица

Стр.: ..., 2, 3