Как найти гессиан функции

Как найти гессиан функции

Гессиан функции — симметрическая квадратичная форма[1], описывающая поведение функции во втором порядке.

Для функции f, дважды дифференцируемой в точке xin mathbb{R} ^{n}

H(x)=sum _{{i=1}}^{n}sum _{{j=1}}^{n}a_{{ij}}x_{i}x_{j}

или

H(z)=sum _{{i=1}}^{n}sum _{{j=1}}^{n}a_{{ij}}z_{i}overline {z}_{j}

где a_{{ij}}=partial ^{2}f/partial x_{i}partial x_{j} (или a_{{ij}}=partial ^{2}f/partial z_{i}partial overline {z}_{j}) и функция f задана на n-мерном вещественном пространстве mathbb {R} ^{n} (или комплексном пространстве mathbb{C}^n) с координатами x_{1},ldots ,x_{n} (или z_{1},ldots ,z_{n}). В обоих случаях гессиан — квадратичная форма, заданная на касательном пространстве, не меняющаяся при линейных преобразованиях переменных. Гессианом также часто называют и определитель матрицы {displaystyle (a_{ij}),} см. ниже.

Матрица Гессе[править | править код]

Матрица этой квадратичной формы образована вторыми частными производными функции. Если все производные существуют, то

H(f)={begin{bmatrix}{frac {partial ^{2}f}{partial x_{1}^{2}}}&{frac {partial ^{2}f}{partial x_{1},partial x_{2}}}&cdots &{frac {partial ^{2}f}{partial x_{1},partial x_{n}}}\\{frac {partial ^{2}f}{partial x_{2},partial x_{1}}}&{frac {partial ^{2}f}{partial x_{2}^{2}}}&cdots &{frac {partial ^{2}f}{partial x_{2},partial x_{n}}}\\vdots &vdots &ddots &vdots \\{frac {partial ^{2}f}{partial x_{n},partial x_{1}}}&{frac {partial ^{2}f}{partial x_{n},partial x_{2}}}&cdots &{frac {partial ^{2}f}{partial x_{n}^{2}}}end{bmatrix}}

Определитель этой матрицы называется определителем Гессе, или просто гессианом[источник не указан 3813 дней].

Матрицы Гессе используются в задачах оптимизации методом Ньютона.
Полное вычисление матрицы Гессе может быть затруднительно, поэтому были разработаны квазиньютоновские алгоритмы, основанные на приближённых выражениях для матрицы Гессе. Наиболее известный из них — алгоритм Бройдена — Флетчера — Гольдфарба — Шанно.

Симметрия матрицы Гессе[править | править код]

Смешанные производные функции f — это элементы матрицы Гессе, стоящие не на главной диагонали. Если они непрерывны, то порядок дифференцирования не важен:

{frac {partial }{partial x_{i}}}left({frac {partial f}{partial x_{j}}}right)={frac {partial }{partial x_{j}}}left({frac {partial f}{partial x_{i}}}right)

Это можно также записать как

f_{{x_{i}x_{j}}}=f_{{x_{j}x_{i}}},quad forall i,jin {1,ldots ,n}.

В этом случае матрица Гессе симметрична.

Критические точки функции[править | править код]

Если градиент f (её векторная производная) равен нулю в некоторой точке x_{0}, то эта точка называется критической. Достаточным условием существования экстремума в этой точке является знакоопределённость гессиана f (понимаемого в данном случае как квадратичная форма), а именно:

Вариации и обобщения[править | править код]

Вектор-функции[править | править код]

Если f — вектор-функция, то есть

f=(f_{1},f_{2},dots ,f_{n}),

то её вторые частные производные образуют не матрицу, а тензор ранга 3, который можно рассматривать как массив из n матриц Гессе:

{displaystyle H(f)=left(H(f_{1}),ldots ,H(f_{n})right).}

При n = 1 данный тензор вырождается в обычную матрицу Гессе.

Окаймлённый гессиан[править | править код]

При решении задачи нахождения условного экстремума функции {displaystyle f:mathbb {R} ^{n}rightarrow mathbb {R} } с ограничениями

{displaystyle left{{begin{array}{c}g_{1}(x)=0,\vdots \g_{m}(x)=0,end{array}}right.}

где x in mathbb{R}^n, m<n, для проверки достаточных условий экстремума можно использовать так называемый окаймлённый гессиан функции Лагранжа {displaystyle L(x,lambda )}, который будет иметь вид[2]

{displaystyle left({begin{array}{cc}{dfrac {partial ^{2}L}{partial x^{2}}}&{dfrac {partial ^{2}L}{partial xpartial lambda }}\left({dfrac {partial ^{2}L}{partial xpartial lambda }}right)^{mathrm {T} }&{dfrac {partial ^{2}L}{partial lambda ^{2}}}end{array}}right)=left({begin{array}{cccccc}{dfrac {partial ^{2}L}{partial x_{1}^{2}}}&ldots &{dfrac {partial ^{2}L}{partial x_{1}partial x_{n}}}&{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{1}}}\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial ^{2}L}{partial x_{n}partial x_{1}}}&ldots &{dfrac {partial ^{2}L}{partial x_{n}^{2}}}&{dfrac {partial g_{1}}{partial x_{n}}}&ldots &{dfrac {partial g_{m}}{partial x_{n}}}\{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{1}}{partial x_{n}}}&0&ldots &0\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial g_{m}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{n}}}&0&ldots &0end{array}}right).}

