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:

$(\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}{x}_i{x}_j)+(\sum _{i=1}^n{b}_i{x}_i)+c$

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

${\overrightarrow{x}}^{T}A\overrightarrow{x}+{\overrightarrow{b}}^T\overrightarrow{x}+c$

where $A$ is a $n\times n$ matrix with entries $a_{ij}$ and $\overrightarrow{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)=a{x}^2+bx+c$, $A=(a),\overrightarrow{b}=b$
default domain	the whole of ${\mathbb{R}}^n$	the whole of $\mathbb{R}$
range	If the matrix $A$ is not positive semidefinite or negative semidefinite, the range is all of $\mathbb{R}$. If the matrix $A$ is positive definite or ($A$ is positive semidefinite and $\overrightarrow{b}$ is in its image), the range is $[m,\mathrm{\infty })$ where $m$ is the minimum value. If the matrix $A$ is negative definite or ($A$ is negative semidefinite and $\overrightarrow{b}$ is in its image), the range is $(-\mathrm{\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}{\overrightarrow{b}}^T{A}^{-1}\overrightarrow{b}$, attained at $\frac{-1}{2}{A}^{-1}\overrightarrow{b}$ If $A$ is positive semidefinite but not positive definite, it depends on whether $\overrightarrow{b}$ is in the image of $A$. If yes, replace $A^{-1}\overrightarrow{b}$ with the solution $\overrightarrow{v}$ to $A\overrightarrow{v}=\overrightarrow{b}$, so we get a local minimum of $c-\frac{1}{4}{\overrightarrow{b}}^T\overrightarrow{v}$ attained at $\frac{-1}{2}\overrightarrow{v}$ If $A$ is not positive semidefinite or if $\overrightarrow{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 semidefinite, then $c-\frac{1}{4}{\overrightarrow{b}}^T{A}^{-1}\overrightarrow{b}$, attained at $\frac{-1}{2}{A}^{-1}\overrightarrow{b}$, where $A=-M^{T}M$ If $A$ is negative semidefinite but not negative definite, it depends on whether $\overrightarrow{b}$ is in the image of $A$. If yes, replace $A^{-1}\overrightarrow{b}$ with the solution $\overrightarrow{v}$ to $A\overrightarrow{v}=\overrightarrow{b}$, so we get a local minimum of $c-\frac{1}{4}{\overrightarrow{b}}^T\overrightarrow{v}$ attained at $\frac{-1}{2}\overrightarrow{v}$ If $A$ is not positive semidefinite or if $\overrightarrow{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 negative definite case corresponds to $a<0$, and there is no minimum in this case.

Differentiation

Partial derivatives and gradient vector

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}=(\sum _{j=1}^n(a_{ij}+a_{ji})x_j)+b_i$

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

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

In the case that $A$ is a symmetric matrix, this simplifies to:

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

Hessian matrix

The Hessian matrix of the quadratic function is the matrix $A+A^T$. In the case that $A$ is symmetric, this simplifies to $2A$.

Higher derivatives

All the higher derivative tensors are zero.

Cases

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^{T}M$

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

We can "complete the square" for this function:

$f(\overrightarrow{x})={(M\overrightarrow{x}+\frac{1}{2}(M^T{)}^{-1}\overrightarrow{b})}^T(M\overrightarrow{x}+\frac{1}{2}(M^T{)}^{-1}\overrightarrow{b})+(c-\frac{1}{4}{\overrightarrow{b}}^T{A}^{-1}\overrightarrow{b})$

In other words:

$f(\overrightarrow{x})={\Vert M\overrightarrow{x}+\frac{1}{2}(M^T{)}^{-1}\overrightarrow{b}\Vert }^2+(c-\frac{1}{4}{\overrightarrow{b}}^T{A}^{-1}\overrightarrow{b})$

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

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

Simplifying, we obtain that we minimum occurs at:

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

Moreover, the value of the minimum is:

$c-\frac{1}{4}{\overrightarrow{b}}^T{A}^{-1}\overrightarrow{b}$