Objective functions gradients and minima

What an optimizer looks for

An optimisation problem has a number to make small, the objective $f(\mathbf w)$ , and variables $\mathbf w$ that you are free to change. The objective can be a least-squares loss, the variance $\mathbf w^{T}\Sigma\mathbf w$ of a portfolio, or the gap between model prices and market prices in a calibration. Making something large is the same problem with the sign flipped, because maximising $f$ is minimising $-f$ .

\nabla f(\mathbf w)=\Big(\frac{\partial f}{\partial w_1},\dots,\frac{\partial f}{\partial w_n}\Big),\qquad H_{ij}=\frac{\partial^{2} f}{\partial w_i\,\partial w_j}

(1)

The gradient points in the direction in which $f$ rises fastest, so $-\nabla f$ is the direction of steepest descent. At a minimum the gradient is zero, which is the first-order condition. A zero gradient alone is not enough, because maxima and saddle points have it too. The Hessian $H$ tells them apart: if $H$ is positive definite (all eigenvalues positive) the point is a local minimum, if it is negative definite a maximum, and if it has eigenvalues of both signs the point is a saddle.

A two-variable exampleTake

f(x,y)=(x-1)^2+2(y+2)^2

. Then

\nabla f=(2(x-1),\,4(y+2))

. At the point

(3,0)

the gradient is

(4,8)

, so moving against it lowers

f

. The gradient is zero only at

(1,-2)

. There

H=\mathrm{diag}(2,4)

has positive eigenvalues, so

(1,-2)

is the minimum and

f=0

at it.

Stationary point: $\nabla f=0$ . Necessary for a minimum, not sufficient.
Classification: positive definite $H$ means a local minimum, indefinite $H$ a saddle.
In one variable: $f'(x)=0$ with $f''(x)>0$ is a minimum.

Check your gradient numericallyMost optimisation bugs are wrong gradients. Compare your formula with the central difference

\big(f(x+h)-f(x-h)\big)/(2h)

for a small

h

such as

10^{-5}

: the two should agree to several digits. Do this once for every new objective before trusting a solver that uses it.

Lab · what's graded

A partial derivative15 pts
The length of the gradient15 pts
The minimum of a cubic15 pts
Classifying a stationary point15 pts
Match the vocabulary15 pts
Finding a minimum by hand10 pts
Why move against the gradient15 pts

What an optimizer looks for

\nabla f(\mathbf w)=\Big(\frac{\partial f}{\partial w_1},\dots,\frac{\partial f}{\partial w_n}\Big),\qquad H_{ij}=\frac{\partial^{2} f}{\partial w_i\,\partial w_j}

(1)

A two-variable exampleTake

f(x,y)=(x-1)^2+2(y+2)^2

. Then

\nabla f=(2(x-1),\,4(y+2))

. At the point

(3,0)

the gradient is

(4,8)

, so moving against it lowers

f

. The gradient is zero only at

(1,-2)

. There

H=\mathrm{diag}(2,4)

has positive eigenvalues, so

(1,-2)

is the minimum and

f=0

at it.

Stationary point: $\nabla f=0$ . Necessary for a minimum, not sufficient.
Classification: positive definite $H$ means a local minimum, indefinite $H$ a saddle.
In one variable: $f'(x)=0$ with $f''(x)>0$ is a minimum.

Check your gradient numericallyMost optimisation bugs are wrong gradients. Compare your formula with the central difference

\big(f(x+h)-f(x-h)\big)/(2h)

for a small

h

such as

10^{-5}

: the two should agree to several digits. Do this once for every new objective before trusting a solver that uses it.

Lab · what's graded

A partial derivative15 pts
The length of the gradient15 pts
The minimum of a cubic15 pts
Classifying a stationary point15 pts
Match the vocabulary15 pts
Finding a minimum by hand10 pts
Why move against the gradient15 pts

Objective functions gradients and minima

What an optimizer looks for

Lab · what's graded

Log in to run your code.

Objective functions gradients and minima

What an optimizer looks for

Lab · what's graded

Log in to run your code.