Проверка достаточных условий экстремума заключается в вычислении знаков детерминантов определённого набора подматриц окаймлённого гессиана. Именно, если существуют {displaystyle x^{*}in mathbb {R} ^{n}} и {displaystyle lambda ^{*}in mathbb {R} ^{m}} такие, что {displaystyle nabla L(x^{*},lambda ^{*})=0} и

{displaystyle (-1)^{m}{mbox{det}}left({begin{array}{cccccc}{dfrac {partial ^{2}L}{partial x_{1}^{2}}}&ldots &{dfrac {partial ^{2}L}{partial x_{1}partial x_{p}}}&{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{1}}}\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial ^{2}L}{partial x_{p}partial x_{1}}}&ldots &{dfrac {partial ^{2}L}{partial x_{p}^{2}}}&{dfrac {partial g_{1}}{partial x_{p}}}&ldots &{dfrac {partial g_{m}}{partial x_{p}}}\{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{1}}{partial x_{p}}}&0&ldots &0\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial g_{m}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{p}}}&0&ldots &0end{array}}right)>0}

для {displaystyle p=m+1,ldots ,n}, то в точке x^{*} функция f имеет строгий условный минимум. Если же

{displaystyle (-1)^{p}{mbox{det}}left({begin{array}{cccccc}{dfrac {partial ^{2}L}{partial x_{1}^{2}}}&ldots &{dfrac {partial ^{2}L}{partial x_{1}partial x_{p}}}&{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{1}}}\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial ^{2}L}{partial x_{p}partial x_{1}}}&ldots &{dfrac {partial ^{2}L}{partial x_{p}^{2}}}&{dfrac {partial g_{1}}{partial x_{p}}}&ldots &{dfrac {partial g_{m}}{partial x_{p}}}\{dfrac {partial g_{1}}{partial x_{1}}}&ldots &{dfrac {partial g_{1}}{partial x_{p}}}&0&ldots &0\vdots &ddots &vdots &vdots &ddots &vdots \{dfrac {partial g_{m}}{partial x_{1}}}&ldots &{dfrac {partial g_{m}}{partial x_{p}}}&0&ldots &0end{array}}right)>0}

для {displaystyle p=m+1,ldots ,n}, то в точке x^{*} функция f имеет строгий условный максимум[3].

История[править | править код]

Понятие введено Людвигом Отто Гессе (1844), который использовал другое название. Термин «гессиан» был введён Джеймсом Джозефом Сильвестром.

См. также[править | править код]

  • Якобиан
  • Критическая точка (математика)
  • Лемма Морса
  • Критерий Сильвестра — критерий положительной или отрицательной определённости квадратной матрицы

Примечания[править | править код]

  1. ↑ Гессиан. Дата обращения: 2 апреля 2016. Архивировано 15 апреля 2016 года.
  2. ↑ Hallam, Arne Econ 500: Quantitative Methods in Economic Analysis I. Iowa State (7 октября 2004). Дата обращения: 14 апреля 2021. Архивировано 19 апреля 2021 года.
  3. ↑ Neudecker, Heinz. Matrix Differential Calculus with Applications in Statistics and Econometrics / Heinz Neudecker, Jan R. Magnus. — New York : John Wiley & Sons, 1988. — P. 136. — ISBN 978-0-471-91516-4.

Ссылки[править | править код]

  • Камынин Л.И. Математический анализ. Т. 1, 2. – 2001.
  • Кудрявцев Л.Д «Краткий курс математического анализа. Т.2. Дифференциальное и интегральное исчисления функций многих переменных. Гармонический анализ», ФИЗМАТЛИТ, 2002, — 424 с. — ISBN 5-9221-0185-4. Или любое другое издание.
  • Голубицкий М., Гийемин В. Устойчивые отображения и их особенности, — М.: Мир, 1977.
Источник

Гессиан функции — симметрическая квадратичная форма описывющая поведение функции во втором порядке.

Для функции {displaystyle f} дважды дифференцируемой в точке {displaystyle xin mathbb {R} ^{n}}

{displaystyle H(x)=sum _{i=1}^{n}sum _{j=1}^{n}a_{ij}x_{i}x_{j}}

или

{displaystyle H(z)=sum _{i=1}^{n}sum _{j=1}^{n}a_{ij}z_{i}{overline {z}}_{j}}

где {displaystyle a_{ij}=partial ^{2}f/partial x_{i}partial x_{j}} (или {displaystyle a_{ij}=partial ^{2}f/partial z_{i}partial {overline {z}}_{j}}) и {displaystyle f(p)} задана на {displaystyle n}-мерном действительном пространстве {displaystyle mathbf {R} ^{n}} (или комплексном пространстве {displaystyle mathbf {C} ^{n}}) с координатами {displaystyle x_{1},ldots ,x_{n}} (или {displaystyle z_{1},ldots ,z_{n}}).
В обоих случаях гессиан — квадратичная форма, заданная на касательном пространстве, не меняющаяся при линейных преобразованиях переменных.

Матрица Гессе

Матрица этой квадратичной формы образована вторыми частными производными функции. Если все производные существуют, то

{displaystyle H(f)={begin{bmatrix}{frac {partial ^{2}f}{partial x_{1}^{2}}}&{frac {partial ^{2}f}{partial x_{1},partial x_{2}}}&cdots &{frac {partial ^{2}f}{partial x_{1},partial x_{n}}}\\{frac {partial ^{2}f}{partial x_{2},partial x_{1}}}&{frac {partial ^{2}f}{partial x_{2}^{2}}}&cdots &{frac {partial ^{2}f}{partial x_{2},partial x_{n}}}\\vdots &vdots &ddots &vdots \\{frac {partial ^{2}f}{partial x_{n},partial x_{1}}}&{frac {partial ^{2}f}{partial x_{n},partial x_{2}}}&cdots &{frac {partial ^{2}f}{partial x_{n}^{2}}}end{bmatrix}}}

