5.1. Differentiation

We consider functions from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$.

5.1.1. Differentiability and Jacobian

Definition 5.1 (Differentiability at a point)

Let $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$. Let $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$. The function $f$ is differentiable at $\mathbf{x}$ if there exists a matrix $Df(\mathbf{x})\in {\mathbb{R}}^{m\times n}$ that satisfies

(5.1)$$\underset{\mathbf{z}\in \mathrm{dom}f,\mathbf{z}\ne \mathbf{x},\mathbf{z}\to \mathbf{x}}{lim}\frac{\Vert f(\mathbf{z})-f(\mathbf{x})-Df(\mathbf{x})(\mathbf{z}-\mathbf{x}){\Vert }_2}{\Vert \mathbf{z}-\mathbf{x}{\Vert }_2}=0.$$

Such a matrix $Df(\mathbf{x})$ is called the derivative (or Jacobian) of $f$ at $\mathbf{x}$.

There can be at most one $Df(\mathbf{x})$ satisfying the limit in (5.1).

Observation 5.1

If we write $\mathbf{z}=\mathbf{x}+\mathbf{h}$ then an alternative form for (5.1) is given by:

$$\underset{\mathbf{x}+\mathbf{h}\in \mathrm{dom}f,\mathbf{h}\ne \mathbf{0},\mathbf{h}\to \mathbf{0}}{lim}\frac{\Vert f(\mathbf{x}+\mathbf{h})-f(\mathbf{x})-Df(\mathbf{x})\mathbf{h}{\Vert }_2}{\Vert \mathbf{h}{\Vert }_2}=0.$$

The matrix $Df(\mathbf{x})$ can be obtained from the partial derivatives:

$$Df(\mathbf{x}{)}_{ij}=\frac{\partial f_i(\mathbf{x})}{\partial x_j},i=1,\dots ,m,j=1,\dots ,n.$$

