Quadratic function of multiple variables

Definition

Consider variables $x_1,x_2,\dots,x_n$. A quadratic function of the variables $x_1,x_2,\dots,x_n$ is a function of the form:

$\left(\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_ix_j\right) + \left(\sum_{i=1}^n b_ix_i\right) + c$

In vector form, if we denote by $\vec{x}$ the column vector with coordinates $x_1,x_2,\dots,x_n$, then we can write the function as:

$\vec{x}^TA\vec{x} + \vec{b}^T\vec{x} + c$

where $A$ is a $n \times n$ matrix with entries $a_{ij}$ and $\vec{b}$ is the column vector with entries $b_i$.

Note that the matrix $A$ is non-unique: if $A + A^T = F + F^T$ then we could replace $A$ by $F$. Therefore, we could choose to replace $A$ by the matrix $(A + A^T)/2$ and have the advantage of working with a symmetric matrix.

Key data

For the discussion here, assume that $A$ has been made a symmetric matrix.

Item	Value	Consistency with the case $n = 1$, where $f(x) = ax^2 + bx + c$, $A = (a)$ (a $1 \times 1$ matrix), $\vec{b} = (b)$ (a 1-dimensional vector)
default domain	the whole of $\R^n$	the whole of $\R$
range	If the matrix $A$ is not positive semidefinite or negative semidefinite, the range is all of $\R$. If the matrix $A$ is positive definite or ($A$ is positive semidefinite and $\vec{b}$ is in its image), the range is $[m,\infty)$ where $m$ is the minimum value. If the matrix $A$ is negative definite or ($A$ is negative semidefinite and $\vec{b}$ is in its image), the range is $(-\infty,m]$ where $m$ is the maximum value.	The case of "not positive semidefinite or negative semidefinite" does not arise for $n = 1$. Moreover, all the semidefinite cases must be definite, so we only have to consider the positive definite case and the negative definite case. The positive definite case corresponds to $a > 0$ The negative definite case corresponds to $a < 0$
local minimum value and points of attainment	If the matrix $A$ is positive definite, then $c - \frac{1}{4}\vec{b}^TA^{-1}\vec{b}$, attained at $\frac{-1}{2}A^{-1}\vec{b}$ If $A$ is positive semidefinite but not positive definite, it depends on whether $\vec{b}$ is in the image of $A$. If yes, replace $A^{-1}\vec{b}$ with the solution $\vec{v}$ to $A\vec{v} = \vec{b}$, so we get a local minimum of $c - \frac{1}{4}\vec{b}^T\vec{v}$ attained at $\frac{-1}{2}\vec{v}$ If $A$ is not positive semidefinite or if $\vec{b}$ is not in the image of $A$, no local minimum value	The positive definite case corresponds to $a > 0$: Here, the local minimum value of $c - \frac{b^2}{4a}$ is attained at $\frac{-b}{2a}$ (consistent with the matrix formulation) The negative definite case corresponds to $a < 0$, and there is no minimum in this case.
local maximum value and points of attainment	If the matrix $A$ is negative definite, then $c - \frac{1}{4}\vec{b}^TA^{-1}\vec{b}$, attained at $\frac{-1}{2}A^{-1}\vec{b}$ If $A$ is negative semidefinite but not negative definite, it depends on whether $\vec{b}$ is in the image of $A$. If yes, replace $A^{-1}\vec{b}$ with the solution $\vec{v}$ to $A\vec{v} = \vec{b}$, so we get a local minimum of $c - \frac{1}{4}\vec{b}^T\vec{v}$ attained at $\frac{-1}{2}\vec{v}$ If $A$ is not negative semidefinite or if $\vec{b}$ is not in the image of $A$, no local minimum value	The negative definite case corresponds to $a < 0$: Here, the local maximum value of $c - \frac{b^2}{4a}$ is attained at $\frac{-b}{2a}$ (consistent with the matrix formulation) The positive definite case corresponds to $a > 0$, and there is no maximum in this case.
gradient vector function (analogous to the derivative)	$\vec{x} \mapsto 2A\vec{x} + \vec{b}$	the derivative is $x \mapsto 2ax + b$ (consistent with the matrix formulation)
Hessian matrix (analogous to the second derivative)	$\vec{x} \mapsto 2A$ (constant matrix-valued function)	the second derivative is the constant function $x \mapsto 2a$ (consistent with the matrix formulation)

Differentiation

Partial derivatives and gradient vector

Case of general matrix

The partial derivative with respect to the variable $x_i$, and therefore also the $i^{th}$ coordinate of the gradient vector, is given by:

$\frac{\partial f}{\partial x_i} = \left(\sum_{j=1}^n (a_{ij} + a_{ji})x_j\right) + b_i$

In terms of the matrix and vector notation, the gradient vector, expressed as a column vector, is:

