Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 6

Use the LagrangianThe Lagrange multiplier equations areFeasibility makes $x\ne 0$, so $\lambda =2x^2>0$. The second equation becomes $2y(8y^2+\lambda )=0$, forcing $y=0$ and then $x=\pm 1$. The constraint gradient $(2x,-2y)$ is nonzero on the feasible set, so the multiplier calculation has no missing singular feasible point.

To verify the global minimum rather than just stationarity, eliminate $x^2=1+y^2$:Equality holds exactly at $(x,y)=(1,0)$ or $(-1,0)$, with minimum value $1$.

If $\mathbf{b}=0$, the objective is zero at every feasible point, so every point of the ellipsoid is a minimizer. Suppose now $\mathbf{b}\ne 0$. A minimum cannot be interior: a sufficiently small step in direction $-\mathbf{b}$ would remain feasible and decrease the objective. The boundary is active.

Forstationarity gives $\mathbf{b}+2\lambda A\mathbf{x}=0$. A positive-definite symmetric matrix is invertible, and the minimizing sign has $\lambda >0$. Enforcing the boundary gives

For global optimality, use the inner product $⟨u,v{⟩}_A=u^{\mathsf{T}}Av$. The Cauchy-Schwarz inequality givesThe proposed point attains the negative of this bound. Thus the minimum is $-\sqrt{{\mathbf{b}}^{\mathsf{T}}{A}^{-1}\mathbf{b}}$, and equality in the Cauchy-Schwarz inequality, together with the sign and boundary conditions, makes this minimizer unique when $\mathbf{b}\ne 0$.

Use a column gradient. By the multivariable chain rule,The scalar coefficients multiply the constant vectors ${\mathbf{a}}_i$. In particular $f^{\prime }(t)=-t{e}^{-t^2/2}$, although explicit differentiation of $f$ is not required.

Differentiating the gradient term by term gives the Hessian matrixTake row $i$ of $A$ to be ${\mathbf{a}}_i^{\mathsf{T}}$. ThenIndeed, entry $(j,k)$ of this product is ${\sum }_i{\Delta }_{ii}{a}_{ij}{a}_{ik}$, exactly the entry of the displayed sum of outer products. Explicitly,These coefficients may have either sign, so a positive-definite Hessian matrix cannot be assumed. This is an instance of the Hessian of a sum of functions of linear forms.

At $d=1000$, gradient descent and full BFGS are practical candidates; a dense Newton method can also be feasible, but its extra work and indefinite curvature need attention. The number of examples $n$, data sparsity and conditioning still matter.

For dense $A$, a gradient evaluation costs $O(nd)$ arithmetic, with $O(d)$ working storage beyond the data and accumulation buffers. Gradient descent is inexpensive per iteration and, with an appropriate line search, follows a descent direction, but poor conditioning can make it slow.

Forming the Hessian matrix explicitly costs $O(n{d}^2)$ arithmetic, and a dense Newton method solve costs $O(d^3)$. A $1000$-square double-precision matrix uses about $8$ MB, so storage alone is manageable, but repeated factorization may be expensive. Because the Hessian matrix can be indefinite or singular, an unmodified Newton step need not decrease the loss; a modified Hessian, damping or a trust region is appropriate.

Full BFGS uses gradients and an $O(d^2)$ curvature approximation, avoiding explicit second derivatives. Its rank-two updates and direction calculation cost $O(d^2)$ per step and require roughly the same matrix storage. A positive-definite initial approximation with safeguarded curvature updates and a suitable line search preserves descent directions. For this scale it is often a good compromise, without guaranteeing a global minimum.^[ref]

At $d=10^6$, gradient descent remains a plausible large-scale choice; dense Newton method and full-memory BFGS are generally impractical. A dense $d\times d$ double-precision matrix alone contains $10^{12}$ entries, about $8$ TB. Dense factorization also has order $10^{18}$ arithmetic work. Full BFGS avoids factorization but retains quadratic storage and update work, so it does not solve that scaling problem.

Gradient descent uses linear working storage in $d$, though the cost of reading the data and evaluating the gradient is still $O(nd)$ for dense $A$. Sparsity or streaming can be important. Limited-memory BFGS, a distinct limited-memory variant, stores only a fixed number $m$ of recent update pairs and uses $O(md)$ storage and update work, making it a realistic alternative to full BFGS.^[ref]

The available Hessian matrix factorization also permits a matrix-free Hessian-vector product:It costs $O(nd)$ for dense data without forming $H$. A suitable iterative, safeguarded Newton method can exploit this structure, so the conclusion rules out the dense implementation rather than every possible second-order algorithm.

These methods seek a local solution and require convergence checks appropriate to nonconvex optimization. The formula does not even ensure a finite minimizer exists: with one positive coefficient and nonzero $\mathbf{a}$, the positive exponential loss approaches zero along an unbounded direction without attaining it. Dimension alone cannot supply a convergence guarantee.