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

The second-derivative criterion for convexity isThe non-strict inequality is necessary and sufficient; the stronger condition $f^{\prime \prime }>0$ is sufficient for strict convexity.

Expand before taking the second derivative:The second-derivative criterion for convexity proves that $f$ is strictly convex, hence convex.

The Hessian criterion for convexity, in the usual twice-differentiable multivariate setting, isThus the Hessian matrix must be a positive semidefinite matrix everywhere. The criterion follows by applying the second-derivative criterion for convexity to each line restriction $t\mapsto g(x+tv)$, whose second derivative is $v^{\mathsf{T}}H(g)(x+tv)v$. Continuous second partials are a sufficient regularity hypothesis for this line-restriction argument.

Writing $g=e^{x^{\mathsf{T}}x}$, the gradient and Hessian matrix areConsequently, for any nonzero $v$,In particular the Hessian matrix is a positive semidefinite matrix everywhere, so the Hessian criterion for convexity proves $g$ is convex. The strict inequality along every nonconstant line also proves strict convexity.

The map $u\mapsto u^2$ is strictly increasing on $[0,\infty )$: for $u,v\ge 0$, $u\le v$ if and only if $u^2\le v^2$. Therefore a point has the smallest $f$-value if and only if it has the smallest $f^2$-value, and the same applies to $g$. By minimizers under strictly increasing transformations, both asserted argmin equalities hold, including when the argmin sets are empty. The differentiability assumptions are unnecessary for this order argument.

Minimize the square of the Euclidean distance, using minimizers under strictly increasing transformations. For $s=x+y>0$,For fixed $s$ the unique minimum has $x=y=s/2$. Put $x=y=\alpha >0$ and $J(\alpha )=2{\alpha }^2+{\ln }^2(2\alpha )$. Its derivative isLet $h(\alpha )=2{\alpha }^2+\ln (2\alpha )$. Since $h^{\prime }(\alpha )=4\alpha +1/\alpha >0$, it is strictly increasing, with limits $-\infty$ and $+\infty$ at the two ends of $(0,\infty )$. It therefore has exactly one zero. The sign of $J^{\prime }$ changes there from negative to positive, proving the unique global minimum. The nearest point is $P=(\alpha ,\alpha ,\ln (2\alpha ))$ at that zero.^[ref]

The Newton root-finding iteration isStarting at $0.4$ gives $0.376376476$, $0.376544572$, and $0.376544582$. Moreover $h(0.3765)<0<h(0.3766)$ certifies the rounding. Thus $\alpha =0.377$ to three significant figures; more accurately $P\approx (0.3765445825,0.3765445825,-0.2835716452)$.

Use Simpson's rule: the cubic exactness of Simpson's rule includes every quadratic integrand, so three function evaluations already give the exact answer. Thus the error is zero. For a general smooth integrand the corresponding composite Simpson's rule has error $O(N^{-4})$ in big O notation, but that bound is unnecessarily weak here.

Use composite Simpson's rule on this smooth, bounded one-dimensional interval. Its fourth derivative is bounded on the interval, so the error bound for composite Simpson's rule gives $O(N^{-4})$ in big O notation as the number of function evaluations increases.

Use tensor-product quadrature with composite Simpson's rule in each coordinate. If there are $m$ subintervals in each direction, then $N=(m+1{)}^2$ and the quadrature rule error is $O(m^{-4})$: apply the one-dimensional error bound for composite Simpson's rule successively, using bounded fourth partial derivatives. Hence the error is $O(N^{-2})$ in big O notation. The rectangular domain makes the product grid convenient.

A convenient choice for this irregular region is Monte Carlo integration. The region is contained in $[-1,1{]}^2$. For independent uniform points $U_j$ in that square, letThe indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error $O(N^{-1/2})$ in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.

For a generic integrand in 20 dimensions, Monte Carlo integration gives root mean square error $O(N^{-1/2})$, whereas tensor-product quadrature with composite Simpson's rule gives only $O(N^{-4/20})=O(N^{-1/5})$. One can sample uniformly in the Euclidean unit ball, for example by an independent uniform direction and radius $U^{1/20}$ with $U$ uniform on $[0,1]$.

