Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 5 / c

Use bisection on $f^{\prime }$ when the derivative is cheap and a bracket $f^{\prime }(a)<0<f^{\prime }(b)$ is easy to obtain. For a differentiable convex function, $f^{\prime }$ is nondecreasing, so such a bracket locates a global minimum, allowing a flat minimizing interval. Without convexity, first isolate a region containing the desired local minimum; arbitrary stationary points need not be minima.

Use golden-section search when reliable function values are available but derivatives are unavailable or expensive. It needs a bracket on which the objective is a unimodal function, commonly found by three ordered points whose middle value is below the two outer values. Those inequalities alone do not prove that the objective is a unimodal function. A convex function supplies the needed shape; for a nonconvex objective, isolate an interval on which it is a unimodal function.

Both methods have linear convergence of bracket width. Bisection contracts the width by $1/2$ per new derivative evaluation. Golden-section search contracts it by $(\sqrt{5}-1)/2\approx 0.618$ per new function evaluation after initialization, reusing one earlier value. Choose by evaluation cost and bracket availability as well as this contraction factor: comparing iteration counts alone can misidentify the faster method.

Convexity of the components of a vector field is not the decisive criterion for a root-finding problem. Neither method becomes globally reliable merely because each component is convex.

Prefer the Newton root-finding iteration when the Jacobian matrix is available accurately and at reasonable cost. Solve $J({\mathbf{x}}_k){\mathbf{s}}_k=-\mathbf{f}({\mathbf{x}}_k)$ rather than explicitly forming an inverse matrix. Near a root with a nonsingular Jacobian matrix and a locally Lipschitz Jacobian matrix, the usual exact iteration has quadratic convergence.

Prefer Broyden's method when evaluating or differentiating the vector field makes a fresh Jacobian matrix expensive. It learns an approximate Jacobian matrix through secant updates using function differences. Under appropriate local regularity and initialization assumptions it has superlinear convergence, generally slower asymptotically than the quadratic convergence of exact Newton steps, but often with cheaper iterations.^[ref]

Dimension matters through storage and solves. A full dense Newton factorization costs order $d^3$ arithmetic operations; a dense Broyden approximation uses order $d^2$ storage, and maintained inverse or factorization updates can cost order $d^2$. A naive fresh dense solve can still cost order $d^3$. Sparsity can favour Newton, while very large $d$ can make either dense formulation unsuitable. Neither local rate guarantees convergence from an arbitrary starting point.

Gradient descent uses only the current gradient and a suitable step size; its additional storage is order $d$. It is attractive for very large $d$ or when low per-iteration cost matters most. For a smooth strongly convex function, standard step choices give linear convergence, with a rate sensitive to the condition number. Mere convexity gives a global-minimum interpretation but does not alone imply a linear rate; for nonconvex objectives the usual guarantee concerns stationary points.

BFGS uses successive gradients to update an approximation to inverse curvature, incorporating information that can correct poor scaling. Full BFGS uses order $d^2$ storage and update work. With suitable line searches and local smoothness and positive-curvature assumptions near a nondegenerate minimum, it has superlinear convergence. This often favours it in moderate dimensions when gradients are not extremely cheap relative to the extra work.

Neither gradient descent nor BFGS requires an explicitly evaluated Hessian matrix. Thus an expensive Hessian matrix is compatible with both, rather than a reason to reject BFGS. If an accurate Hessian matrix and its factorization are exceptionally cheap, Newton's method in optimization becomes an additional reasonable option. Convexity helps identify a stationary point as a global minimum; without it, both methods need suitable descent and curvature safeguards. The BFGS update learns curvature from the Quasi-Newton secant equation.^[ref]