4.4.4 Practice set: unconstrained optimisation

Optimality conditions

Optimality conditions in several variables (lesson 4.4.1)

0 of 7 correct

1.
$f(x, y) = x^2 - 2xy + 3y^2 - 4y$ has one critical point. What is its $y$ -coordinate?
2.
The Hessian of $x^2 - 2xy + 3y^2 - 4y$ is $\begin{pmatrix} 2 & -2 \\ -2 & 6 \end{pmatrix}$ . Find $\det H$
3.
What is the minimum value of $x^2 - 2xy + 3y^2 - 4y$ ?
4.
Minimise $\frac{1}{2}\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}$ with $A = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}$ and $\mathbf{b} = (4, 3)$ . What is the minimum value?
5.
Minimise $F(c) = (c - 1)^2 + (c - 4)^2 + (c - 10)^2$ . Find $c$
6.
At a critical point $H = \begin{pmatrix} 1 & 3 \\ 3 & 1 \end{pmatrix}$ . Is it a minimum (type 1), a maximum (type 2) or a saddle (type 3)?
7.
$x^2 + y^4$ has $\nabla f = \mathbf{0}$ and $H = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}$ at the origin, so the test is silent. Is the origin a 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.

Gradient descent

Gradient descent (lesson 4.4.2)

0 of 7 correct

1.
Take one gradient-descent step on $f(x, y) = 2x^2 + y^2$ from $(1, 2)$ with $\eta = 0.1$ . What is the new $y$ ?
2.
For $2x^2 + y^2$ , below what step size does gradient descent converge from every start?
3.
For $2x^2 + y^2$ with $\eta = 0.4$ , by what factor is $x$ multiplied at each step?
4.
For $2x^2 + y^2$ , find the best fixed step $\frac{2}{\lambda_{\max} + \lambda_{\min}}$
5.
A quadratic's Hessian has eigenvalues 0.5 and 50. With the best fixed step, find the slowest factor $\frac{\kappa - 1}{\kappa + 1}$
6.
Each step multiplies the error by 0.5. What is the smallest number of steps that shrinks it below $10^{-6}$ of its start?
7.
Backtracking on $f(x) = 2.5x^2$ at $x = 1$ tries $\eta = 1, 0.5, 0.25, \ldots$ Which $\eta$ is accepted first?

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.

Newton's method

Newton's method in several variables (lesson 4.4.3)

0 of 7 correct

1.
Take one Newton step on $f(x, y) = x^2 + 3y^2 - 2x + 6y$ from $(0, 0)$ . What is the new $y$ ?
2.
Solve $H\mathbf{h} = -\nabla f$ for $H = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$ and $\nabla f = (4, 0)$ . Give $h_2$
3.
For $f(x, y) = e^x - 2x + y^2$ , take one Newton step from $(0, 1)$ . What is the new $x$ ?
4.
Two Newton errors in a row are 0.1 and 0.004. With the same quadratic constant, estimate the next
5.
How many different entries does the symmetric Hessian of a function of 50 variables have?
6.
Plain Newton on $f(x, y) = 4 - x^2 - y^2$ from $(1, 2)$ lands in one step. What is $f$ there?
7.
At a point $H = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ and $\nabla f = (1, -1)$ . Cholesky fails, so the safeguarded step uses $\mathbf{h} = -\nabla f$ . Give $h_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.

Coding exercise

Exercise

Gradient descent with backtracking

Write descend(f, grad, x0, tol=1e-6, max_steps=10_000) that minimises f from x0, with the backtracking rule of lesson 4.4.2. It returns (x, steps): a NumPy array and the number of steps taken.

Start from a new decimal array, np.array(x0, dtype=float), so the caller's array is left unchanged.
Before each step, if $\lVert\nabla f(\mathbf{x})\rVert$ is below tol, return. A start at the minimum takes 0 steps.
For each step, set $\eta = 1$ and halve it until $f(\mathbf{x} - \eta\nabla f) \le f(\mathbf{x}) - \frac{1}{2}\eta\lVert\nabla f\rVert^2$ . Then step to $\mathbf{x} - \eta\nabla f$ .
Raise ValueError if tol is not positive, or if $\eta$ falls below $10^{-12}$ : then no step lowers $f$ , and grad is probably wrong.
Raise RuntimeError if the gradient is still too long after max_steps steps.

The tests use the examples of lessons 4.4.1 to 4.4.3: the two quadratics, the curved valley and the quartic from two starts. They add $10x^2 + y^2$ , where a fixed step of 1 diverges. Others pass a gradient with the wrong sign, tol=0 and too few steps.

See the tests

import numpy as np


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


def _tilted_grad(p):
    return np.array([2 * p[0] + p[1] - 3, p[0] + 2 * p[1]])


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


