Optimisation

Multidimensional Taylor Series

The scalar case of the taylor series is an expansion of the function $f(x)$ about the point $x^{\ast }=a$:

$$f(x)=\sum _{n=0}^{\infty }\frac{1}{n!}{f}^{(n)}(a)(x-a{)}^n$$

This can be generalised to a matrix case. Let $f$ be a scalar function of a column vector $\mathbf{x}$. The taylor series expansion of $f(\mathbf{x})$ about the point ${\mathbf{x}}^{\ast }=\mathbf{a}$ is:

$$f(\mathbf{x})=\sum _{n=0}^{\infty }\frac{1}{n!}(\mathbf{x}-\mathbf{a}{)}^n({\partial }^{(n)}f)(\mathbf{a})$$

This result $f$ is a scalar. Consider the first three terms:

$$f(\mathbf{x})=\sum _{n=0}^{\infty }\frac{1}{n!}(\mathbf{x}-\mathbf{a}{)}^n({\partial }^{(n)}f)(\mathbf{a})=f(\mathbf{a})+\left(\frac{\partial f}{\partial \mathbf{x}}{|}_{\mathbf{x}=\mathbf{a}}\right)(\mathbf{x}-\mathbf{a})+\frac{1}{2!}(\mathbf{x}-\mathbf{a}{)}^{\prime }\left(\frac{{\partial }^{2}f}{\partial {\mathbf{x}}^2}{|}_{\mathbf{x}=\mathbf{a}}\right)(\mathbf{x}-\mathbf{a})$$

${\mathbf{g}}_{\mathbf{x}=\mathbf{a}}$ is a $1\times n$ row vector with it's gradient evaluated at the point $\mathbf{a}$:

$$\left(\frac{\partial f}{\partial \mathbf{x}}{|}_{\mathbf{x}=\mathbf{a}}\right)=\left[\begin{array}{cccc}\frac{\partial f}{\partial x_1}{|}_{\mathbf{x}=\mathbf{a}}& \frac{\partial f}{\partial x_2}{|}_{\mathbf{x}=\mathbf{a}}& \dots & \frac{\partial f}{\partial x_n}{|}_{\mathbf{x}=\mathbf{a}}\end{array}\right]$$

${\mathbf{H}}_{\mathbf{x}=\mathbf{a}}$ is the $n\times n$ matrix of second derivatives, called the Hessian matrix, evaluated at point $\mathbf{a}$

• The Hessian matrix is generally symmetric
• Matrix of mixed partial derivatives

$${\mathbf{H}}_{\mathbf{x}=\mathbf{a}}=\left(\frac{{\partial }^{2}f}{\partial {\mathbf{x}}^2}{|}_{\mathbf{x}=\mathbf{a}}\right)=\left[\frac{{\partial }^{2}f}{\partial x_i\partial x_j}{|}_{\mathbf{x}=\mathbf{a}}\right]$$

Taylor series can be used to approximate multidimensional functions:

• Let $S$ be a scalar function of an $n\times 1$ vector $\mathbf{x}$, $S(\mathbf{x})$
• Expand $S$ about a point $\mathbf{x}$, assuming displacements $\mathbf{h}$ about $\mathbf{x}$
• The first term is a linear form
• Second term a quadratic form
• Higher order terms are ignored

$$S(\mathbf{x}+\mathbf{h})=S(\mathbf{x})+{\mathbf{g}}_{\mathbf{x}}\mathbf{h}+\frac{1}{2}{\mathbf{x}}^{\prime }{\mathbf{H}}_{\mathbf{x}}\mathbf{h}+...$$

Multidimensional Optimisation

Optimisation tasks involve finding $\mathbf{x}$ such that $S$ is at an extremum (max/min).

Consider a continuous function $S(\mathbf{x})$, expanded about the point ${\mathbf{x}}_0$, with a vector $\mathbf{\zeta }$ as the displacement from ${\mathbf{x}}_0$:

