Примечание 2

Матрицей Гессе называют матрицу вторых частных производных целевой функции по управляемым параметрам.

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

Пример 1

Поиск экстремума выполняют в соответствии с формулой

(2)

Направление поиска на очередном шаге связано с направлением поиска на предыдущем шаге соотношением

(3)

где — коэффициент. Кроме того, учитывают условие сопряженности

(4)

и линейную аппроксимацию в окрестностях точки

(5)

Поскольку шаг рассчитывается исходя из условия одномерной оптимизации, то, во-первых, справедливо соотношение

(6)

во-вторых, имеем

откуда получаем

(7)

Алгоритм поиска сводится к применению формулы (3), пока не будет выполнено условие окончания вычислений

Чтобы определить коэффициент , решают систему уравнений (2)-(7) путем подстановки в (4) величин из (3) и из (2):

или

откуда

и с учетом (6) и (7)

Следовательно,

(8)

На первом шаге поиска выбирают и находят точку . На втором шаге по формуле (8) рассчитывают , по формулам (3) и (2) определяют и и т.д.

Метод переменной метрики (иначе метод Девидона-Флетчера-Пауэлла) можно рассматривать как результат усовершенствования метода второго порядка — метода Ньютона.

Метод Ньютона основан на использовании необходимых условий безусловного экстремума целевой функции

(9)

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

(10)

Выражение (10) — это система линейных алгебраических уравнений. Ее корень есть очередное приближение к решению

Если процесс сходится, то решение достигается за малое число итераций, окончанием которых служит выполнение условия

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

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

Введем обозначения:

— единичная матрица. Начальное значение матрицы . Матрицу корректируют на каждом шаге, т.е.

где

Поэтому

Можно показать, что стремится к , — к при , где — размерность пространства управляемых параметров. Спустя шагов, нужно снова начинать с .