def _valley_grad(p):
    x, y = p
    return np.array([-2 * (1 - x) - 20 * x * (y - x**2), 10 * (y - x**2)])


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


def _quartic_grad(p):
    return np.array([4 * p[0] ** 3 - 6 * p[0] + 1, 2 * p[1]])


def _expect_error(kind, call, why):
    try:
        call()
    except kind:
        return
    raise AssertionError(f"expected {kind.__name__}: {why}")


def test_quadratic():
    """x² + xy + y² − 3x from (0, 0) ends at its minimum (2, −1)"""
    x, steps = descend(_tilted, _tilted_grad, [0.0, 0.0])
    expect_close(x, np.array([2.0, -1.0]), what="the point returned", abs_tol=1e-5)


def test_returns_a_pair():
    """The result is a pair: a NumPy array and a whole number of steps"""
    result = descend(_tilted, _tilted_grad, [0.0, 0.0])
    assert isinstance(result, tuple) and len(result) == 2, f"expected (x, steps), got {result!r}"
    x, steps = result
    assert isinstance(x, np.ndarray), f"x should be a NumPy array, got {type(x).__name__}"
    assert int(steps) == steps and steps > 0, f"steps should be a positive whole number, got {steps!r}"


def test_start_at_minimum():
    """Started at the minimum, it takes 0 steps"""
    x, steps = descend(_tilted, _tilted_grad, [2.0, -1.0])
    expect_equal(steps, 0, what="steps from the minimum itself")
    expect_close(x, np.array([2.0, -1.0]), what="the point returned")


def test_three_variables():
    """½xᵀKx − bᵀx with lesson 4.4.1's K and b = (3, 0, −3) ends at (1, 1, −1)"""
    K = np.array([[4.0, -1.0, 0.0], [-1.0, 3.0, 2.0], [0.0, 2.0, 5.0]])
    b = np.array([3.0, 0.0, -3.0])
    x, _ = descend(lambda v: 0.5 * v @ K @ v - b @ v, lambda v: K @ v - b, np.zeros(3))
    expect_close(x, np.array([1.0, 1.0, -1.0]), what="the minimiser", abs_tol=1e-5)


def test_step_too_large_is_halved():
    """On 10x² + y² a fixed step of 1 diverges; backtracking still reaches (0, 0)"""
    x, _ = descend(lambda p: 10 * p[0] ** 2 + p[1] ** 2, lambda p: np.array([20 * p[0], 2 * p[1]]), [1.0, 1.0])
    expect_close(x, np.array([0.0, 0.0]), what="the point returned", abs_tol=1e-5)


def test_curved_valley():
    """The curved valley from (−1.5, 2.5) reaches (1, 1) within 10,000 steps"""
    x, steps = descend(_valley, _valley_grad, [-1.5, 2.5])
    expect_close(x, np.array([1.0, 1.0]), what="the point returned", abs_tol=1e-4)
    assert steps < 10_000, f"expected fewer than 10,000 steps, took {steps}"


def test_start_decides_the_minimum():
    """x⁴ − 3x² + x + y² ends at the local minimum from (1, 0.5) and the global one from (−1, 0.5)"""
    right, _ = descend(_quartic, _quartic_grad, [1.0, 0.5])
    left, _ = descend(_quartic, _quartic_grad, [-1.0, 0.5])
    expect_close(right, np.array([1.130901, 0.0]), what="the minimum reached from (1, 0.5)", abs_tol=1e-5)
    expect_close(left, np.array([-1.300840, 0.0]), what="the minimum reached from (−1, 0.5)", abs_tol=1e-5)


def test_too_few_steps():
    """With max_steps=20 the curved valley is not done: RuntimeError"""
    _expect_error(RuntimeError, lambda: descend(_valley, _valley_grad, [-1.5, 2.5], max_steps=20),
                  "the gradient is still large after 20 steps")


def test_wrong_gradient():
    """A gradient with the wrong sign points uphill: ValueError"""
    _expect_error(ValueError, lambda: descend(_tilted, lambda p: -_tilted_grad(p), [0.0, 0.0]),
                  "no step size makes f fall, because -grad points uphill")


def test_bad_tolerance():
    """tol must be positive: ValueError for tol=0"""
    _expect_error(ValueError, lambda: descend(_tilted, _tilted_grad, [0.0, 0.0], tol=0), "tol=0 can never be met")


def test_input_unchanged():
    """The caller's starting array is left unchanged"""
    start = np.array([0.0, 0.0])
    descend(_tilted, _tilted_grad, start)
    expect_equal(start.tolist(), [0.0, 0.0], what="the starting array after the call")

Optimality conditions

Gradient descent

Newton's method

Coding exercise

Free further reading