Положим, что функция

(

) всюду дважды дифференцируема в

-мерном евклидовом пространстве

.
 | (1) |
Обоснование метода оптимизации Ньютона.
Рассмотрим первые три члена разложения функции

(

) в ряд Тейлора в окрестности точки

:
 | (2) |
Здесь

(

) -
матрица Гессе функции

(

). Из (2) следует, что градиент функции

(

) равен
 | (3) |
Если
матрица Гессе 
(

) положительно определена, то функция

(

) достигает минимума в точке, в которой градиент этой функции равен нулевому вектору.
Таким образом, в точке

минимума функции

(

) справедливо равенство
 | (4) |
где

-

-мерный вектор нулей. Отсюда получаем итерационную формулу
 | (5) |
для отыскания очередного приближения к точке минимума функции

(

). Здесь
 | (6) |
Выражение (5) представляет собой итерационную формулу решения системы уравнений (4) широко известным методом касательных (методом Ньютона) – см. параграф 4.8. Этим фактом объясняется название рассматриваемого метода оптимизации.
Найдем скалярное произведение градиента функции

(

) в точке

и вектора

:
 | (7) |
Рис. 1. К обоснованию метода многомерной оптимизации Ньютона.
Отметим трудности, которые могут возникать при использовании итерационной формулы (5):
- Если размерность пространства
велика, то обращение на каждой итерации матрицы Гессе
(
) может потребовать значительных вычислительных ресурсов;
- Значение минимизируемой функции
(
) в точке
может превышать значение функции в предыдущей точке
вследствие того, что направление
ведет к уменьшению
(
), но величина шага слишком велика;
- Направление спуска, определяемое вектором
, ведет к убыванию целевой функции только при положительной определенности матрицы Гессе
(
). Это приводит к тому, что на каждой итерации необходимы вычислительные затраты на проверку обусловленности этой матрицы. Указанная матрица может быть плохо обусловленной. Более того, указанная матрица может быть вырожденной и, поэтому, не иметь обратной матрицы.
Вследствие этих трудностей итерационная формула (5) в «чистом» виде не используется в вычислительной практике.
Для того чтобы избежать обращения
матрицы Гессе, на практике вектор

находят обычно из следующей системы линейных алгебраических уравнений (СЛАУ), вытекающей из равенства (6):
 | (8) |
СЛАУ (8) может быть решена различными численными методами (например, прямыми методами, итерационными методами).
Величина шага в направлении

, которая приводит к убыванию функции

(

), может быть обеспечена путем добавления в итерационную формулу (5) коэффициента

, т.е. путем использования вместо формулы (5) итерационной формулы
 | (9) |
где коэффициент

выбирают тем или иным способом так, чтобы обеспечить условие

.
Для того, чтобы направление спуска независимо от определенности
матрицы Гессе 
(

) вело у убыванию функции

(

), в качестве вектора

можно использовать вектор
 | (10) |
где

-

-единичная матрица, а

- параметр, выбираемый так, чтобы матрица

являлась положительно определенной.
Схема метода оптимизации Ньютона.
Рассмотрим схему одной из модификаций
метода оптимизации Ньютона, в которой используется итерационная формула (9) и вектор

находят путем решения на каждой итерации СЛАУ (8).
- Задаем начальную точку
, начальную величину шага
и коэффициент дробления шага
Полагаем счетчик числа итераций
=0.
- Вычисляем в точке
вектор градиента
(
) и матрицу Гессе
(
).
- Решаем СЛАУ (8) и находим вектор
.
- По формуле (9) вычисляем компоненты вектора
.
- Вычисляем величину
- значение функции
(
) в точке
.
- Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем
, и завершаем итерации. Иначе – переходим к следующему пункту.
- Если
<
, то полагаем
=
+1 и переходим к п.2. Иначе – фиксированное число раз полагаем
и переходим к пункту 4
или условие
где

- константа, определяющая требуемую точность решения по градиенту функции

(

).