Hessian matrix

Part of a series of articles about

Definitions
Derivative (generalizations) Differential infinitesimal of a function total
Concepts
Differentiation notation Second derivative Third derivative Change of variables Implicit differentiation Related rates Taylor's theorem
Rules and identities
Sum Product Chain Power Quotient General Leibniz Faà di Bruno's formula

Integral

Definitions
Lists of integrals
Antiderivative Integral (improper) Riemann integral Lebesgue integration Contour integration
Integration by
Parts Discs Cylindrical shells Substitution (trigonometric) Partial fractions Order Reduction formulae

Series

Convergence tests
Geometric (arithmetico-geometric) Harmonic Alternating Power Binomial Taylor
Summand limit (term test) Ratio Root Integral Direct comparison Limit comparison Alternating series Cauchy condensation Dirichlet Abel

Vector

Theorems
Gradient Divergence Curl Laplacian Directional derivative Identities
Divergence Gradient Green's Kelvin–Stokes

Multivariable

Formalisms
Matrix Tensor Exterior Geometric
Definitions
Partial derivative Multiple integral Line integral Surface integral Volume integral Jacobian Hessian matrix

Specialized

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".

Specifically, suppose $f : ℝ n \to ℝ$ is a function taking as input a vector $x \in ℝ n$ and outputting a scalar $f (x) \in ℝ$ ; if all second partial derivatives of $f$ exist and are continuous over the domain of the function, then the Hessian matrix $H$ of $f$ is a square $n \times n$ matrix, usually defined and arranged as follows:

{\mathbf H}={\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}}.

or, component-wise:

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

The determinant of the above matrix is also sometimes referred to as the Hessian.^[1]

The Hessian matrix can be considered related to the Jacobian matrix by $H (f)(x) = J (\nabla f)(x)$ .

Mixed derivatives and symmetry of the Hessian

The mixed derivatives of f are the entries off the main diagonal in the Hessian. Assuming that they are continuous, the order of differentiation does not matter (Schwarz's theorem). For example,

{\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).

In a formal statement: if the second derivatives of $f$ are all continuous in a neighborhood $D$ , then the Hessian of $f$ is a symmetric matrix throughout $D$ ; see symmetry of second derivatives.

Critical points

If the gradient (the vector of the partial derivatives) of a function $f$ is zero at some point $x$ , then $f$ has a critical point (or stationary point) at $x$ . The determinant of the Hessian at $x$ is then called the discriminant. If this determinant is zero then $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]

Second derivative test

Main article: Second partial derivative test

The Hessian matrix of a convex function is positive semi-definite. Refining this property allows us to test if 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 (respectively, a local maximum), the Hessian is positive-semi-definite (respectively, negative semi-definite).

Note that 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 simple. In one variable, the Hessian contains just 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×1 minor being negative.

Bordered Hessian

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 $g (x) = c$ , the bordered Hessian is the Hessian of the Lagrange function $\Lambda (\mathbf {x} ,\lambda )=f(\mathbf {x} )-\lambda [g(\mathbf {x} )-c]$ :