$$S({\mathbf{x}}_0+\zeta )\approxeq S({\mathbf{x}}_0)+{\left(\frac{\partial S}{\partial \mathbf{x}}\right)}^{\prime }\zeta +\frac{1}{2}{\zeta }^{\prime }\left(\frac{{\partial }^{2}S}{\partial {\mathbf{x}}^2}\right)\zeta =S({\mathbf{x}}_0)+{\mathbf{g}}_{{\mathbf{x}}_0}^{\prime }\zeta +\frac{1}{2}{\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta$$

The point ${\mathbf{x}}_0$ is an extremum if the gradient vector ${\mathbf{g}}^{\prime }(\mathbf{x})=0$ when $\mathbf{x}={\mathbf{x}}_0$. The homogenous nonlinear equation ${\mathbf{g}}^{\prime }({\mathbf{x}}_0)=0$ therefore defines an extremum ${\mathbf{x}}_0$.

If ${\mathbf{g}}^{\prime }({\mathbf{x}}_0)=0$, then:

$$S({\mathbf{x}}_0)+{\mathbf{g}}_{{\mathbf{x}}_0}^{\prime }\zeta +\frac{1}{2}{\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta ⟹S({\mathbf{x}}_0)+\frac{1}{2}{\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta$$

Therefore:

$$S({\mathbf{x}}_0+\zeta )-S({\mathbf{x}}_0)=\frac{1}{2}{\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta$$

This is the important result that defines the extremum of a function $\mathbf{S}(\mathbf{x})$

To determine the nature of the extremum, the sign of the ${\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta$ must be determined. By the spectral resolution, this is determined by the eigenvalues ${\lambda }_i$ of $\mathbf{H}$. It is said that the sign definiteness of $\mathbf{H}$ is determined by ${\lambda }_i$

Let $Q(\mathbf{x})$ be a quadratic form $Q(\mathbf{x})={\zeta }^{\prime }{\mathbf{H}}_{\mathbf{x}}\zeta$ m, where $H$ is a symmetric $n\times n$ matrix. The eigenvalues of $\mathbf{H}$ are ${\lambda }_1,{\lambda }_2,...,{\lambda }_n$. The definiteness is determined by all of the eigenvalues:

Extrema of a Multivariate Quadratic

For a quadratic $Q(\mathbf{x})={\mathbf{x}}^{\prime }\mathbf{Ax}+{\mathbf{b}}^{\prime }\mathbf{x}+\mathbf{c}$, the extremum is at the point where $\frac{\partial Q}{\partial \mathbf{x}}=0$:

$$\frac{\partial Q}{\partial \mathbf{x}}=2{\mathbf{x}}^{\prime }\mathbf{A}+{\mathbf{b}}^{\prime }=0$$

$$2{\mathbf{Ax}}_0=-\mathbf{b}$$

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

A maximum/minimum exists at the point ${\mathbf{x}}_0$ if the matrix $\mathbf{A}$ is positive/negative definite.

Example 1

Find the extremum (and it's nature) of the quadratic function:

$$f(x_1,x_2)=4x_1^2+2x_1{x}_2-x_1+2x_2+1$$

Put into matrix form:

$$f(\mathbf{x})=={\mathbf{x}}^{\prime }{\mathbf{A}}^{\prime }\mathbf{x}+{\mathbf{b}}^{\prime }\mathbf{x}+1={\mathbf{x}}^{\prime }\left[\begin{array}{cc}4& 1\\ 1& 0\end{array}\right]\mathbf{x}+\left[\begin{array}{cc}-1& 2\end{array}\right]\mathbf{x}+1$$

The extremum of this quadratic form exists at the point ${\mathbf{x}}_0$ where:

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

$${\mathbf{A}}^{-1}=\left[\begin{array}{cc}0& 1\\ 1& -4\end{array}\right]$$

$${\mathbf{x}}_0=-\frac{1}{2}{\mathbf{A}}^{-1}\mathbf{b}=-\frac{1}{2}\left[\begin{array}{cc}0& 1\\ 1& -4\end{array}\right]\left[\begin{array}{c}-1\\ 2\end{array}\right]=\left[\begin{array}{c}-1\\ 4.5\end{array}\right]$$

$${\mathbf{x}}_0=\left[\begin{array}{c}-1\\ 4.5\end{array}\right]$$

To determine the nature, find the eigenvalues of $\mathbf{A}$:

$${\lambda }_1=4.235{\lambda }_2=-0.236$$

The eigenvalues lie either side of zero, which makes $\mathbf{A}$ indefinite, and the extremum is therefore a saddle point.

Example 2

Find the stationary points (and their nature) for the function:

$f(\mathbf{x})=f(x_1,x_2)=x_1^2+3x_1{x}_2^2-x_2^3+4$

The stationary points lie where $g({\mathbf{x}}_0)=0$:

$$g(\mathbf{x})=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\end{array}\right]=\left[\begin{array}{c}2x_1+3x_2^2\\ 6x_1{x}_2-3x_2^2\end{array}\right]$$

The solutions are therefore:

$$\left[\begin{array}{c}2x_1+3x_2^2\\ 6x_1{x}_2-3x_2^2\end{array}\right]=0$$

$$\begin{gathered} 2x_1+3x_2^2=0 \\ 6x_1{x}_2-3x_2^2=0 \end{gathered}$$

Two solutions:

$${\mathbf{x}}_0=\left[\begin{array}{c}0\\ 0\end{array}\right]{\mathbf{x}}_0=\left[\begin{array}{c}-1/6\\ -1/3\end{array}\right]$$

To determine the nature of the extremum, we need the hessian matrix:

$$\mathbf{H}(\mathbf{x})=\left[\begin{array}{cc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_2{x}_1}\\ \frac{{\partial }^{2}f}{\partial x_1{x}_2}& \frac{{\partial }^{2}f}{\partial x_2^2}\end{array}\right]=\left[\begin{array}{cc}2& 6x_2\\ 6x_2& 6x_1-6x_2\end{array}\right]$$

The eigenvalues at each point will give the nature. For ${\mathbf{x}}_0=\left[\begin{array}{c}0\\ 0\end{array}\right]$:

$${\lambda }_1=0{\lambda }_2=2$$

The hessian matrix is positive semidefinite, so the point is probably a valley, but further analysis is required to determine the nature of the point.

For ${\mathbf{x}}_0=\left[\begin{array}{c}-1/6\\ -1/3\end{array}\right]$:

$${\lambda }_1=3.56{\lambda }_2=-0.56$$

The hessian matrix is indefinite, so the point is a saddle point.