$$\begin{array}{r}Df(\mathbf{x})=\left[\begin{array}{cccc}\frac{\partial f_1(\mathbf{x})}{\partial x_1}& \frac{\partial f_1(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_1(\mathbf{x})}{\partial x_n}\\ \frac{\partial f_2(\mathbf{x})}{\partial x_1}& \frac{\partial f_2(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_2(\mathbf{x})}{\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial f_m(\mathbf{x})}{\partial x_1}& \frac{\partial f_m(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_m(\mathbf{x})}{\partial x_n}\end{array}\right].\end{array}$$

1. The Jacobian $Df(\mathbf{x})$ is an $m\times n$ real matrix.

2. Partial derivatives of each component of $f$ (i.e., $f_i$) line up on the $i$-th row.

3. Partial derivatives for one coordinate $x_j$ line up on the $j$-th column.

4. If $f$ is single valued, then the Jacobian $Df(\mathbf{x})$ is a row vector.

Example 5.1 (Jacobian of identity function)

Let $f:{\mathbb{R}}^n\to {\mathbb{R}}^n$ be defined as:

$$f(\mathbf{x})=\mathbf{x}.$$

Then, $f_i(\mathbf{x})=x_i$. Hence,

$$\frac{\partial f_i(\mathbf{x})}{\partial x_j}=\delta (i,j).$$

Thus

$$Df(\mathbf{x})={\mathbf{I}}_n$$

the $n\times n$ identity matrix.

Example 5.2 (Jacobian of linear transformation)

Let $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be defined as:

$$f(\mathbf{x})=\mathbf{A}\mathbf{x}$$

where $\mathbf{A}=(a_{ij})$ is an $m\times n$ real matrix.

Then, $f_i(\mathbf{x})=\sum _{j=1}^n{a}_{ij}{x}_j$. Hence,

$$\frac{\partial f_i(\mathbf{x})}{\partial x_j}=a_{ij}.$$

Thus

$$Df(\mathbf{x})=\mathbf{A}.$$

Example 5.3 (Jacobian of affine transformation)

Let $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be defined as:

$$f(\mathbf{x})=\mathbf{A}\mathbf{x}+\mathbf{b}$$

where $\mathbf{A}=(a_{ij})\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$.

Then, $f_i(\mathbf{x})=\sum _{j=1}^n{a}_{ij}{x}_j+b_i$. Hence,

$$\frac{\partial f_i(\mathbf{x})}{\partial x_j}=a_{ij}.$$

Thus

$$Df(\mathbf{x})=\mathbf{A}.$$

The vector $\mathbf{b}$ is a constant offset. It has no impact on the derivative.

Definition 5.2 (Differentiable function)

A function $f$ is called differentiable if its domain $\mathrm{dom}f$ is open and it is differentiable at every point of $\mathrm{dom}f$.

Definition 5.3 (First order approximation)

The affine function given by:

(5.2)$$\hat{f}(\mathbf{x})=f(\mathbf{a})+Df(\mathbf{a})(\mathbf{x}-\mathbf{a})$$

is called the first order approximation of $f$ at $\mathbf{x}=\mathbf{a}\in \mathrm{int}\mathrm{dom}f$.

5.1.2. Real Valued Functions

Rest of this section focuses mostly on real valued functions of type $f:{\mathbb{R}}^n\to \mathbb{R}$.

1. First order derivative of a real valued function is called a gradient.

2. Second order derivative of a real valued function is called a Hessian.

3. We consider first order and second order approximations of a real valued function.

5.1.3. Gradient

Definition 5.4 (Gradient)

When $f:{\mathbb{R}}^n\to \mathbb{R}$ is a real valued function, then the derivative $Df(\mathbf{x})$ is a $1\times n$ matrix. The gradient of a real valued function is defined as:

$$\mathrm{\nabla }f(\mathbf{x})=Df(\mathbf{x}{)}^T$$

at $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$ if $f$ is differentiable at $\mathbf{x}$.

For real valued functions, the derivative is a row vector but the gradient is a column vector.

The components of the gradient are given by the partial derivatives as:

$$\mathrm{\nabla }f(\mathbf{x}{)}_i=\frac{\partial f(\mathbf{x})}{\partial x_i},i=1,\dots ,n.$$

Example 5.4 (Gradient of linear functional)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a linear functional given by:

$$f(\mathbf{x})=⟨\mathbf{x},\mathbf{a}⟩={\mathbf{a}}^T\mathbf{x}.$$

We can expand it as:

$$f(\mathbf{x})=\sum _{j=1}^n{a}_j{x}_j.$$

Computing partial derivative with respect to $x_i$, we get:

$$\frac{\partial f(\mathbf{x})}{\partial x_i}=\frac{\partial }{\partial x_i}\left(\sum _{j=1}^n{a}_j{x}_j\right)=a_i.$$

Putting the partial derivatives together, we get:

$$\mathrm{\nabla }f(\mathbf{x})=\mathbf{a}.$$

Example 5.5 (Gradient of affine functional)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a affine functional given by:

$$f(\mathbf{x})={\mathbf{a}}^T\mathbf{x}+b$$

where $\mathbf{a}\in {\mathbb{R}}^n$ and $b\in \mathbb{R}$.

We can expand it as:

$$f(\mathbf{x})=\sum _{j=1}^n{a}_j{x}_j+b.$$

Computing partial derivative with respect to $x_i$, we get:

$$\frac{\partial f(\mathbf{x})}{\partial x_i}=\frac{\partial }{\partial x_i}(\sum _{j=1}^n{a}_j{x}_j+b)=a_i.$$

Putting the partial derivatives together, we get:

$$\mathrm{\nabla }f(\mathbf{x})=\mathbf{a}.$$

The intercept $b$ is a constant term which doesn’t affect the gradient.

Example 5.6 (Gradient of quadratic form)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a quadratic form given by:

$$f(\mathbf{x})={\mathbf{x}}^T\mathbf{A}\mathbf{x}$$

where $\mathbf{A}\in {\mathbb{R}}^{n\times n}$.

We can expand it as:

$$f(\mathbf{x})=\sum _{i=1}^n\sum _{j=1}^n{x}_i{a}_{ij}{x}_j.$$

Note that the diagonal elements $a_{ii}$ give us terms of the form $a_{ii}{x}_i^2$. Let us split the expression into diagonal and non-diagonal terms:

$$\begin{array}{r}f(\mathbf{x})=\sum _{i=1}^n{a}_{ii}{x}_i^2+\sum _{\begin{array}{c}i,j\\ i\ne j\end{array}}{x}_i{a}_{ij}{x}_j.\end{array}$$

There are $n$ terms in the first sum (the diagonal entries of $\mathbf{A}$) and $n^2-n$ terms in the second sum (the non-diagonal entries of $\mathbf{A}$).

Taking partial derivative w.r.t. $x_k$, we obtain:

$$\begin{array}{r}\frac{\partial f(\mathbf{x})}{\partial x_k}=2a_{kk}{x}_k+\sum _{\begin{array}{c}i\\ i\ne k\end{array}}{x}_i{a}_{ik}+\sum _{\begin{array}{c}j\\ j\ne k\end{array}}{a}_{kj}{x}_j.\end{array}$$

• The first term comes from $a_{kk}$ term that is quadratic in $x_k$.

• The first sum comes from linear terms where $k=j$ and $i=1,\dots ,n$ except $i\ne k$.

• The second sum comes from linear terms where $k=i$ and $j=1,\dots ,n$ except $j\ne k$.

• There are $2n-2$ terms in the sums and $2$ $a_{kk}{x}_k$ terms.

• We can move one $a_{kk}{x}_k$ into each sum to simplify the partial derivative as:

$$\frac{\partial f(\mathbf{x})}{\partial x_k}=\sum _{i=1}^n{x}_i{a}_{ik}+\sum _{j=1}^n{a}_{kj}{x}_j.$$

Note that the $k$-th component of the vector $\mathbf{u}=\mathbf{A}\mathbf{x}$ is $\sum _{j=1}^n{a}_{kj}{x}_j$.

Similarly, the $k$-th component of the vector $\mathbf{v}={\mathbf{A}}^T\mathbf{x}$ is $\sum _{i=1}^n{a}_{ik}{x}_i$.

Thus,

$$\frac{\partial f(\mathbf{x})}{\partial x_k}=v_k+u_k.$$

Putting together the partial derivatives, we obtain:

$$\mathrm{\nabla }f(\mathbf{x})=\mathbf{v}+\mathbf{u}={\mathbf{A}}^T\mathbf{x}+\mathbf{A}\mathbf{x}=({\mathbf{A}}^T+\mathbf{A})\mathbf{x}=(\mathbf{A}+{\mathbf{A}}^T)\mathbf{x}.$$

If $\mathbf{A}$ is symmetric then,

$$\mathrm{\nabla }f(\mathbf{x})=2\mathbf{A}\mathbf{x}.$$

Example 5.7 (Gradient of squared ${\ell }_2$ norm)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a quadratic form given by:

$$f(\mathbf{x})=\Vert \mathbf{x}{\Vert }_2^2={\mathbf{x}}^T\mathbf{x}.$$

We can write this as

$$f(\mathbf{x})={\mathbf{x}}^T\mathbf{I}\mathbf{x}$$

where $\mathbf{I}$ is the identity matrix.

Following, Example 5.6,

$$\mathrm{\nabla }f(\mathbf{x})=2\mathbf{I}\mathbf{x}=2\mathbf{x}.$$

Example 5.8 (Gradient of quadratic functional)

Let $\mathbf{P}\in {\mathbb{S}}^n$ be a symmetric matrix. Let $\mathbf{q}\in {\mathbb{R}}^n$ and $r\in \mathbb{R}$. Consider the quadratic functional $f:{\mathbb{R}}^n\to \mathbb{R}$ given as:

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{P}\mathbf{x}+{\mathbf{q}}^T\mathbf{x}+r.$$

We can compute the gradient as follows:

$$\begin{array}{rl}\mathrm{\nabla }f(\mathbf{x})& =\mathrm{\nabla }(\frac{1}{2}{\mathbf{x}}^T\mathbf{P}\mathbf{x}+{\mathbf{q}}^T\mathbf{x}+r)\\ & =\frac{1}{2}\mathrm{\nabla }({\mathbf{x}}^T\mathbf{P}\mathbf{x})+\mathrm{\nabla }({\mathbf{q}}^T\mathbf{x})+\mathrm{\nabla }r\\ & =\frac{1}{2}(\mathbf{P}+{\mathbf{P}}^T)\mathbf{x}+\mathbf{q}\\ & =\frac{1}{2}(\mathbf{P}+\mathbf{P})\mathbf{x}+\mathbf{q}\\ & =\mathbf{P}\mathbf{x}+\mathbf{q}.\end{array}$$

• We took advantage of the fact that gradient operation commutes with scalar multiplication and distributes on vector addition.

• Since $r$ is a constant, it has no contribution to the derivative.

• We reused results from previous examples.

• We utilized the fact that $\mathbf{P}={\mathbf{P}}^T$ since $\mathbf{P}$ is symmetric.

In summary:

$$\mathrm{\nabla }f(\mathbf{x})=\mathbf{P}\mathbf{x}+\mathbf{q}.$$

The derivative of $f$ is then obtained by taking the transpose of the gradient:

$$Df(\mathbf{x})={\mathbf{x}}^T\mathbf{P}+{\mathbf{q}}^T.$$

Definition 5.5 (Gradient mapping)

If a real valued function $f:{\mathbb{R}}^n\to \mathbb{R}$ is differentiable, the gradient mapping of $f$ is the function $\mathrm{\nabla }f:{\mathbb{R}}^n\to {\mathbb{R}}^n$ with $\mathrm{dom}\mathrm{\nabla }f=\mathrm{dom}f$, with the value $\mathrm{\nabla }f(\mathbf{x})$ at every $\mathbf{x}\in \mathrm{dom}f$.

5.1.4. Continuous Differentiability

Definition 5.6 (Continuously differentiable real valued function)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function with $S=\mathrm{dom}f$. Let $U\subseteq S$ be an open set. If all the partial derivatives of $f$ exist and are continuous at every $\mathbf{x}\in U$, then $f$ is called continuously differentiable over $U$.

If $f$ is continuously differentiable over an open set $U\subseteq S$, then it is continuously differentiable over every subset $C\subseteq U$.

If $S$ is open itself and $f$ is continuously differentiable over $S$, then $f$ is called continuously differentiable.

5.1.5. First Order Approximation

Definition 5.7 (First order approximation of real valued functions)

The affine function given by:

(5.3)$$\hat{f}(\mathbf{x})=f(\mathbf{a})+\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})$$

is the first order approximation of a real valued function $f$ at $\mathbf{x}=\mathbf{a}\in \mathrm{int}\mathrm{dom}f$.

Theorem 5.1 (First order approximation accuracy)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be defined on an open set $S=\mathrm{dom}f$. Assume that $f$ is continuously differentiable on $S$. Then,

$$\underset{\mathbf{d}\to \mathbf{0}}{lim}\frac{f(\mathbf{x}+\mathbf{d})-f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{x}{)}^T\mathbf{d}}{\Vert \mathbf{d}\Vert }=0\mathrm{\forall }\mathbf{x}\in S.$$

