Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 339 / 2

For a feasible vector, set $X=x{x}^T$. It is a positive semidefinite matrix, andThus every original feasible point supplies an equally valuable SDP feasible point. Dropping the rank-one restriction is the semidefinite relaxation of slab-constrained quadratic maximization, provingThe original PDF has $|a_i^{T}x|\le 1$; the absolute values are missing from the extracted TeX and are essential for this relaxation.

For the subsequent finite rounding argument, the constraint vectors must span ${\mathbb{R}}^n$. Otherwise a nonzero common-kernel vector $d$ makes both $x=td$ and $X=td{d}^T$ unbounded feasible families, so both objective suprema are infinite. Under spanning, $H={\sum }_i{a}_i{a}_i^T$ is a positive-definite matrix andThe first inequality uses positive semidefinite trace nonnegativity. The SDP feasible set is closed and bounded, hence compact, so an optimum exists. Its trace is positive: a sufficiently small positive multiple of the identity is feasible when $n\ge 1$. These facts justify the optimum and nonzero denominator used below. Assume $m,n\ge 1$.

Use the spectral theorem for real symmetric matrices to write $X^{\ast }=V\Lambda V^T$, with $V$ orthogonal and $\Lambda$ diagonal and nonnegative. For any sign vector, ${\xi }_j^2=1$, soThis is an exact identity for every sign choice. Put $M(\xi )={\max }_i|a_i^T\hat{x}(\xi )|$. When $M>0$, the Rademacher rounding for a semidefinite relaxation givesHence $x(\xi )$ is feasible. In the finite spanning case from part (a), $\mathrm{tr}{X}^{\ast }>0$ makes $\hat{x}\ne 0$, and the spanning condition then gives $M>0$. If a nonzero $\hat{x}$ instead had $M=0$, it would be an unbounded feasible direction rather than a vector to divide by zero.

Set $u_i=(V{\Lambda }^{1/2}{)}^T{a}_i$. SDP feasibility impliesChoose $\alpha =\sqrt{2\log (2m)}$. For the uniform sign vector, whose coordinates are independent Rademacher random variables, the supplied bound for the maximum of finitely many Rademacher linear forms givesA positive-probability event in this finite space contains at least one sign vector. ThusThe strict inequality in the supplied probability estimate matters: at the chosen threshold its right-hand side is zero.

For that sign vector, part (b) gives a feasible original point satisfying $\Vert x(\xi ){\Vert }_2^2\ge p_{\mathrm{SDP}}^{\ast }/[2\log (2m)]$. Taking the best original objective proves the unheaded concluding request as well:This is the logarithmic approximation bound for slab-constrained quadratic maximization, obtained by the probabilistic method. It is a finite-value rounding guarantee under the spanning/attainment conditions explained above.