$(\nabla f)(\vec{x}) = (A + A^T)\vec{x} + \vec{b}$

Case of symmetric matrix

In the case that $A$ is a symmetric matrix, the above expressions simplify as follows.

Since $a_{ij} = a_{ji}$ for all $i,j$, the expression for the partial derivative becomes:

$\frac{\partial f}{\partial x_i} = \left(\sum_{j=1}^n 2a_{ij} x_j\right) + b_i$

The expression for the gradient vector becomes:

$(\nabla f)(\vec{x}) = 2A\vec{x} + \vec{b}$

Case $n = 1$

A sanity check for the above expressions is that in the case $n = 1$, where $A = (a), \vec{b} = b$, we get the same answers as for the quadratic function $f(x) = ax^2 + bx + c$.

This is indeed the case. The only partial derivative here is the ordinary derivative, and this also is the gradient vector, and has expression:

$f'(x) = 2ax + b$

This agrees with both the expression for $\partial f/\partial x_i$ and the expression for $(\nabla f)(\vec{x})$.

Second-order partial derivatives and Hessian matrix

Case of general matrix

Recall that we had obtained (we replace the dummy variable $j$ by $k$ to facilitate differentiation with respect to $j$ in the next step):

$\frac{\partial f}{\partial x_i} = \left(\sum_{k=1}^n (a_{ik} + a_{ki})x_k\right) + b_i$

Differentiating both sides with respect to $x_j$ (note that $j$ may be equal to $i$ or different from $i$) we find that the only term with a nonzero derivative is the term where $k = j$. In this case, the derivative is the coefficient of $x_j$. Therefore, we obtain:

$\frac{\partial^2 f}{\partial x_j \partial x_i} = a_{ij} + a_{ji}$

Thus, the Hessian matrix of the quadratic function is given as:

$H(f)(\vec{x}) = A + A^T$

Note that this is independent of the choice of $\vec{x}$. This fact is true only because of the nature of the function: for more general functional forms, the Hessian matrix varies with the choice of input vector.

We can also see this in matrix form directly. The gradient function is:

$(\nabla f)(\vec{x}) = (A + A^T)\vec{x} + \vec{b}$

This is a linear transformation, and the Jacobian matrix of this linear transformation computes the Hessian that we want. We can use the well-known fact that the Jacobian matrix of a linear transformation coincides with the matrix describing the linear part of the transformation, and therefore the Hessian is:

$H(f)(\vec{x}) = A + A^T$

Case of symmetric matrix

We can either plug into the formulas for the general case or perform similar calculations to get the formulas in the case that $A$ is a symmetric matrix:

$\frac{\partial^2 f}{\partial x_j \partial x_i} = 2a_{ij}$

$H(f)(\vec{x}) = 2A$

Case $n = 1$

A sanity check for the above expressions is that in the case $n = 1$, where $A = (a), \vec{b} = b$, we get the same answers as for the quadratic function $f(x) = ax^2 + bx + c$.

This is indeed the case. The only second-order partial derivative is $f''(x) = 2a$. This agrees both with the formula for the second-order partial derivative and with the formula for the Hessian matrix.

Higher derivatives

All higher order partial derivatives (pure or mixed) are zero. This can be seen directly from the fact that the second-order partial derivatives are all constants, so differentiating them further (with respect to any variable) gives zero.

Therefore, the higher derivative tensors (the higher-order analogues of the gradient vector and Hessian matrix) are also identically zero.

Points and intervals of interest

For the discussion here, assume that $A$ is symmetric. If it is not, replace $A$ by the matrix $(A + A^T)/2$.

Critical points

Case that the matrix $A$ is invertible

To find the critical points, we need to set the gradient vector equal to zero. This gives the vector equation:

$2A\vec{x} + \vec{b} = \vec{0}$

In other words:

$A \vec{x} = \frac{-1}{2}\vec{b}$

Under the assumption that $A$ is invertible (or equivalently, that all its eigenvalues are nonzero), we can left-multiply both sides by $A^{-1}$ and obtain:

$\vec{x} = \frac{-1}{2} A^{-1} \vec{b}$

We thus have a unique critical point as described above.

Case that the matrix $A$ is non-invertible

We still need to solve the same linear system:

$2A \vec{x} + \vec{b}$

However, since $A$ is no longer invertible (i.e., it has zero as an eigenvalue, or equivalently, it has a nonzero kernel), two cases arise:

• No solution exists. This happens if the vector $\vec{b}$ is not in the image of the linear transformation defined by $A$. Conceptually, what is happening is that the linear part of $f$ is not constrained by the quadratic part, and therefore the function is unbounded.
• A solution exists, but it is not unique. This happens if the vector $\vec{b}$ is in the image of the linear transformation defined by $A$. In fact, the solution set is an affine space of dimension equal to the nullity of $A$. Thus, we get an affine space's worth of critical points.