Another way to write this result is:

$$f(\mathbf{x})=f(\mathbf{a})+\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})+o(\Vert \mathbf{x}-\mathbf{a}\Vert )$$

where $\mathbf{a}\in S$ and $o(\cdot ):{\mathbb{R}}_{+}\to \mathbb{R}$ is a one dimensional function satisfying $\frac{o(t)}{t}\to 0$ as $t\to 0^{+}$.

5.1.6. Chain Rule

Theorem 5.2 (Chain rule)

Suppose $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is differentiable at $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$ and $g:{\mathbb{R}}^m\to {\mathbb{R}}^p$ is differentiable at $f(\mathbf{x})\in \mathrm{int}\mathrm{dom}g$. Define the composition $h:{\mathbb{R}}^n\to {\mathbb{R}}^p$ as:

$$h(\mathbf{x})=g(f(\mathbf{x})).$$

Then, $h$ is differentiable at $\mathbf{x}$ with the derivative given by:

$$Dh(\mathbf{x})=Dg(f(\mathbf{x}))Df(\mathbf{x}).$$

Notice how the derivative lines up as a simple matrix multiplication.

Corollary 5.1 (Chain rule for real valued functions)

Suppose $f:{\mathbb{R}}^n\to \mathbb{R}$ is differentiable at $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$ and $g:\mathbb{R}\to \mathbb{R}$ is differentiable at $f(\mathbf{x})\in \mathrm{int}\mathrm{dom}g$. Define the composition $h:{\mathbb{R}}^n\to \mathbb{R}$ as:

