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

Метод Ньютона.

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

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

Такой выбор направления спуска гарантирует выполнение требования , при условии, что матрица Гессе положительно определена. Чтобы обеспечить выполнение требования даже в тех случаях, когда для каких либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соот-ветствующих значений k вычислить точку по методу градиентного спуска с выбором величины шага из условия
К методу Ньютона можно придти из следующих соображений.
Необходимым условием экстремума функции многих переменных f(x) в точке является равенство нулю ее градиента в этой точке:

Функция f(х) в окрестности точки может быть разложена в ряд Тейлора с точностью до членов второго порядка:

Направление определяется из необходимого условия экстремума первого порядка:
.
Имеем

При выполнении условия о положительной определенности матрицы получим:

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

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