4.3.3 Practice set: second-order methods

The Hessian and the quadratic copy

The Hessian and second-order Taylor expansion (lesson 4.3.1)

0 of 7 correct

1.
For $f(x, y) = x^2y^3$ , find $f_{xy}$ at $(1, 1)$
2.
$\nabla f(\mathbf{a}) = (1, -1)$ and $H = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix}$ . Estimate the second component of $\nabla f$ after the step $\mathbf{h} = (0.1, 0.2)$
3.
$f(\mathbf{a}) = 3$ , $\nabla f(\mathbf{a}) = (2, 0)$ and $H = \begin{pmatrix} 2 & -1 \\ -1 & 4 \end{pmatrix}$ . Evaluate the quadratic copy at the step $\mathbf{h} = (0.1, 0.2)$
4.
For $H = \begin{pmatrix} 2 & 3 \\ 3 & -4 \end{pmatrix}$ , find the second derivative of $f$ along the unit vector $\mathbf{u} = (0.8, 0.6)$
5.
For $f = xy$ at $(1, 2)$ with bump $\delta = 0.1$ , the corner values are $f_{++} = 2.31$ , $f_{+-} = 2.09$ , $f_{-+} = 1.89$ and $f_{--} = 1.71$ . Estimate $f_{xy}$
6.
A quadratic copy misses by 0.0008 at the step $0.2\,\mathbf{u}$ . Estimate its miss at $0.1\,\mathbf{u}$
7.
$f_{xx} = 2$ , $f_{xy} = 5$ and $f_{yy} = 0$ . Find the bend term $\frac{1}{2}\mathbf{h}^\top H\mathbf{h}$ at $\mathbf{h} = (1, 1)$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Critical points and the second-derivative test

Minima, maxima and saddle points (lesson 4.3.2)

0 of 7 correct

1.
The tilted bowl $x^2 + xy + y^2 - 3x$ has gradient $(2x + y - 3,\ x + 2y)$ . Find the $x$ -coordinate of its critical point
2.
At a critical point, $H = \begin{pmatrix} 2 & 3 \\ 3 & 2 \end{pmatrix}$ . Type 1 for a minimum, 2 for a maximum, 3 for a saddle
3.
$x^3 - 3x + y^3 - 3y$ has four critical points, at $x = \pm 1$ , $y = \pm 1$ . How many of them are saddles?
4.
Find the largest value of $4x + 2y - x^2 - y^2 + xy$
5.
At a critical point $\mathbf{a}$ , $H$ has eigenvalue 2 along the unit vector $\mathbf{q}$ . Estimate $f(\mathbf{a} + 0.1\mathbf{q}) - f(\mathbf{a})$
6.
$x^2 + y^4$ and $x^2 - y^4$ both have $\det H = 0$ at the origin. Which has a saddle there? Type 1 for $x^2 + y^4$ , 2 for $x^2 - y^4$
7.
At a point, $\nabla f = (0, 3)$ and $H$ is positive definite. Is it a local minimum? Type 1 for yes, 0 for no

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Coding exercise

Exercise

What kind of critical point?

Write classify(f, a, d=1e-4, tol=1e-4, grad_tol=1e-6). Here f takes a NumPy array of $n$ numbers and returns one number, and a is the point. Return one of the strings "not critical", "minimum", "maximum", "saddle" or "no verdict".

Turn a into a decimal array. Estimate each partial derivative by a central difference with bump d (lesson 4.1.2). If any has size above grad_tol, return "not critical".
Estimate $H$ by central differences with bump d: the four-corner formula of lesson 4.1.2 for every entry, as in lesson 4.3.1.
Take the eigenvalues of $\frac{1}{2}(H + H^\top)$ with np.linalg.eigvalsh. If any has size below tol, return "no verdict". Otherwise apply the test of lesson 4.3.2.

The tests use the cubic and example 2 of lesson 4.3.2, its three-variable function, a maximum in three variables and a minimum in four. They also try a point where $H$ is positive definite but the gradient is not 0, and $x^4 + y^2$ and $-x^4 + y^2$ at the origin.

See the tests

import numpy as np


def cubic(p):
    return p[0] ** 3 - 3 * p[0] + p[1] ** 2


def example2(p):
    return 6 * p[0] * p[1] - 2 * p[0] ** 3 - 3 * p[1] ** 2


def three(p):
    return p[0] ** 2 + p[1] ** 2 + p[2] ** 2 - p[0] * p[1] * p[2]


def test_minimum():
    """x³ − 3x + y² has a minimum at (1, 0)"""
    expect_equal(classify(cubic, [1, 0]), "minimum", what="classify(cubic, [1, 0])")


def test_saddle():
    """x³ − 3x + y² has a saddle at (−1, 0)"""
    expect_equal(classify(cubic, [-1, 0]), "saddle", what="classify(cubic, [-1, 0])")


def test_maximum():
    """6xy − 2x³ − 3y² has a maximum at (1, 1)"""
    expect_equal(classify(example2, [1, 1]), "maximum", what="classify(example2, [1, 1])")


def test_saddle_with_zero_corner():
    """6xy − 2x³ − 3y² has a saddle at (0, 0), where f_xx = 0"""
    expect_equal(classify(example2, [0, 0]), "saddle", what="classify(example2, [0, 0])")


def test_not_critical():
    """At (1, 1) the cubic's Hessian is positive definite, but the gradient is (0, 2): not critical"""
    expect_equal(classify(cubic, [1, 1]), "not critical", what="classify(cubic, [1, 1])")


def test_three_variables():
    """x² + y² + z² − xyz: a minimum at the origin and a saddle at (2, 2, 2)"""
    expect_equal(classify(three, [0, 0, 0]), "minimum", what="classify(three, [0, 0, 0])")
    expect_equal(classify(three, [2, 2, 2]), "saddle", what="classify(three, [2, 2, 2])")


def test_maximum_three_variables():
    """−x² − y² − z² + xy has a maximum at the origin"""
    f = lambda p: -p[0] ** 2 - p[1] ** 2 - p[2] ** 2 + p[0] * p[1]
    expect_equal(classify(f, [0, 0, 0]), "maximum", what="classify(-x² - y² - z² + xy, [0, 0, 0])")


def test_four_variables():
    """(x₁ − 1)² + (x₂ − 2)² + (x₃ − 3)² + (x₄ − 4)² has a minimum at (1, 2, 3, 4)"""
    f = lambda p: float(np.sum((np.asarray(p) - np.array([1, 2, 3, 4])) ** 2))
    expect_equal(classify(f, [1, 2, 3, 4]), "minimum", what="classify(sum of squares, [1, 2, 3, 4])")


def test_no_verdict():
    """x⁴ + y² and −x⁴ + y² both give no verdict at the origin: an eigenvalue of H is 0"""
    expect_equal(classify(lambda p: p[0] ** 4 + p[1] ** 2, [0, 0]), "no verdict", what="classify(x⁴ + y², [0, 0])")
    expect_equal(classify(lambda p: -p[0] ** 4 + p[1] ** 2, [0, 0]), "no verdict", what="classify(-x⁴ + y², [0, 0])")


def test_tuple_input():
    """The point may be a tuple of whole numbers: (1, 0) is still the cubic's minimum"""
    expect_equal(classify(cubic, (1, 0)), "minimum", what="classify(cubic, (1, 0))")

The Hessian and the quadratic copy

Critical points and the second-derivative test

Coding exercise

Free further reading