$$h(\mathbf{x})=g(f(\mathbf{x})).$$

Then, $h$ is differentiable at $\mathbf{x}$ with the gradient given by:

$$\mathrm{\nabla }h(\mathbf{x})=g^{\prime }(f(\mathbf{x}))\mathrm{\nabla }f(\mathbf{x}).$$

Example 5.9 (Gradient of log-sum-exp)

Let $h:{\mathbb{R}}^n\to \mathbb{R}$ be given by:

$$h(\mathbf{x})=\ln (\sum _{i=1}^n\exp x_i)$$

with $\mathrm{dom}h={\mathbb{R}}^n$.

Let $g(y)=\ln y$ and

$$f(\mathbf{x})=\sum _{i=1}^n\exp x_i$$

Then, we can see that $h(\mathbf{x})=g(f(\mathbf{x}))$. Now $g^{\prime }(y)=\frac{1}{y}$ and

$$\begin{array}{r}\mathrm{\nabla }f(\mathbf{x})=\left[\begin{array}{c}\exp x_1\\ ⋮\\ \exp x_n\end{array}\right].\end{array}$$

Thus,

$$\begin{array}{r}\mathrm{\nabla }h(\mathbf{x})=\frac{1}{\sum _{i=1}^n\exp x_i}\left[\begin{array}{c}\exp x_1\\ ⋮\\ \exp x_n\end{array}\right].\end{array}$$