Определитель этой матрицы также называется Гессианом.

Матрицы Гессе используются в задачах оптимизации в методе Ньютона.
Полное вычисление матрицы Гессе может быть затруднительно, поэтому были разработаны квази-ньютоновы алгоритмы, основанные на приближенных выражениях для матрицы Гессе.
Наиболее известный такой алгоритм — BFGS.

Симметрия Гессиана

Смешанные производные функции f — это элементы матрицы Гессе, стоящие не на главной диагонали. Если они непрерывны, то порядок дифференцирования не важен (теорема Клеро), например

{displaystyle {frac {partial }{partial x}}left({frac {partial f}{partial y}}right)={frac {partial }{partial y}}left({frac {partial f}{partial x}}right)}

Это можно также записать как

{displaystyle f_{xy}=f_{yx},}

Формально, если вторые частные производные f — непрерывные в области D функции, то матрица Гессе симметрична на D.

Критические точки функции

Если градиент {displaystyle f} (её векторная производная) равен нулю в некоторой точке {displaystyle x}, то эта точка называется критической.
Достаточные условия существования экстремума в этой точке является знакоопределённость Гессиана f, а именно:

Вариации и обобщения

Если f-векторнозначная функция, то есть

{displaystyle f=(f_{1},f_{2},dots ,f_{n}),}

то её вторые частные производные образуют не матрицу, а тензор ранга 3.

История

Понятие введено Гессе (1844) который использовал другое название. Термин «Гессиан» был введён Сильвестром.

См. также

  • Якобиан
  • Определитель Гессе

Ссылки

  • Кудрявцев Л.Д «Краткий курс математического анализа. Т.2. Дифференциальное и интегральное исчиления функций многих переменных. Гармонический анализ», ФИЗМАТЛИТ, 2002, — 424 с. — ISBN 5-9221-0185-4

ca:Matriu Hessiana
cs:Hessova matice
he:מטריצת הסיאן
nl:Hessiaan
pl:Hesjan
sv:Hessian

Источник

  1. Выпуклость функции

Свойство функции,
при котором функция убывает, а затем
возрастает (имеет т. минимума)

Находим
первые частные производные функции
F(x1,
…, xn)
по всем переменным x1,
…, xn
(градиент). Находим гессиан (матрицу
вторых производных) функции F(x1,
…, xn).
Далее с помощью критерия Сильвестра
определяем знак гессиана. Если гессиан
определен не положительно, то функция
выпукла вверх, если гессиан определен
неотрицательно, то функция выпукла
вниз.

Функция
F(x1,
…, xn).

  1. Гессиан

Матрица частных
вторых производных.

Находим
первые частные производные функции
F(x1,
…, xn)
по всем переменным x1,
…, xn
(градиент). Далее вычисляем вторые
производные каждой первой производной
по каждой из переменных x1,
…, xn.
Расставить их на соответствующие места
в матрице.

Функция
F(x1,
…, xn).

  1. Критерий Сильвестра

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

Находим
первые частные производные функции
F(x1,
…, xn)
по всем переменным x1,
…, xn
(градиент). Находим гессиан (матрицу
вторых производных) функции F(x1,
…, xn).
Далее с помощью критерия Сильвестра
определяем, выпуклость функции: если
определители угловых миноров гессиана
всех порядков положительны, то функция
выпукла вниз; если знаки определителя
угловых миноров гессиана всех порядков
чередуются начиная с отрицательного,
то функция выпукла вверх; иначе
неопределенность.

Гессиан
функции F(x1,
…, xn).

  1. Выпуклость

Минимум.

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

Максимум

Находим градиент.
Каждую из координат градиента приравниваем
к нулю. Решаем данную систему уравнений,
и находим стационарные точки. Вычисляем
гессиан. Подставляем координаты точек
в гессиан. Если нечетные (1 и 3-ий) угловые
миноры гессиана меньше нуля, а четные
(2 и 4-ий) – большеё нуля, то данная точка
является точкой глобального максимума
функции.

Выпуклая вниз

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

Выпуклая вверх

Находим градиент.
Затем, вычисляем гессиан. Если главные
миноры гессиана нечетного порядка (1 и
3-го) меньше нуля, а четные (2 и 4-ий) –
больше нуля, то данная функция выпуклая
вверх.

  1. Задача условной оптимизации

Найти оптимальное
значение (максимальное или минимальное)
функции, при заданных ограничениях по
переменным.

  1. Найти решение
    задачи безусловной оптимизации и
    проверить его соответствие ОДР.

  2. Найти решения
    задачи условной оптимизации, при
    ограничениях равенствах.

  3. Найти значения ЦФ
    в точках пересечения ограничений ОДР.

  4. Сравнить
    значения функции F(x1,
    …, xn)
    в точках, полученных в результате
    действий проведенных в предыдущих трех
    пунктах, и выбрать из них максимальное
    или минимальное, в зависимости от
    условия задачи.

Принцип: отобрать
точки, в которых возможно минимальное
или максимальное значение функции в
заданной области, и выбрать среди них
оптимальную точку.

