Maxima, Minima and Single-Variable Optimization

Critical points

$f$ has a local maximum at $c$ if $f(c) \ge f(x)$ for all $x$ near $c$ (similarly for a local minimum). Fermat's theorem: if $f$ has a local extremum at an interior point $c$ and is differentiable there, then $f'(c) = 0$.

Critical points are where $f'(c) = 0$ (stationary points) or $f'(c)$ does not exist. Every interior extremum is a critical point, but not every critical point is an extremum ($x^3$ at 0).

Tests for local extrema

First-derivative test — look at the sign of $f'$ around $c$:

Second-derivative test at a stationary point ($f'(c) = 0$):

Higher-order test: if $f'(c) = \dots = f^{(n-1)}(c) = 0$ and $f^{(n)}(c) \ne 0$: for even $n$, a minimum if $f^{(n)}(c) > 0$ and a maximum if $< 0$; for odd $n$, neither (inflection). This follows from the Taylor expansion $f(c + h) - f(c) \approx \frac{f^{(n)}(c)}{n!}h^n$.

Global extrema on a closed interval

A continuous function on $[a, b]$ attains its global max and min (extreme value theorem). Closed-interval method:

1. Find all critical points in $(a, b)$.
2. Evaluate $f$ at those points and at the endpoints $a, b$.
3. The largest value is the global maximum; the smallest is the global minimum.

Concavity, convexity and inflection points

• Convex (concave up) on $I$: $f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda)f(y)$ — every chord lies above the graph. For twice-differentiable $f$: $f'' \ge 0$ on $I$. Equivalently, the graph lies above every tangent line: $f(y) \ge f(x) + f'(x)(y - x)$.
• Concave: $-f$ convex; $f'' \le 0$.
• Inflection point: where concavity changes ($f''$ changes sign).

Why convexity matters: for a convex function, every local minimum is global, and a stationary point is a global minimiser. Linear regression's squared loss, logistic regression's log-loss, the SVM hinge loss and L1/L2 penalties are convex; neural network losses are not.

Useful facts: $e^x$, $x^2$, $\lvert x\rvert$, $-\ln x$, $x\ln x$ are convex; non-negative weighted sums and maxima of convex functions are convex; a convex function of an affine function is convex.

Applied optimisation problems

Optimisation algorithms

Gradient descent

$$x_{k+1} = x_k - \eta\,f'(x_k).$$

Move downhill by a step proportional to the slope. The learning rate $\eta$ controls everything:

• too small → slow convergence;
• too large → oscillation or divergence;
• for $f(x) = \frac L2(x - x^*)^2$: $x_{k+1} - x^* = (1 - \eta L)(x_k - x^*)$, converging iff $0 < \eta < 2/L$; $\eta = 1/L$ is optimal.

For general smooth convex $f$ with $\lvert f''\rvert \le L$, the step size $\eta \le 1/L$ guarantees steady decrease. Variants: stochastic gradient descent (gradient from a random mini-batch), momentum, adaptive methods (Adam). See neural networks.

Newton's method

Minimise the local quadratic model $f(x_k) + f'(x_k)h + \frac12f''(x_k)h^2$:

$$x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}.$$

It is Newton's root-finding method applied to $f'$. It converges quadratically near a minimiser with $f'' > 0$ (the number of correct digits roughly doubles each step) and minimises a quadratic in one step, but each step needs $f''$, and it can head to a maximum or diverge if $f'' \le 0$ or the start is poor.

Bracketing methods

Without derivatives: golden-section search shrinks an interval containing the minimum of a unimodal function by the factor 0.618 per step; bisection on $f'$ halves an interval where $f'$ changes sign.

Optimisation in statistics and ML

• Maximum likelihood: maximise $\ell(\theta) = \sum\ln f(x_i;\theta)$; logs turn products into sums and keep the same maximiser. Bernoulli: $\hat p =$ successes/trials; exponential: $\hat\lambda = 1/\bar x$.
• Least squares: minimising $\sum(y_i - c)^2$ over $c$ gives $c = \bar y$; minimising $\sum\lvert y_i - c\rvert$ gives the median.
• Regularisation trades fit against complexity: minimising $(x - a)^2 + \lambda x^2$ gives $x = \frac{a}{1 + \lambda}$ — shrinkage, the one-dimensional picture of ridge regression.

Quick revision