Now, if we define

$$\begin{array}{r}\mathbf{z}=\left[\begin{array}{c}\exp x_1\\ ⋮\\ \exp x_n\end{array}\right]\end{array}$$

then, we see that:

$${\mathbf{1}}^T\mathbf{z}=\sum _{i=1}^n\exp x_i.$$

Using this notation:

$$\mathrm{\nabla }h(\mathbf{x})=\frac{1}{{\mathbf{1}}^T\mathbf{z}}\mathbf{z}.$$

Example 5.10 (Gradient of ${\ell }_2$ norm at nonzero vectors)

Let $h:{\mathbb{R}}^n\to \mathbb{R}$ be given by:

$$h(\mathbf{x})=\Vert \mathbf{x}{\Vert }_2=\sqrt{⟨\mathbf{x},\mathbf{x}⟩}$$

with $\mathrm{dom}h={\mathbb{R}}^n$.

Let $g:\mathbb{R}\to \mathbb{R}$ with $\mathrm{dom}g={\mathbb{R}}_{+}$ be given by $g(y)=\sqrt{y}$.

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ with $\mathrm{dom}f={\mathbb{R}}^n$ be given by

$$f(\mathbf{x})=⟨\mathbf{x},\mathbf{x}⟩=\sum _{i=1}^n{x}_i^2=\Vert \mathbf{x}{\Vert }_2^2.$$

Then, we can see that $h(\mathbf{x})=g(f(\mathbf{x}))$ or $h=g\circ f$.

$g$ is differentiable on the open set ${\mathbb{R}}_{++}$. For every $y\in {\mathbb{R}}_{++}$,

$$g^{\prime }(y)=\frac{1}{2\sqrt{y}}$$

and (from Example 5.7)

$$\mathrm{\nabla }f(\mathbf{x})=2\mathbf{x}.$$

Thus, for every $\mathbf{x}\ne \mathbf{0}$, following Corollary 5.1,

$$\mathrm{\nabla }h(\mathbf{x})=g^{\prime }(f(\mathbf{x}))\mathrm{\nabla }f(\mathbf{x})=\frac{1}{2\sqrt{\Vert \mathbf{x}{\Vert }_2^2}}2\mathbf{x}=\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_2}.$$

The gradient of ${\ell }_2$ norm at $\mathbf{0}$ doesn’t exist. However, subgradients can be computed. See Example 9.71 and Example 9.72.

Corollary 5.2 (Chain rule for composition with affine function)

Suppose $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is differentiable. Let $\mathbf{A}\in {\mathbb{R}}^{n\times p}$ and $\mathbf{b}\in {\mathbb{R}}^n$. Define $g:{\mathbb{R}}^p\to {\mathbb{R}}^m$ as:

$$g(\mathbf{x})=f(\mathbf{A}\mathbf{x}+\mathbf{b})$$

with $\mathrm{dom}g=\{\mathbf{x}|\mathbf{A}\mathbf{x}+\mathbf{b}\in \mathrm{dom}f\}$.

The derivative of $g$ at $\mathbf{x}\in \mathrm{int}\mathrm{dom}g$ is given by:

$$Dg(\mathbf{x})=Df(\mathbf{A}\mathbf{x}+\mathbf{b})A.$$

If $f$ is real valued (i.e. $m=1$), then the gradient of a composition of a function with an affine function is given by:

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

Example 5.11 (Chain rule for restriction on a line)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued differentiable function. Consider the restriction of $f$ on a line in its domain

$$g(t)=f(\mathbf{x}+t\mathbf{v})$$

where $\mathbf{x}\in \mathrm{dom}f$ and $\mathbf{v}\in {\mathbb{R}}^n$ with the domain

$$\mathrm{dom}g=\{t|\mathbf{x}+t\mathbf{v}\in \mathrm{dom}f\}.$$

If we define $h:\mathbb{R}\to {\mathbb{R}}^n$ as:

$$h(t)=\mathbf{x}+t\mathbf{v};$$

we can see that:

$$g(t)=f(h(t))$$

By chain rule:

$$g^{\prime }(t)=Df(h(t))Dh(t)=\mathrm{\nabla }f(h(t){)}^T\mathbf{v}=\mathrm{\nabla }f(\mathbf{x}+t\mathbf{v}{)}^T\mathbf{v}.$$