Функция
F(x1,
…, xn)
и система ограничений gi(x1, …,
xn)=<0.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
Источник

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

  • 1 Введение
    • 1.1 Постановка математической задачи
      • 1.1.1 Вычисление матрицы Якоби
      • 1.1.2 Вычисление матрицы Гессе
  • 2 Методы вычисления матрицы Якоби
    • 2.1 Прямое вычисление частных производных
      • 2.1.1 Оценка погрешности метода
    • 2.2 Метод Бройдена
  • 3 Методы вычисления матрицы Гессе
  • 4 Численный эксперимент
  • 5 Рекомендации программисту
  • 6 Заключение
  • 7 Список литературы

Введение

Постановка математической задачи

Вычисление матрицы Якоби

Пусть задана система n функций y_1(x_1, x_2, dots x_m) dots y_n(x_1, x_2, dots x_m) от m переменных. Матрицей Якоби или якобианом данной системы функций называется
матрица, составленная из частных производных этих функций по всем переменным.

J=begin{bmatrix} frac{partial y_1}{partial x_1} & cdots & frac{partial y_1}{partial x_m} \ vdots & ddots & vdots \ frac{partial y_n}{partial x_1} & cdots & frac{partial y_n}{partial x_m} end{bmatrix}.

Если в некоторой точке x_1 dots x_m очень сложно или невозможно вычислить частные производные, frac{partial y_i}{partial x_j} , то для вычисления матрицы Якоби применяются методы численного дифференцирования.

Вычисление матрицы Гессе

Матрицей Гессе функции m переменных y(x_1 dots x_m) называется матрица, составленная из вторых производных функции y(x_1 dots x_m) по всем переменным

H(f) = begin{bmatrix} frac{partial^2 y}{partial x_1^2} & frac{partial^2 y}{partial x_1,partial x_2} & cdots & frac{partial^2 y}{partial x_1,partial x_m} \ \ frac{partial^2 y}{partial x_2,partial x_1} & frac{partial^2 y}{partial x_2^2} & cdots & frac{partial^2 y}{partial x_2,partial x_m} \ \ vdots & vdots & ddots & vdots \ \ frac{partial^2 y}{partial x_m,partial x_1} & frac{partial^2 y}{partial x_m,partial x_2} & cdots & frac{partial^2 y}{partial x_m^2} end{bmatrix}

Если в некоторой точке x_1 dots x_m очень сложно или невозможно вычислить частные производные, frac{partial^2 y}{partial x_i partial x_j} , то для вычисления матрицы Гессе применяются методы численного дифференцирования.

Методы вычисления матрицы Якоби

Прямое вычисление частных производных

Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления
производной frac{partial y_i}{partial x_j} применяются методы вычисления первой производной.

Формула для элемента якобиана при использовании правой разностной производной:
J_{ij} = frac {y_i(x_1 dots x_j + h_{ij} dots x_m) - y_i(x_1 dots x_m)} {h_{ij} }

Формула для элемента якобиана при использовании центральной разностной производной:

J_{ij} = frac {y_i(x_1 dots x_j + h_{ij} dots x_m) - y_i(x_1 dots x_j - h_{ij} dots x_m)} {2*h_{ij}}

Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в m * (n + 1)
точках. Если использовать центральную производную, то нужно находить значения функций y_1 dots y_n в 2 * m * n точках. С другой, стороны погрешность правой производной имеет порядок O(h) а центральной – O(h^2).
В большинстве случаев вычисление значения функции y_i – это затратная по времени операция, поэтому используется правая разностная производная.

Оценка погрешности метода

Основная проблема при вычислении каждого элемента матрицы Якоби – как правильно выбрать шаг метода h_{ij} . Шаг выбирается независимо для каждого элемента матрицы.

Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной.
Для сокращения записи введём обозначения f(xi_j) = y_i(x_1 dots xi_j dots x_m).
Остаточный член в соотношении f(x)' approx frac{f(x+ h) - f1}{h} имеет вид
r_1 = - f''(xi)h/2 .
Если |f''(xi)| le M_2 , то |r_1| le M_2*h/2
Если значения f1 и f2 заданы с погрешностями vareps_1, vareps_2 le E , то погрешность будет
содержать ещё одно слагаемое r_2 = - frac{vareps_1 - vareps_2}{h} le 2E/h . Таким образом, оценка суммарной погрешности имеет вид |r| le |r_1| + |r_2| le f(h) = M_2 h/2 + 2E/h . Эта оценка достигает минимума при
h_0 = 2 sqrt {E/M_2}. При этом f(h_0) = 2 sqrt{M_2 E} .
Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. При величине шага, близкой к h_0 погрешность имеет порядок O(sqrt E) .

Метод Бройдена

Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений.
При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации.
Вычисление якобиана требует вычисления функций в O(m * n) точках. Это сложная и затратная по времени операция. Суть
метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации,
а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций y_1 dots y_n и их производных.

Пусть задана система нелинейных уравнений F(x) = 0, где F:R^m to R^n .
Тогда якобиан на n-ой итерации выражается по формуле
J_n = J_{n - 1} + frac{F(x_n) - F(x_{n-1}) - J_{n - 1} (x_n - x_{n-1})} { ||x_n - x_{n-1}||^2} (x_n - x_{n-1})^T

После этого следующее приближение вычисляется по формуле

x_{n + 1} = x_n - J_n^{-1} F(x_n)

Методы вычисления матрицы Гессе

Как и матрица Якоби, матрица Гессе может быть вычислена с помощью разностной аппроксимации производных.
frac{partial^2 f}{partial x_i,partial x_j} = frac{ f(x + (e_i + e_j) h) - f(x + e_i h) - f(x + e_j h) + f(x) } {h^2}, где
x – вектор переменных, а e_i и e_j – единичные вектора.
Эта формула требует вычисления значений функции f в frac {n (n + 1)} {2} точках.
Погрешность формулы имеет порядок O(h).

