Practical Methods of Optimization

Introduction - Home

Exercises: 1 - 2 - 3 - 4 - 5 - 6

Exercise. Obtain expressions for the gradient vector and Hessian matrix for the functions of $n$ variables:

(i)	$a^{T} x$ : $a$ constant;
(ii)	$x^{T} A x$ : $A$ unsymmetric and constant;
(iii)	$\frac{1}{2} x^{T} A x + b^{T} x$ : $A$ symmetric, $A$ , $b$ constant;
(iv)	$f^{T} f$ : $f$ is an $m$ -vector depending on $x$ and $\nabla f^{T}$ is denoted by $A$ which is not constant.

Solution.

(i)

\nabla (a^{T} x) = (\begin{matrix} \frac{\partial \sum_{i} a_{i} x_{i}}{\partial x_{1}} \\ ⋮ \\ \frac{\partial \sum_{i} a_{i} x_{i}}{\partial x_{n}} \end{matrix}) = (\begin{matrix} a_{1} \\ ⋮ \\ a_{n} \end{matrix}) = a

\nabla {(\nabla (a^{T} x))}^{T} = \nabla (a^{T}) = (\begin{matrix} \frac{\partial a_{1}}{\partial x_{1}} & \dots & \frac{\partial a_{n}}{\partial x_{1}} \\ ⋮ & \dots & ⋮ \\ \frac{\partial a_{1}}{\partial x_{n}} & \dots & \frac{\partial a_{n}}{\partial x_{n}} \end{matrix}) = 0

(ii)

\nabla (x^{T} A x) = (\begin{matrix} \frac{\partial \sum_{i} \sum_{j} x_{i} A_{i j} x_{j}}{\partial x_{1}} \\ ⋮ \\ \frac{\partial \sum_{i} \sum_{j} x_{i} A_{i j} x_{j}}{\partial x_{n}} \end{matrix}) = (\begin{matrix} \sum_{j} A_{1 j} x_{j} + \sum_{i} x_{i} A_{i 1} \\ ⋮ \\ \sum_{j} A_{n j} x_{j} + \sum_{i} x_{i} A_{i n} \end{matrix}) = (A + A^{T}) \cdot x

The Hessian matrix is then:

\nabla (\nabla (x^{T} A x)) = \nabla {((A + A^{T}) \cdot x)}^{T} = (\begin{matrix} \frac{\partial \sum_{j} A_{1 j} x_{j} + \sum_{i} x_{i} A_{i 1}}{\partial x_{1}} & \dots & \frac{\partial \sum_{j} A_{n j} x_{j} + \sum_{i} x_{i} A_{i n}}{\partial x_{1}} \\ ⋮ & \dots & ⋮ \\ \frac{\partial \sum_{j} A_{1 j} x_{j} + \sum_{i} x_{i} A_{i 1}}{\partial x_{n}} & \dots & \frac{\partial \sum_{j} A_{n j} x_{j} + \sum_{i} x_{i} A_{i n}}{\partial x_{n}} \end{matrix}) = A + A^{T}

(iii) This is similar to the case above. We have that:

\nabla (\frac{1}{2} x^{T} A x + b^{T} x) = \frac{1}{2} (A + A^{T}) \cdot x + b

\nabla {(\nabla (\frac{1}{2} x^{T} A x + b^{T} x))}^{T} = \frac{1}{2} (A + A^{T})

Since $A$ is symmetric, then $A = A^{T}$ , hence,

\nabla (\frac{1}{2} x^{T} A x + b^{T} x) = A x + b

\nabla {(\nabla (\frac{1}{2} x^{T} A x + b^{T} x))}^{T} = A

(iv) We have that:

f^{T} f = \sum_{k} f_{k} {(x)}^{2}

\nabla (f^{T} f) = (\begin{matrix} \frac{\partial \sum_{k} f_{k}^{2} (x)}{\partial x_{1}} \\ ⋮ \\ \frac{\partial \sum_{k} f_{k}^{2} (x)}{\partial x_{m}} \end{matrix}) = 2 \sum_{k} f_{k} \nabla f_{k}

Since

A = (\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \dots & \frac{\partial f_{m}}{\partial x_{1}} \\ ⋮ & \dots & ⋮ \\ \frac{\partial f_{1}}{\partial x_{m}} & \dots & \frac{\partial f_{m}}{\partial x_{m}} \end{matrix})

then

\nabla (f^{T} f) = 2 A f

For the Hessian:

H = \nabla {(\nabla (f^{T} f))}^{T} = 2 \nabla {(A f)}^{T}