In particular, if $\mathbf{v}=\mathbf{y}-\mathbf{x}$, with $\mathbf{y}\in \mathrm{dom}f$,

$$g^{\prime }(t)=\mathrm{\nabla }f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}){)}^T(\mathbf{y}-\mathbf{x})=\mathrm{\nabla }f(t\mathbf{y}+(1-t)\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x}).$$

5.1.7. Hessian

In this section, we review the second derivative of a real valued function $f:{\mathbb{R}}^n\to \mathbb{R}$.

Definition 5.8 (Hessian)

The second derivative or Hessian matrix of $f$ at $\mathbf{x}\in \mathrm{int}\mathrm{dom}f$, denoted by ${\mathrm{\nabla }}^{2}f$, is given by:

$${\mathrm{\nabla }}^{2}f(\mathbf{x}{)}_{ij}=\frac{{\partial }^{2}f(\mathbf{x})}{\partial x_i\partial x_j},i=1,\dots ,nj=1,\dots ,n$$

provided $f$ is twice differentiable at $\mathbf{x}$.

Example 5.12 (Hessian of linear functional)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a linear functional given by:

$$f(\mathbf{x})=⟨\mathbf{x},\mathbf{a}⟩={\mathbf{a}}^T\mathbf{x}.$$

We can expand it as:

$$f(\mathbf{x})=\sum _{j=1}^n{a}_j{x}_j.$$

Computing partial derivative with respect to $x_i$, we get:

$$\frac{\partial f(\mathbf{x})}{\partial x_i}=\frac{\partial }{\partial x_i}\left(\sum _{j=1}^n{a}_j{x}_j\right)=a_i.$$

If we further compute the partial derivative w.r.t. $x_j$, we get:

$$\frac{{\partial }^{2}f(\mathbf{x})}{\partial x_i\partial x_j}=\frac{\partial a_i}{\partial x_j}=0.$$

Thus, the Hessian is an $n\times n$ 0 matrix:

$${\mathrm{\nabla }}^{2}f(\mathbf{x})={\mathbf{O}}_n.$$

Theorem 5.3

Hessian is the derivative of the gradient mapping.

$$D\mathrm{\nabla }f(\mathbf{x})={\mathrm{\nabla }}^{2}f(\mathbf{x}).$$

Example 5.13 (Hessian of quadratic form)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a quadratic form given by:

$$f(\mathbf{x})={\mathbf{x}}^T\mathbf{A}\mathbf{x}$$

where $\mathbf{A}\in {\mathbb{R}}^{n\times n}$.

Recall from Example 5.6 that:

$$\mathrm{\nabla }f(\mathbf{x})=({\mathbf{A}}^T+\mathbf{A})\mathbf{x}.$$

Also recall from Example 5.2 that

$$D(\mathbf{C}\mathbf{x})=\mathbf{C}$$

for all $\mathbf{C}\in {\mathbb{R}}^{m\times n}$.

Thus, using Theorem 5.3

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=D\mathrm{\nabla }f(\mathbf{x})=D(({\mathbf{A}}^T+\mathbf{A})\mathbf{x})={\mathbf{A}}^T+\mathbf{A}.$$

If $\mathbf{A}$ is symmetric then

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=2\mathbf{A}.$$

Example 5.14 (Hessian of log-sum-exp)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by:

$$f(\mathbf{x})=\ln \left(\sum _{i=1}^n{e}^{x_i}\right)$$

with $\mathrm{dom}f={\mathbb{R}}^n$.

Define

$$\begin{array}{r}\mathbf{z}=\left[\begin{array}{c}{e}^{x_1}\\ ⋮\\ e^{x_n}\end{array}\right]\end{array}$$

then, we see that:

$${\mathbf{1}}^T\mathbf{z}=\sum _{i=1}^n{e}^{x_i}.$$

Using this notation:

$$f(\mathbf{x})=\ln \left({\mathbf{1}}^T\mathbf{z}\right).$$

We have:

$$\frac{\partial z_i}{\partial x_i}=\frac{\partial }{\partial x_i}{e}^{x_i}=e^{x_i}=z_i.$$

$\frac{\partial z_j}{\partial x_i}=0$ for $i\ne j$. Now,

$$\begin{array}{rl}\frac{\partial }{\partial x_i}f(\mathbf{x})& =\frac{\partial }{\partial z_i}\ln \left({\mathbf{1}}^T\mathbf{z}\right)\cdot \frac{\partial z_i}{\partial x_i}\\ & =\frac{1}{{\mathbf{1}}^T\mathbf{z}}\frac{\partial }{\partial z_i}{\mathbf{1}}^T\mathbf{z}\cdot z_i\\ & =\frac{1}{{\mathbf{1}}^T\mathbf{z}}{z}_i.\end{array}$$