Численный эксперимент

В качестве примера рассчитаем с помощью вышеизложенного метода матрицу Гессе функции x^2 * sqrt y в точке (1, 1)

Величина шага Численный результат Истинное значение Погрешность
0.01

begin{bmatrix} 1.999999999999780 & 1.002499984530392 \ \ 1.002499984530392 & -0.250007812910846 end{bmatrix}

begin{bmatrix} 2 & 1 \ \ 1 & -0.25 end{bmatrix}

begin{bmatrix} 0.000000000000220 & 0.002499984530392 \ \ 0.002499984530392 & 0.500007812910846 end{bmatrix}

0.001

begin{bmatrix} 1.999999999724444 & 1.000249999938419 \1.000249999938419 & -0.250000078083623 end{bmatrix}

begin{bmatrix} 2 & 1 \ \ 1 & -0.25 end{bmatrix}

begin{bmatrix} 0.000000000275556 & 0.000249999938418 \ \ 0.000249999938418 & 0.500000078083623 end{bmatrix}

0.0001

begin{bmatrix} 1.999999998947288 & 1.000024996145044 \ \ 1.000024996145044 & -0.250000009582863 end{bmatrix}

begin{bmatrix} 2 & 1 \ \ 1 & -0.25 end{bmatrix}

begin{bmatrix} 0.000000001052712 & 0.000024996145044 \ \ 0.000024996145044 & 0.500000009582863 end{bmatrix}

0.00001

begin{bmatrix} 2.000002385926791 & 1.000002303186420 \ \ 1.000002303186420 & -0.250000020685093 end{bmatrix}

begin{bmatrix} 2 & 1 \ \ 1 & -0.25 end{bmatrix}

begin{bmatrix} 0.000002385926791 & 0.000002303186420 \ \ 0.000002303186420 & 0.500000020685093 end{bmatrix}

Рекомендации программисту

Вычисление матрицы Якоби требует большого числа операций. Поэтому при выборе метода её вычисления следует найти оптимальный баланс
между погрешностью метода и его скоростью.

Программа для вычисления якобиана, исходный код [1кб]

Программа для вычисления гессиана, исходный код [1кб]

Библиотека алгоритмов линейной алгебры [180кб]

Заключение

Список литературы

  • Самарский А. А. , Гулин А. В. Численные методы. Москва «Наука», 1989.
  • Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. Лаборатория Базовых Знаний, 2003.
  • Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна. — М.:ФИЗМАТЛИТ, 2002. — 496 с.
  • Хайкин С. Нейронные сети, полный курс. 2е издание, испр. — М: Вильямс. 2008. — 1103 с ISBN 978-5-8459-0890-2
  • Bishop C. Exact calculation of the Hessian matrix for the multilayer perceptron / Neural Computation. Volume 4, Issue 4 (July 1992). Pp. 494—501. ISSN:0899-7667
  • MacKay D. How do you evaluate the Hessian in the first place?
Источник

From Wikipedia, the free encyclopedia

In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term “functional determinants”.

Definitions and properties[edit]

Suppose {displaystyle f:mathbb {R} ^{n}to mathbb {R} } is a function taking as input a vector {displaystyle mathbf {x} in mathbb {R} ^{n}} and outputting a scalar {displaystyle f(mathbf {x} )in mathbb {R} .} If all second-order partial derivatives of f exist, then the Hessian matrix mathbf{H} of f is a square ntimes n matrix, usually defined and arranged as

{displaystyle mathbf {H} _{f}={begin{bmatrix}{dfrac {partial ^{2}f}{partial x_{1}^{2}}}&{dfrac {partial ^{2}f}{partial x_{1},partial x_{2}}}&cdots &{dfrac {partial ^{2}f}{partial x_{1},partial x_{n}}}\[2.2ex]{dfrac {partial ^{2}f}{partial x_{2},partial x_{1}}}&{dfrac {partial ^{2}f}{partial x_{2}^{2}}}&cdots &{dfrac {partial ^{2}f}{partial x_{2},partial x_{n}}}\[2.2ex]vdots &vdots &ddots &vdots \[2.2ex]{dfrac {partial ^{2}f}{partial x_{n},partial x_{1}}}&{dfrac {partial ^{2}f}{partial x_{n},partial x_{2}}}&cdots &{dfrac {partial ^{2}f}{partial x_{n}^{2}}}end{bmatrix}}.}

That is, the entry of the ith row and the jth column is

{displaystyle (mathbf {H} _{f})_{i,j}={frac {partial ^{2}f}{partial x_{i},partial x_{j}}}.}

If furthermore the second partial derivatives are all continuous, the Hessian matrix is a symmetric matrix by the symmetry of second derivatives.

The determinant of the Hessian matrix is called the Hessian determinant.[1]

The Hessian matrix of a function f is the transpose of the Jacobian matrix of the gradient of the function f; that is: {displaystyle mathbf {H} (f(mathbf {x} ))=mathbf {J} (nabla f(mathbf {x} ))^{T}.}

Applications[edit]

Inflection points[edit]

If f is a homogeneous polynomial in three variables, the equation f=0 is the implicit equation of a plane projective curve. The inflection points of the curve are exactly the non-singular points where the Hessian determinant is zero. It follows by Bézout’s theorem that a cubic plane curve has at most 9 inflection points, since the Hessian determinant is a polynomial of degree {displaystyle 3.}