{\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)^{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)^{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 m × m block of zeroes, 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 $z T H z$ = 0 if $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.^[5] Intuitively, one can think of the m constraints as reducing the problem to one with n – m free variables. (For example, the maximization of $f (x 1,x 2,x 3)$ subject to the constraint $x 1 +x 2 +x 3 = 1$ can be reduced to the maximization of $f (x 1,x 2,1-x 1 -x 2)$ without constraint.)

Specifically, sign conditions are imposed on the sequence of principal minors (determinants of upper-left-justified sub-matrices) of the bordered Hessian, the smallest minor consisting of the truncated first 2m+1 rows and columns, the next consisting of the truncated first 2m+2 rows and columns, and so on, with the last being the entire bordered Hessian.^[6] 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 (–1)^m+1. A sufficient condition for a local minimum is that all of these minors have the sign of (–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

If $f$ is instead a vector field $f : ℝ n \to ℝ m$ , i.e.

{\mathbf f}({\mathbf x})=(f_{1}({\mathbf x}),f_{2}({\mathbf x}),\dots ,f_{m}({\mathbf x})),

then the collection of second partial derivatives is not a $n \times 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 $f$ :

{\mathbf H}({\mathbf f})=({\mathbf H}(f_{1}),{\mathbf H}(f_{2}),\dots ,{\mathbf H}(f_{m}))

This tensor promptly degenerates to the usual Hessian matrix when $m$ = 1.

Generalization to the complex case

In the context of several complex variables, the Hessian may be generalized. Suppose $f\colon \mathbb {C} ^{n}\longrightarrow \mathbb {C}$ , and we write $f\left(z_{1},\ldots ,z_{n}\right)$ . Then one may generalize the Hessian to ${\frac {\partial ^{2}f}{\partial z_{i}\partial {\overline {z_{j}}}}}$ . Note that if $f$ satisfies the n-dimensional Cauchy-Riemann conditions, then the complex Hessian matrix is identically zero.

Generalizations to Riemannian manifolds

Let $(M,g)$ be a Riemannian manifold and $\nabla$ its Levi-Civita connection. Let $f:M \to \mathbb{R}$ be a smooth function. We may define the Hessian tensor

\displaystyle \mbox{Hess}(f) \in \Gamma(T^*M \otimes T^*M)

\mbox{Hess}(f):=\nabla \nabla f = \nabla df

where we have taken advantage of the first covariant derivative of a function being the same as its ordinary derivative. Choosing local coordinates $\{x^i\}$ we obtain the local expression for the Hessian as

\mbox{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

\mbox{Hess}(f)(X,Y)= \langle \nabla_X \mbox{grad}f,Y \rangle

and

\mbox{Hess}(f)(X,Y)=X(Yf)-df(\nabla_XY)

Use in optimization

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,

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 $(\partial f / \partial x 1, ..., \partial f / \partial x n)$ . Computing and storing the full Hessian matrix takes $Θ (n 2)$ 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.^[7]

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

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

Letting $Δ x = r v$ for some scalar $r$ , this gives

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

i.e.,

{\mathbf {H}}({\mathbf {v}})={\frac {1}{r}}{\Bigl [}\nabla f({\mathbf {x}}+r{\mathbf {v}})-\nabla f({\mathbf {x}}){\Bigr ]}+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 $O (r)$ term, but decreasing it loses precision in the first term.^[8])

Notes

↑ Binmore, Ken; Davies, Joan (2007). Calculus Concepts and Methods. Cambridge University Press. p. 190. ISBN 9780521775410. OCLC 717598615.
↑ Callahan, James J. (2010). Advanced Calculus: A Geometric View. Springer Science & Business Media. p. 248. ISBN 9781441973320.
↑ Casciaro, B.; Fortunato, D.; Francaviglia, M.; Masiello, A., eds. (2011). Recent Developments in General Relativity. Springer Science & Business Media. p. 178. ISBN 9788847021136.
↑ Domenico P. L. Castrigiano; Sandra A. Hayes (2004). Catastrophe theory. Westview Press. p. 18. ISBN 978-0-8133-4126-2.
↑ Neudecker, Heinz; Magnus, Jan R. (1988). Matrix Differential Calculus with Applications in Statistics and Econometrics. New York: John Wiley & Sons. p. 136. ISBN 0-471-91516-5.
↑ Chiang, Alpha C. (1984). Fundamental Methods of Mathematical Economics (Third ed.). McGraw-Hill. p. 386.
↑ Nocedal, Jorge; Wright, Stephen (2000). Numerical Optimization. Springer Verlag. ISBN 978-0387987934.
↑ 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.

External links

Weisstein, Eric W. "Hessian". MathWorld.

Matrix classes

Explicitly constrained entries	(0,1) Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Binary Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Markov Metzler Monomial Moore Nonnegative Partitioned Parisi Pentadiagonal Permutation Persymmetric Polynomial Positive Quaternionic Sign Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Unitary Vandermonde Walsh Z

Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero

Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Diagonalizable Hurwitz Positive-definite Stability Stieltjes

Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Orthonormal Singular Unimodular Unipotent Totally unimodular Weighing

With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Coxeter Derogatory Distance Duplication Elimination Euclidean distance Fundamental (linear differential equation) Generator Gramian Hessian Householder Jacobian Moment Payoff Pick Random Rotation Seifert Shear Similarity Symplectic Totally positive Transformation Wedderburn X–Y–Z

Used in statistics	Bernoulli Centering Correlation Covariance Dispersion Doubly stochastic Fisher information Hat Precision Stochastic Transition

Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Skew-adjacency Tutte

Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)

Related terms	Jordan canonical form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Quaternionic matrix Row echelon form Wronskian

List of matrices Category:Matrices

This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.