Proceeding to compute the second derivatives:

$$\begin{array}{rl}\frac{{\partial }^2}{\partial x_i\partial x_j}f(\mathbf{x})& =\frac{\partial }{\partial x_i}\left(\frac{1}{{\mathbf{1}}^T\mathbf{z}}{z}_j\right)\\ & =\frac{\partial }{\partial z_i}\left(\frac{1}{{\mathbf{1}}^T\mathbf{z}}{z}_j\right)\cdot \frac{\partial z_i}{\partial x_i}\\ & =\frac{{\mathbf{1}}^T\mathbf{z}{\delta }_{ij}-z_j}{({\mathbf{1}}^T\mathbf{z}{)}^2}\cdot z_i\\ & =\frac{{\mathbf{1}}^T\mathbf{z}{\delta }_{ij}{z}_i-z_i{z}_j}{({\mathbf{1}}^T\mathbf{z}{)}^2}\\ & =\frac{{\delta }_{ij}{z}_i}{{\mathbf{1}}^T\mathbf{z}}-\frac{z_i{z}_j}{({\mathbf{1}}^T\mathbf{z}{)}^2}.\end{array}$$

Now, note that $(\mathbf{z}{\mathbf{z}}^T{)}_{ij}=z_i{z}_j$. And, $(\mathrm{diag}(\mathbf{z}){)}_{ij}={\delta }_{ij}{z}_i$.

Thus,

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=\frac{1}{{\mathbf{1}}^T\mathbf{z}}\mathrm{diag}(\mathbf{z})-\frac{1}{({\mathbf{1}}^T\mathbf{z}{)}^2}\mathbf{z}{\mathbf{z}}^T.$$

Alternatively,

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=\frac{1}{({\mathbf{1}}^T\mathbf{z}{)}^2}(({\mathbf{1}}^T\mathbf{z})\mathrm{diag}(\mathbf{z})-\mathbf{z}{\mathbf{z}}^T).$$

Example 5.15 (Derivatives for least squares cost function)

Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$. Let $\mathbf{b}\in {\mathbb{R}}^n$. Consider the least squares cost function:

$$f(\mathbf{x})=\frac{1}{2}\Vert \mathbf{A}\mathbf{x}-\mathbf{b}{\Vert }_2^2.$$

Expanding it, we get:

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T{\mathbf{A}}^T\mathbf{A}\mathbf{x}-{\mathbf{b}}^T\mathbf{A}\mathbf{x}+\frac{1}{2}{\mathbf{b}}^T\mathbf{b}.$$

Note that ${\mathbf{A}}^T\mathbf{A}$ is symmetric. Using previous results, we obtain the gradient:

$$\mathrm{\nabla }f(\mathbf{x})={\mathbf{A}}^T\mathbf{A}\mathbf{x}-{\mathbf{A}}^T\mathbf{b}.$$

And the Hessian is:

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=D\mathrm{\nabla }f(\mathbf{x})={\mathbf{A}}^T\mathbf{A}.$$

Example 5.16 (Derivatives for quadratic over linear function)

Let $f:\mathbb{R}\times \mathbb{R}\to \mathbb{R}$ be given by:

$$f(x,y)=\frac{x^2}{y}$$

with $\mathrm{dom}f=\{(x,y)|y>0\}$.

The gradient is obtained by computing the partial derivatives w.r.t. $x$ and $y$:

$$\begin{array}{r}\mathrm{\nabla }f(x,y)=\left[\begin{array}{c}\frac{2x}{y}\\ \frac{-x^2}{y^2}\end{array}\right].\end{array}$$

The Hessian is obtained by computing second order partial derivatives:

$$\begin{array}{r}{\mathrm{\nabla }}^{2}f(x,y)=\left[\begin{array}{cc}\frac{2}{y}& \frac{-2x}{y^2}\\ \frac{-2x}{y^2}& \frac{2x^2}{y^3}\end{array}\right]=\frac{2}{y^3}\left[\begin{array}{cc}{y}^2& -xy\\ -xy& x^2\end{array}\right].\end{array}$$

5.1.8. Twice Continuous Differentiability

Definition 5.9 (Twice continuously differentiable real valued function)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be a real valued function with $S=\mathrm{dom}f$. Let $U\subseteq S$ be an open set. If all the second order partial derivatives of $f$ exist and are continuous at every $\mathbf{x}\in U$, then $f$ is called twice continuously differentiable over $U$.