Second-derivative test[edit]

The Hessian matrix of a convex function is positive semi-definite. Refining this property allows us to test whether a critical point x is a local maximum, local minimum, or a saddle point, as follows:

If the Hessian is positive-definite at x, then f attains an isolated local minimum at x. If the Hessian is negative-definite at x, then f attains an isolated local maximum at x. If the Hessian has both positive and negative eigenvalues, then x is a saddle point for f. Otherwise the test is inconclusive. This implies that at a local minimum the Hessian is positive-semidefinite, and at a local maximum the Hessian is negative-semidefinite.

For positive-semidefinite and negative-semidefinite Hessians the test is inconclusive (a critical point where the Hessian is semidefinite but not definite may be a local extremum or a saddle point). However, more can be said from the point of view of Morse theory.

The second-derivative test for functions of one and two variables is simpler than the general case. In one variable, the Hessian contains exactly one second derivative; if it is positive, then x is a local minimum, and if it is negative, then x is a local maximum; if it is zero, then the test is inconclusive. In two variables, the determinant can be used, because the determinant is the product of the eigenvalues. If it is positive, then the eigenvalues are both positive, or both negative. If it is negative, then the two eigenvalues have different signs. If it is zero, then the second-derivative test is inconclusive.

Equivalently, the second-order conditions that are sufficient for a local minimum or maximum can be expressed in terms of the sequence of principal (upper-leftmost) minors (determinants of sub-matrices) of the Hessian; these conditions are a special case of those given in the next section for bordered Hessians for constrained optimization—the case in which the number of constraints is zero. Specifically, the sufficient condition for a minimum is that all of these principal minors be positive, while the sufficient condition for a maximum is that the minors alternate in sign, with the 1 times 1 minor being negative.

Critical points[edit]

If the gradient (the vector of the partial derivatives) of a function f is zero at some point {displaystyle mathbf {x} ,} then f has a critical point (or stationary point) at {displaystyle mathbf {x} .} The determinant of the Hessian at mathbf {x} is called, in some contexts, a discriminant. If this determinant is zero then mathbf {x} is called a degenerate critical point of f, or a non-Morse critical point of f. Otherwise it is non-degenerate, and called a Morse critical point of f.

The Hessian matrix plays an important role in Morse theory and catastrophe theory, because its kernel and eigenvalues allow classification of the critical points.[2][3][4]

The determinant of the Hessian matrix, when evaluated at a critical point of a function, is equal to the Gaussian curvature of the function considered as a manifold. The eigenvalues of the Hessian at that point are the principal curvatures of the function, and the eigenvectors are the principal directions of curvature. (See Gaussian curvature § Relation to principal curvatures.)

Use in optimization[edit]

Hessian matrices are used in large-scale optimization problems within Newton-type methods because they are the coefficient of the quadratic term of a local Taylor expansion of a function. That is,

{displaystyle y=f(mathbf {x} +Delta mathbf {x} )approx f(mathbf {x} )+nabla f(mathbf {x} )^{mathrm {T} }Delta mathbf {x} +{frac {1}{2}},Delta mathbf {x} ^{mathrm {T} }mathbf {H} (mathbf {x} ),Delta mathbf {x} }

where nabla f is the gradient {displaystyle left({frac {partial f}{partial x_{1}}},ldots ,{frac {partial f}{partial x_{n}}}right).} Computing and storing the full Hessian matrix takes {displaystyle Theta left(n^{2}right)} memory, which is infeasible for high-dimensional functions such as the loss functions of neural nets, conditional random fields, and other statistical models with large numbers of parameters. For such situations, truncated-Newton and quasi-Newton algorithms have been developed. The latter family of algorithms use approximations to the Hessian; one of the most popular quasi-Newton algorithms is BFGS.[5]

Such approximations may use the fact that an optimization algorithm uses the Hessian only as a linear operator {displaystyle mathbf {H} (mathbf {v} ),} and proceed by first noticing that the Hessian also appears in the local expansion of the gradient:

{displaystyle nabla f(mathbf {x} +Delta mathbf {x} )=nabla f(mathbf {x} )+mathbf {H} (mathbf {x} ),Delta mathbf {x} +{mathcal {O}}(|Delta mathbf {x} |^{2})}

Letting {displaystyle Delta mathbf {x} =rmathbf {v} } for some scalar r, this gives

{displaystyle mathbf {H} (mathbf {x} ),Delta mathbf {x} =mathbf {H} (mathbf {x} )rmathbf {v} =rmathbf {H} (mathbf {x} )mathbf {v} =nabla f(mathbf {x} +rmathbf {v} )-nabla f(mathbf {x} )+{mathcal {O}}(r^{2}),}

that is,

{displaystyle mathbf {H} (mathbf {x} )mathbf {v} ={frac {1}{r}}left[nabla f(mathbf {x} +rmathbf {v} )-nabla f(mathbf {x} )right]+{mathcal {O}}(r)}

so if the gradient is already computed, the approximate Hessian can be computed by a linear (in the size of the gradient) number of scalar operations. (While simple to program, this approximation scheme is not numerically stable since r has to be made small to prevent error due to the {displaystyle {mathcal {O}}(r)} term, but decreasing it loses precision in the first term.[6])

Notably regarding Randomized Search Heuristics, the evolution strategy’s covariance matrix adapts to the inverse of the Hessian matrix, up to a scalar factor and small random fluctuations.
This result has been formally proven for a single-parent strategy and a static model, as the population size increases, relying on the quadratic approximation.[7]

Other applications[edit]

