Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 6 / b / ii / Solution

Here a dense $100000$-by-$100000$ matrix has $10^{10}$ entries, about $80$ GB even with eight-byte storage per entry. Use limited-memory BFGS on the negative of the objective, or equivalently its positive-definite approximate-metric form of gradient ascent. It stores only a fixed small number $\ell$ of vector pairs, costing $O(\ell d)$ memory rather than $O(d^2)$.

Let $G(x)={\sum }_{i=1}^{100}{e}^{e^{-\Vert x-a_i{\Vert }^2}}$ and put $c_i(x)=e^{e^{-\Vert x-a_i{\Vert }^2}}{e}^{-\Vert x-a_i{\Vert }^2}$. Direct use of the chain rule givesIf $H_n$ denotes the positive-definite inverse-Hessian matrix approximation for $-G$, the iteration iswith a line search increasing $G$ and the usual safeguarded limited-memory updates. No exact Hessian matrix is required. With fixed memory and the usual bounded-metric and line search hypotheses, expect local linear convergence near a nondegenerate strict maximum; fixed-memory limited-memory BFGS does not generally inherit the superlinear theorem for full-memory BFGS.

Unlike the preceding objective, $G$ is not generally a concave function. Thus this is a method for finding a local maximum; comparison of different converged candidates or a global search is needed to certify a global maximum for arbitrary centres. The symbolic problem supplies no assumption that would justify an unconditional global-convergence claim.^[ref]