If $f$ is twice continuously differentiable over an open set $U\subseteq S$, then it is twice continuously differentiable over every subset $C\subseteq U$.

If $S$ is open itself and $f$ is twice continuously differentiable over $S$, then $f$ is called twice continuously differentiable.

Theorem 5.4 (Symmetry of Hessian)

If $f:{\mathbb{R}}^n\to \mathbb{R}$ with $S=\mathrm{dom}f$ is twice continuously differentiable over a set $U\subseteq S$, then its Hessian matrix ${\mathrm{\nabla }}^{2}f(\mathbf{x})$ is symmetric at every $\mathbf{x}\in U$

5.1.9. Second Order Approximation

Theorem 5.5 (Linear approximation theorem)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ with $S=\mathrm{dom}f$ be twice continuously differentiable over an open set $U\subseteq S$. Let $\mathbf{x}\in U$. Let $r>0$ be such that $B(\mathbf{x},r)\subseteq U$. Then, for any $\mathbf{y}\in B(\mathbf{x},r)$, there exist $\mathbf{z}\in [\mathbf{x},\mathbf{y}]$ such that

$$f(\mathbf{y})-f(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x}{)}^T{\mathrm{\nabla }}^{2}f(\mathbf{z})(\mathbf{y}-\mathbf{x}).$$

Theorem 5.6 (Quadratic approximation theorem)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ with $S=\mathrm{dom}f$ be twice continuously differentiable over an open set $U\subseteq S$. Let $\mathbf{x}\in U$. Let $r>0$ be such that $B(\mathbf{x},r)\subseteq U$. Then, for any $\mathbf{y}\in B(\mathbf{x},r)$,

$$f(\mathbf{y})=f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x}{)}^T{\mathrm{\nabla }}^{2}f(\mathbf{x})(\mathbf{y}-\mathbf{x})+o(\Vert \mathbf{y}-\mathbf{x}{\Vert }^2).$$

Definition 5.10 (Second order approximation)

The second order approximation of $f$ at or near $\mathbf{x}=\mathbf{a}$ is the quadratic function defined by:

$$\hat{f}(\mathbf{x})=f(\mathbf{a})+\mathrm{\nabla }f(\mathbf{a}{)}^T(\mathbf{x}-\mathbf{a})+\frac{1}{2}(\mathbf{x}-\mathbf{a}{)}^T{\mathrm{\nabla }}^{2}f(\mathbf{a})(\mathbf{x}-\mathbf{a}).$$

5.1.10. Smoothness

5.1.10.1. Real Functions

Definition 5.11 (Class of continuous functions)

The class of continuous real functions, denoted by $C$, is the set of functions of type $f:\mathbb{R}\to \mathbb{R}$ which are continuous over their domain $\mathrm{dom}f$.

Definition 5.12 (Differentiability class $C^k$)

Let $f:\mathbb{R}\to \mathbb{R}$ be a real function with $S=\mathrm{dom}f$.

Then, we say that $f$ belongs to the differentiability class $C^k$ on $S$ if and only if

$$\frac{d^k}{d{x}^k}f(x)\in C.$$

In other words, the $k$-th derivative of $f$ exists and is continuous.

1. $C^0$ consists of class of continuous real functions.

2. $C^1$ consists of class of continuously differentiable functions.

3. $C^{\mathrm{\infty }}$ consists of class of smooth functions which are infinitely differentiable.

5.1.10.2. Real Valued Functions on Euclidean Space

Definition 5.13 (Differentiability class $C^k$)

A function $f:{\mathbb{R}}^n\to \mathbb{R}$ with $S=\mathrm{dom}f$ where $S$ is an open subset of ${\mathbb{R}}^n$ is said to be of class $C^k$ on $S$, for a positive integer $k$, if all the partial derivatives of $f$

$$\frac{{\partial }^{m}f}{\partial x_1^{m_1}\partial x_2^{m_2}\dots \partial x_n^{m_n}}(\mathbf{x})$$

exist and are continuous for every $m_1,m_2,\dots ,m_n\ge 0$ and $m=m_1+m_2+\dots m_n\le k$.

1. If $f$ is continuous, it is said to belong to $C$ or $C^0$.

2. If $f$ is continuously differentiable, it is said to belong to $C^1$.

3. If $f$ is twice continuously differentiable, it is said to belong to $C^2$.

4. If $f$ is infinitely differentiable, it is said to belong to $C^{\mathrm{\infty }}$.