The Hessian matrix is commonly used for expressing image processing operators in image processing and computer vision (see the Laplacian of Gaussian (LoG) blob detector, the determinant of Hessian (DoH) blob detector and scale space). It can be used in normal mode analysis to calculate the different molecular frequencies in infrared spectroscopy.[8] It can also be used in local sensitivity and statistical diagnostics.[9]

Generalizations[edit]

Bordered Hessian[edit]

A bordered Hessian is used for the second-derivative test in certain constrained optimization problems. Given the function f considered previously, but adding a constraint function g such that {displaystyle g(mathbf {x} )=c,} the bordered Hessian is the Hessian of the Lagrange function {displaystyle Lambda (mathbf {x} ,lambda )=f(mathbf {x} )+lambda [g(mathbf {x} )-c]:}[10]

{displaystyle mathbf {H} (Lambda )={begin{bmatrix}{dfrac {partial ^{2}Lambda }{partial lambda ^{2}}}&{dfrac {partial ^{2}Lambda }{partial lambda partial mathbf {x} }}\left({dfrac {partial ^{2}Lambda }{partial lambda partial mathbf {x} }}right)^{mathsf {T}}&{dfrac {partial ^{2}Lambda }{partial mathbf {x} ^{2}}}end{bmatrix}}={begin{bmatrix}0&{dfrac {partial g}{partial x_{1}}}&{dfrac {partial g}{partial x_{2}}}&cdots &{dfrac {partial g}{partial x_{n}}}\[2.2ex]{dfrac {partial g}{partial x_{1}}}&{dfrac {partial ^{2}Lambda }{partial x_{1}^{2}}}&{dfrac {partial ^{2}Lambda }{partial x_{1},partial x_{2}}}&cdots &{dfrac {partial ^{2}Lambda }{partial x_{1},partial x_{n}}}\[2.2ex]{dfrac {partial g}{partial x_{2}}}&{dfrac {partial ^{2}Lambda }{partial x_{2},partial x_{1}}}&{dfrac {partial ^{2}Lambda }{partial x_{2}^{2}}}&cdots &{dfrac {partial ^{2}Lambda }{partial x_{2},partial x_{n}}}\[2.2ex]vdots &vdots &vdots &ddots &vdots \[2.2ex]{dfrac {partial g}{partial x_{n}}}&{dfrac {partial ^{2}Lambda }{partial x_{n},partial x_{1}}}&{dfrac {partial ^{2}Lambda }{partial x_{n},partial x_{2}}}&cdots &{dfrac {partial ^{2}Lambda }{partial x_{n}^{2}}}end{bmatrix}}={begin{bmatrix}0&{dfrac {partial g}{partial mathbf {x} }}\left({dfrac {partial g}{partial mathbf {x} }}right)^{mathsf {T}}&{dfrac {partial ^{2}Lambda }{partial mathbf {x} ^{2}}}end{bmatrix}}}

If there are, say, m constraints then the zero in the upper-left corner is an mtimes m block of zeros, and there are m border rows at the top and m border columns at the left.

The above rules stating that extrema are characterized (among critical points with a non-singular Hessian) by a positive-definite or negative-definite Hessian cannot apply here since a bordered Hessian can neither be negative-definite nor positive-definite, as {displaystyle mathbf {z} ^{mathsf {T}}mathbf {H} mathbf {z} =0} if mathbf {z} is any vector whose sole non-zero entry is its first.

The second derivative test consists here of sign restrictions of the determinants of a certain set of n-m submatrices of the bordered Hessian.[11] Intuitively, the m constraints can be thought of as reducing the problem to one with n-m free variables. (For example, the maximization of {displaystyle fleft(x_{1},x_{2},x_{3}right)} subject to the constraint {displaystyle x_{1}+x_{2}+x_{3}=1} can be reduced to the maximization of {displaystyle fleft(x_{1},x_{2},1-x_{1}-x_{2}right)} without constraint.)

Specifically, sign conditions are imposed on the sequence of leading principal minors (determinants of upper-left-justified sub-matrices) of the bordered Hessian, for which the first {displaystyle 2m} leading principal minors are neglected, the smallest minor consisting of the truncated first {displaystyle 2m+1} rows and columns, the next consisting of the truncated first {displaystyle 2m+2} rows and columns, and so on, with the last being the entire bordered Hessian; if {displaystyle 2m+1} is larger than {displaystyle n+m,} then the smallest leading principal minor is the Hessian itself.[12] There are thus n-m minors to consider, each evaluated at the specific point being considered as a candidate maximum or minimum. A sufficient condition for a local maximum is that these minors alternate in sign with the smallest one having the sign of {displaystyle (-1)^{m+1}.} A sufficient condition for a local minimum is that all of these minors have the sign of {displaystyle (-1)^{m}.} (In the unconstrained case of m=0 these conditions coincide with the conditions for the unbordered Hessian to be negative definite or positive definite respectively).

Vector-valued functions[edit]

If f is instead a vector field {displaystyle mathbf {f} :mathbb {R} ^{n}to mathbb {R} ^{m},} that is,

{displaystyle mathbf {f} (mathbf {x} )=left(f_{1}(mathbf {x} ),f_{2}(mathbf {x} ),ldots ,f_{m}(mathbf {x} )right),}

then the collection of second partial derivatives is not a ntimes n matrix, but rather a third-order tensor. This can be thought of as an array of m Hessian matrices, one for each component of mathbf {f} :

{displaystyle mathbf {H} (mathbf {f} )=left(mathbf {H} (f_{1}),mathbf {H} (f_{2}),ldots ,mathbf {H} (f_{m})right).}

