Optimisation: maxima, minima and gradient methods

Critical points and how to classify them

Definitions.

• $f$ has a local maximum at $c$ if $f(c) \ge f(x)$ for all $x$ near $c$. A global maximum if this holds for all $x$ in the domain. Minima are defined the same way.
• A critical point is a $c$ where $f'(c) = 0$ or $f'(c)$ does not exist.

Fermat's theorem. At an interior local extremum where $f$ is differentiable, $f'(c) = 0$. The converse is false: $x^3$ has $f'(0) = 0$ but no extremum there.

First-derivative test. If $f'$ changes sign from $+$ to $-$ at $c$, there is a local maximum. From $-$ to $+$, a local minimum. If there is no sign change, there is no extremum.

Second-derivative test. At $f'(c) = 0$:

• $f''(c) > 0$ means a minimum;
• $f''(c) < 0$ means a maximum;
• $f''(c) = 0$ means the test says nothing.

Higher-order test. Let the first non-zero derivative at $c$ be $f^{(n)}(c)$.

• If $n$ is even, there is an extremum: a minimum if $f^{(n)}(c) > 0$, a maximum if it is negative.
• If $n$ is odd, there is no extremum. The point is a point of inflection.

Example 1.

• $x^4$ at 0: the first non-zero derivative is the fourth, equal to $24 > 0$. Minimum.
• $x^3$ at 0: the first non-zero derivative is the third. No extremum.
• $x^5 - 5x$: $f' = 5x^4 - 5 = 0$ at $x = \pm 1$, and $f'' = 20x^3$. So $x = 1$ is a minimum, with $f = -4$, and $x = -1$ is a maximum, with $f = 4$.

Points where $f'$ does not exist can also be extrema. $\lvert x\rvert$ has its minimum at the corner $x = 0$.

Global extrema on a closed interval

By the extreme value theorem, a continuous function on $[a, b]$ has a global maximum and minimum. Method: evaluate $f$ at every critical point inside $(a, b)$ and at both endpoints, then compare.

Example 2. $f(x) = x^3 - 3x^2$ on $[-1, 4]$.

1. $f' = 3x^2 - 6x = 3x(x - 2)$, so the critical points are 0 and 2.
2. The values are $f(-1) = -4$, $f(0) = 0$, $f(2) = 8 - 12 = -4$ and $f(4) = 64 - 48 = 16$.
3. The global maximum is 16, at $x = 4$ (an endpoint). The global minimum is $-4$, reached at both $x = -1$ and $x = 2$.

Note that the local maximum at 0 is not the global maximum.

Example 3. $f(x) = x + \frac1x$ on $[\frac12, 3]$.

1. $f' = 1 - \frac1{x^2} = 0$ at $x = 1$.
2. The values are $f(\frac12) = 2.5$, $f(1) = 2$ and $f(3) = 3.\overline{3}$.
3. The minimum is 2 and the maximum is $\frac{10}{3}$.

Convexity

Definition. $f$ is convex on an interval if the chord between any two points of its graph lies above the graph:

$f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda)f(y) \quad \text{for } 0 \le \lambda \le 1.$

For twice-differentiable $f$, this is the same as $f'' \ge 0$. $f$ is concave if $-f$ is convex.

Why convexity matters. For a convex function, every local minimum is a global minimum. If $f'' > 0$, the minimum is unique. Least squares, ridge regression and logistic regression all have convex losses. Neural network losses do not.