Обобщенный метод Ньютона

Идею метода рассмотрим на примере поиска минимума функции двух переменных F(x₁,x₂).

Квадратичная аппроксимация в виде (1) приобретает вид:

Неизвестные величины здесь - ∆Х₁, ∆Х₂. Будем определять минимум F_оп.

В точке экстремума градиент функции должен быть равен нулю:

(11)

Это система линейных уравнений относительно ∆Х₁, ∆Х₂. Запишем в другом виде:

(12)

Переносим свободные члены в правую часть:

(13)

Решаем эту систему уравнений, находим ∆Х₁, ∆Х₂ и далее следующие при-ближения неизвестных.

Геометрическая интерпретация:

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

В обобщенном методе Ньютона функция в очередной точке апроксимируется элипсоидом и шаг выполняется к центру этого элипса. Решением системы уравнений (13) отыскивается вектор , приводящий к центру элипса. Выполняется квадратичная апроксимация. При этом обеспечивается наилучшая сходимость.

Рассмотрим связь метода оптимизации с методом Ньютона для решения систем нелинейных уравнений.

В точке экстремума функции длина вектора-градиента равна нулю. Составляющие вектора градиента – это производные целевой функции по управляющим параметрам. Значит в точке экстремума функции длина составляющих вектора-градиента также равна нулю:

F= (14)

Обозначим эти производные в (14) как Ψ_і:

F= (15)

Каждая производная представляет собой аналитическое выражение, которое обозначено через Ψ. Получаем нелинейную систему уравнений (15), решив которую мы найдем значения управляющих параметров, соответствующих минимуму целевой функции. Решать ее будем методом Ньютона-Рафсона:

(16)

Первые производные от Ψ являются вторыми производными от целевой функции F и они образуют матрицу Гессе:

Тогда (16) примет вид:

(17)

Рекурентное выражение обобщенного уравнения Ньютона-Рафсона позво-ляет определить координаты точки на очередном приближении. Матрица Якоби, при решении (15) тождественно равна матрице Гессе. Обобщенный метод Ньютона обеспечивает резкое сокращение шагов оптимизации по сравнению с методами 1-го порядка.

Пример:

Найти минимум функции 2-х переменных

Используем обобщенный метод Ньютона.

(П2)

Обобщенный метод Ньютона соответствует решению системы уравнений (п2) методом Ньютона-Рафсона:

(П5)

Определим элементы матрицы Гессе:

(П3)

Дифференцируем Ψ1, Ψ2 по Х₁ и Х₂:

(П4)

Зададим начальные приближения неизвестных:

Определим матрицу Гессе в точке начального приближения:

Определим вектор градиент

(п5)

Решаем эту систему уравнений и находим

Определим очередные приближения

Определим значение целевой функции в новой точке:

Выполняем второй шаг при нових значениях управляющих параметров

Формируем систему вида(п5), решаем ее и т.д..