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

Separate inactive and active optimization constraints. At an interior feasible point with $h>0$, a differentiable local minimum must satisfy $\nabla f=0$. Retain only solutions lying in the interior.

On the boundary $h=0$, if $\nabla h\ne 0$, apply the Lagrange multiplier condition. Using the optimization Lagrangian $L=f-\lambda h$, the Karush-Kuhn-Tucker conditions areThe sign follows from feasible motion into $h>0$: the directional derivative along $\nabla h$ at a minimum cannot be negative. Thus a boundary candidate has $h=0$ and a nonnegative Lagrange multiplier. Boundary points with $\nabla h=0$ must be examined separately, because the usual constraint qualification fails there.

Solve the interior and boundary systems, check membership in the feasible set, and establish which candidates are minima using second-order tests or a direct global comparison. The Karush-Kuhn-Tucker conditions alone are not sufficient for general nonconvex functions or feasible sets. On an unbounded feasible set, also check whether an infimum is attained and whether escaping sequences can improve the objective.

Complete the square to write the objective asLet $z=(x,y)$ and $a=(1,2)$, so $\Vert a\Vert =\sqrt{5}$ while feasibility requires $\Vert z\Vert \ge \sqrt{20}=2\sqrt{5}$. The reverse triangle inequality givesThe objective is therefore at least zero. Equality is attained by $z=2a=(2,4)$, which lies on the boundary. Equality requires the vectors to have the same direction and $\Vert z\Vert =2\sqrt{5}$, so this minimizer is unique. HenceIt also satisfies the Karush-Kuhn-Tucker conditions with $\lambda =1/2$. The direct distance argument proves global optimality even though the exterior of a disk is not a convex set; this is nearest-point minimization outside a Euclidean ball.

The objective is continuous on the compact disk, so a global maximum exists. Its gradient is $(e^x,2e^{2y})$, which is never zero, so a maximum cannot lie in the interior. It must have $x^2+y^2=1$.

Both coordinates of a maximizing point are positive. Reflecting a negative coordinate to its positive counterpart strictly increases the objective without changing the constraint; at an endpoint with one coordinate zero, a small move along the circle into the positive quadrant also increases the objective to first order. Thus it suffices to consider $x>0,y>0$.

The boundary Lagrange multiplier equations are $e^x=2\lambda x$ and $2e^{2y}=2\lambda y$. Eliminate $\lambda$ to obtain the two-dimensional nonlinear system of equationsKeeping this quadrant restriction excludes the boundary minimum that an unconstrained elimination could also produce. Under the stated uniqueness assumption for the admissible solution, the global maximum must be that solution. Approximate it with multivariable Newton iteration, solving $J_F(z_n){\Delta }_n=-F(z_n)$ and setting $z_{n+1}=z_n+{\Delta }_n$, with a suitable safeguard if needed. For example its explicit Jacobian matrix isNo numerical solution of the system is required.

Use the optimization LagrangianSymmetry gives the gradient equations $2Ax=\lambda 1$ and $2By=\lambda 1$. The positive-definite matrices are invertible, so defineThe affine constraint gives $\lambda =2/D$, henceFor a global certificate, write any other feasible point as $(x_{\ast }+u,y_{\ast }+v)$. Feasibility implies $1^{T}u+1^{T}v=0$. Expansion cancels the cross terms and leavesBy positive definiteness this is positive unless $u=v=0$. Thus the solution is the unique global minimum, not merely a stationary point. This is a two-block instance of positive quadratic minimization under one affine constraint.