Determination of local extremum behavior at critical points

Case that the matrix $A$ is invertible

Recall that the Hessian matrix of $f$ is $2A$. Therefore, by the second derivative test for a function of multiple variables, we obtain the following:

• If $A$ is a symmetric positive-definite matrix, i.e., all its eigenvalues are positive, then the unique critical point $\frac{-1}{2}A^{-1}\vec{b}$ is a point of local minimum and is the unique point of absolute minimum (an alternate derivation of this fact is later in the page).
• If $A$ is negative-definite matrix, i.e., all its eigenvalues are negative, then the unique critical point $\frac{-1}{2}A^{-1}\vec{b}$ is a point of local maximum and is the unique point of absolute maximum.
• If $A$ has both positive and negative eigenvalues, then the unique critical point $\frac{-1}{2}A^{-1}\vec{b}$ is neither a point of local minimum nor a point of local maximum. In fact, it gives a saddle point for the function. There is no point of local extremum and the range of the function is all of $\R$.

Case that the matrix $A$ is non-invertible

In this case, the Hessian matrix, $2A$, is also non-invertible and in particular has zero as an eigenvalue.

In the case that there are no critical points, there is nothing to say.

In the case that there are critical points, we note that, through any critical point, there is a direction along which the second derivative is zero. In fact, what's happening geometrically is that the set of critical points form an affine subspace and the quadratic function $f$ is constant on that affine subspace. How the behavior of that affine subspace compares with the values of the function elsewhere depends on the nonzero eigenvalues.

• In the case that $A$ is a symmetric positive-semidefinite matrix, i.e., all its nonzero eigenvalues are positive, the function attains a local minimum and also its absolute minimum at all its critical points. Note that, since the function is constant at this minimum value on the affine space, none of these is a point of strict local minimum.
• In the case that $A$ is a symmetric negative-semidefinite matrix, i.e., all its nonzero eigenvalues are negative, the function attains a local maximum and also its absolute maximum value at all its critical points. Note that, since the function is constant at this minimum value on the affine space, none of these is a point of strict local minimum.

Geometry of the function

The geometry of the quadratic function is largely determined by the spectrum of the matrix $A$ (or equivalently, the spectrum of the matrix $2A$. As before, we shall assume that $A$ is a symmetric matrix. If not, replace $2A$ in the discussion below by $A + A^T$.

Eigenvalues of the Hessian

Since $2A$ is a symmetric real matrix, it can be written in the form:

$2A = USU^{-1}$

where $U$ is an orthogonal matrix and $S$ is a diagonal matrix with real entries. The diagonal entries of $S$ are the eigenvalues of $2A$. Another way of thinking of the above is that with a change of basis that preserves the Euclidean norm, we can convert the Hessian to a diagonal transformation.

The following cases are of interest:

Case on $S$ (i.e., the set of eigenvalues)	Corresponding term for matrix $2A$ (and hence also for $A$)
all positive	symmetric positive-definite matrix
all nonnegative	symmetric positive-semidefinite matrix
all negative	symmetric negative-definite matrix
all nonpositive	symmetric negative-semidefinite matrix
all nonzero	symmetric invertible matrix
some positive, some negative (maybe some zero)	indefinite matrix

Alternate analysis of extreme values

For the discussion of cases, assume that $A$ is a symmetric matrix. If $A$ is not symmetric, replace it by the symmetric matrix $(A + A^T)/2$.

Positive definite case

First, we consider the case where $A$ is a symmetric positive definite matrix. In other words, we can write $A$ in the form:

$A = M^TM$

where $M$ is a $n \times n$ invertible matrix.

We can "complete the square" for this function:

$f(\vec{x}) = \left(M\vec{x} + \frac{1}{2}(M^T)^{-1}\vec{b}\right)^T\left(M\vec{x} + \frac{1}{2}(M^T)^{-1}\vec{b}\right) + \left(c - \frac{1}{4}\vec{b}^TA^{-1}\vec{b}\right)$

In other words:

$f(\vec{x}) = \left \| M\vec{x} + \frac{1}{2}(M^T)^{-1}\vec{b}\right \|^2 + \left(c - \frac{1}{4}\vec{b}^TA^{-1}\vec{b}\right)$

This is minimized when the expression whose norm we are measuring is zero, so that it is minimized when we have:

$M\vec{x} + \frac{1}{2}(M^T)^{-1}\vec{b} = \vec{0}$

Simplifying, we obtain that we minimum occurs at:

$\vec{x} = -\frac{1}{2}A^{-1}\vec{b}$

Moreover, the value of the minimum is:

$c - \frac{1}{4}\vec{b}^TA^{-1}\vec{b}$