Gradients

Directional derivatives

The behavior of a function $f:\mathbb R^n\to\mathbb R$ along the ray $\{x+αd\mid α\in\mathbb R_+\}$, where $x$ and $d$ are $n$-vectors, is given by the univariate function

From standard calculus, the derivative of $\phi$ at the origin, when it exists, is the limit

We thus arrive at the following definition.

It follows immediately from this definition that the partial derivatives of $f$ are simply the directional derivatives of $f$ along the each of the canonical unit direction $e_1,\ldots,e_n$, i.e.,

Descent directions

A nonzero vector $d$ is a descent direction of $f$ at $x$ if the directional derivative is negative:

It follows directly from the definition of the directional derivative that $f(x+αd) < f(x)$ for all positive $\alpha$ small enough.

Gradient vector

The gradient of the function $f$ is the collection of all the partial derivatives:

The gradient and directional derivative are related via the formula

If, for example, the direction $d$ to be the canonical unit direction $e_i$, then this formula reduces to

which confirms the identity (1).

Linear approximation

The gradient of a continuously differentiable function $f$ (i.e., $f$ is differentiable at all $x$ and $\nabla f$ is continuous) provides a local linear approximation of $f$ in the following sense:

The residual $\omicron:\mathbb R_+\to\mathbb R$ of the approximation decays faster than $\| d\|$, i.e.,

Example

Fortunately, there are good computational tools that automatically produce reliable gradients. Consider the 2-dimensional Rosenbrock function and its gradient:

Here is the code for $f$ and its gradient:

a, b = 1, 100
f(x) = (a - x[1])^2 + b*(x[2] - x[1]^2)^2
∇f(x) = [-2(a - x[1]) - 4b*(x[2] - x[1]^2)*x[1] , 2b*(x[2] - x[1]^2) ]

Instead of computing gradients by hand, as we did above, we can use automatic differentiation, such as implemented in the package ForwardDiff, to compute these.

using ForwardDiff
∇fad(x) = ForwardDiff.gradient(f, x)

The function ∇fad returns the value of the gradient at x. Let's compare the hand-computed gradient ∇f against that automatically-computed gradient ∇fad at a random point:

x = rand(2) 
∇f(x) == ∇fad(x)

true

Calculus rules

We derive calculus rules for linear and quadratic functions, which appear often in optimization.

Linear functions

Let $a\in\mathbb R^n$. The linear function

has the gradient $\nabla f(x) = a$, and so the gradient is constant. Here's a small example:

a = collect(1:5)
ForwardDiff.gradient(x->a'x, rand(5))

Quadratic functions

Let $A\in\mathbb R^{n\times n}$ be a square matrix. Consider the quadratic function

One way to derive the gradient of this function is to write out the quadratic function making explicit all of the coefficients in $A$. Here's another approach that uses the product rule:

where $a = Ax$ and $b:=A^T\! x$ are held fixed when applying the gradient. Because each of the functions in the right-hand side of this sum is a linear function, we can apply the calculus rule for linear functions to deduce that

(Recall that $A$ is square.) The matrix $\tfrac12(A+A^T\!)$ is the symmetric part of $A$. If $A$ is symmetric, i.e., $A = A^T\!$, then the gradient reduces to

But in optimization, we almost always assume that the matrix that defines the quadratic in (3) is symmetric because always $x^T\! Ax = \tfrac12 x^T\!(A+A^T\!)x$, and therefore we can instead work with the symmetric part of $A$.

Example (2-norm). Consider the two functions

The function $f_2$ is of the form (3) with $A=I$, and so $\nabla f_2(x) = x$. Use the chain rule to obtain the gradient of the $f_1$:

which isn't differentiable at the origin.

Visualizing gradients

Gradients can be understood geometrically in relation to the level-set of the function. The $α$-level set of a function $f:\mathbb R^n\to\mathbb R$ is the set of points that have an equal or lower value at $x$:

Fix any $x$ and consider the level set $[f≤f(x)]$. For any direction $d$ that's either a descent direction for $f$ or a tangent direction for $[f≤f(x)]$,

which implies that the gradient $\nabla f(x)$ is the outward normal to the level set.