This tensor degenerates to the usual Hessian matrix when {displaystyle m=1.}

Generalization to the complex case[edit]

In the context of several complex variables, the Hessian may be generalized. Suppose {displaystyle fcolon mathbb {C} ^{n}to mathbb {C} ,} and write {displaystyle fleft(z_{1},ldots ,z_{n}right).} Then the generalized Hessian is {displaystyle {frac {partial ^{2}f}{partial z_{i}partial {overline {z_{j}}}}}.} If f satisfies the n-dimensional Cauchy–Riemann conditions, then the complex Hessian matrix is identically zero.

Generalizations to Riemannian manifolds[edit]

Let (M,g) be a Riemannian manifold and nabla its Levi-Civita connection. Let {displaystyle f:Mto mathbb {R} } be a smooth function. Define the Hessian tensor by

{displaystyle operatorname {Hess} (f)in Gamma left(T^{*}Motimes T^{*}Mright)quad {text{ by }}quad operatorname {Hess} (f):=nabla nabla f=nabla df,}

where this takes advantage of the fact that the first covariant derivative of a function is the same as its ordinary differential. Choosing local coordinates {displaystyle left{x^{i}right}} gives a local expression for the Hessian as

{displaystyle operatorname {Hess} (f)=nabla _{i},partial _{j}f dx^{i}!otimes !dx^{j}=left({frac {partial ^{2}f}{partial x^{i}partial x^{j}}}-Gamma _{ij}^{k}{frac {partial f}{partial x^{k}}}right)dx^{i}otimes dx^{j}}

where Gamma^k_{ij} are the Christoffel symbols of the connection. Other equivalent forms for the Hessian are given by

{displaystyle operatorname {Hess} (f)(X,Y)=langle nabla _{X}operatorname {grad} f,Yrangle quad {text{ and }}quad operatorname {Hess} (f)(X,Y)=X(Yf)-df(nabla _{X}Y).}

See also[edit]

  • The determinant of the Hessian matrix is a covariant; see Invariant of a binary form
  • Polarization identity, useful for rapid calculations involving Hessians.
  • Jacobian matrix – Matrix of all first-order partial derivatives of a vector-valued function
  • Hessian equation

Notes[edit]

  1. ^ Binmore, Ken; Davies, Joan (2007). Calculus Concepts and Methods. Cambridge University Press. p. 190. ISBN 978-0-521-77541-0. OCLC 717598615.
  2. ^ Callahan, James J. (2010). Advanced Calculus: A Geometric View. Springer Science & Business Media. p. 248. ISBN 978-1-4419-7332-0.
  3. ^ Casciaro, B.; Fortunato, D.; Francaviglia, M.; Masiello, A., eds. (2011). Recent Developments in General Relativity. Springer Science & Business Media. p. 178. ISBN 9788847021136.
  4. ^ Domenico P. L. Castrigiano; Sandra A. Hayes (2004). Catastrophe theory. Westview Press. p. 18. ISBN 978-0-8133-4126-2.
  5. ^ Nocedal, Jorge; Wright, Stephen (2000). Numerical Optimization. Springer Verlag. ISBN 978-0-387-98793-4.
  6. ^ Pearlmutter, Barak A. (1994). “Fast exact multiplication by the Hessian” (PDF). Neural Computation. 6 (1): 147–160. doi:10.1162/neco.1994.6.1.147. S2CID 1251969.
  7. ^ Shir, O.M.; A. Yehudayoff (2020). “On the covariance-Hessian relation in evolution strategies”. Theoretical Computer Science. Elsevier. 801: 157–174. doi:10.1016/j.tcs.2019.09.002.
  8. ^ Mott, Adam J.; Rez, Peter (December 24, 2014). “Calculation of the infrared spectra of proteins”. European Biophysics Journal. 44 (3): 103–112. doi:10.1007/s00249-014-1005-6. ISSN 0175-7571. PMID 25538002. S2CID 2945423.
  9. ^ Liu, Shuangzhe; Leiva, Victor; Zhuang, Dan; Ma, Tiefeng; Figueroa-Zúñiga, Jorge I. (March 2022). “Matrix differential calculus with applications in the multivariate linear model and its diagnostics”. Journal of Multivariate Analysis. 188: 104849. doi:10.1016/j.jmva.2021.104849.
  10. ^ Hallam, Arne (October 7, 2004). “Econ 500: Quantitative Methods in Economic Analysis I” (PDF). Iowa State.
  11. ^ Neudecker, Heinz; Magnus, Jan R. (1988). Matrix Differential Calculus with Applications in Statistics and Econometrics. New York: John Wiley & Sons. p. 136. ISBN 978-0-471-91516-4.
  12. ^ Chiang, Alpha C. (1984). Fundamental Methods of Mathematical Economics (Third ed.). McGraw-Hill. p. 386. ISBN 978-0-07-010813-4.

Further reading[edit]

  • Lewis, David W. (1991). Matrix Theory. Singapore: World Scientific. ISBN 978-981-02-0689-5.
  • Magnus, Jan R.; Neudecker, Heinz (1999). “The Second Differential”. Matrix Differential Calculus : With Applications in Statistics and Econometrics (Revised ed.). New York: Wiley. pp. 99–115. ISBN 0-471-98633-X.

External links[edit]

  • “Hessian of a function”, Encyclopedia of Mathematics, EMS Press, 2001 [1994]
  • Weisstein, Eric W. “Hessian”. MathWorld.
Источник

Добавить комментарий