For this particular integrand, the most efficient elementary choice uses radial integration over a ball first. The area of the unit 19-sphere is $2{\pi }^{10}/9!$, as follows from the volume of an n-ball. HenceThe reduced integrand is smooth. Apply composite Simpson's rule to obtain $O(N^{-4})$ deterministic error in big O notation, with one original radial integrand evaluation per node. If the selection is restricted to direct multidimensional methods, Monte Carlo integration with $O(N^{-1/2})$ root mean square error is the appropriate choice.

By Taylor's theorem with Lagrange remainder, for an increment $t$,where ${\xi }_t$ lies between $x$ and $x+t$. The given third derivative bound implies $|R_x(t)|\le |t{|}^3/6$.

Apply the preceding Taylor's theorem at $t=h$ and $t=-h$, with $h>0$. The even-order terms cancel in the central finite difference, givingBoth Lagrange remainders have magnitude at most $h^3/6$, so the triangle inequality gives the sharp central-secant derivative error

Write the computed function values as $f(x\pm h)+e_{\pm }$, where $|e_{\pm }|\le \delta$. The computed central finite difference $\tilde{d}$ satisfiesThe two contributions are respectively evaluation absolute error and truncation error. For $\delta >0$, step-size choice for a noisy central derivative minimizes their sum: its derivative is $h/3-\delta /h^2$, negative before and positive afterIf $\delta =0$, the bound tends to zero as $h\downarrow 0$ and has no positive minimizing step.

The derivative is represented by the gradient, and the Hessian matrix contains the second partial derivatives:Equivalently the derivative as a linear map is $Df(x,y)(u,v)=(4x^3-4y)u+(4y-4x)v$.

The stationary point equations give $y=x$ and $x^3=x$, hence $(0,0),(1,1),(-1,-1)$. At $(0,0)$ the Hessian matrix has negative determinant $-16$, so $(0,0)$ is a saddle point. At each of $(1,1)$ and $(-1,-1)$, the Hessian matrix has positive leading minors $12$ and $32$, proving a strict local minimum. More strongly,Thus $(1,1)$ and $(-1,-1)$ are exactly the global minima, with value $3$. There are no local maxima, since any differentiable interior local maximum would be a stationary point, and all three have been classified.

For the equality-constrained minimization problem, $y=8/x$ and $x\ne 0$. Put $t=x^2>0$. The restricted objective isThe only zero has $t^3=64$, so $t=4$. Since $F^{\prime \prime }(t)=2+256/t^3>0$, the second-derivative criterion for convexity proves a unique minimizing $t$. Consequently the equality constraint has minimizers $(2,4)$ and $(-2,-4)$, with minimum $20$.

For the inequality-constrained minimization problem, the identity $f=(x^2-1{)}^2+2(y-x{)}^2+3$ supplies the universal lower bound $3$. Both equality points for that bound, $(1,1)$ and $(-1,-1)$, satisfy $xy=1\le 8$. Hence the inequality constraint has exactly these two minimizers, with minimum $3$.

For Newton's method in optimization, let $\Delta =H(f{)}^{-1}\nabla f$. Its second row equation is $-4{\Delta }_x+4{\Delta }_y=4y-4x$, so ${\Delta }_y={\Delta }_x+y-x$. Therefore $y_{n+1}=y_n-{\Delta }_y=x_n-{\Delta }_x=x_{n+1}$. The given first coordinate yieldsThe Newton step is defined where $\det H(f)=16(3x^2-1)\ne 0$; both coordinates after any defined step are equal.

By the diagonal reduction in a two-variable Newton iteration, $y_n=x_n$ for $n\ge 1$. Put $e_n=x_n-1$. Direct factorization gives the exact Newton map in optimization error identityThe assumed convergence $x_n\to 1$ makes the final factor tend to $3/2$, so it is bounded for all sufficiently large $n$. Hence $|e_{n+1}|\le C|e_n{|}^2$. For the Euclidean norm error $E_n=\Vert (x_n,y_n)-(1,1)\Vert =\sqrt{2}|e_n|$, this becomes $E_{n+1}\le (C/\sqrt{2})E_n^2$, proving quadratic convergence. Unless the exact limit is reached in finitely many steps, $E_{n+1}/E_n^2\to 3/(2\sqrt{2})$.