= Solution
For a feasible vector, set $X=xx^T$. It is a <positive semidefinite matrix>, and
$$
\operatorname{tr}(a_ia_i^TX)=a_i^Txx^Ta_i=(a_i^Tx)^2\le1,\qquad
\operatorname{tr}X=\|x\|_2^2.
$$
Thus 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>, proving
$$
\boxed{p_{\rm SDP}^*\ge v^*.}
$$
The original PDF has $|a_i^Tx|\le1$; 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=tdd^T$ unbounded feasible families, so both objective suprema are infinite. Under spanning, $H=\sum_i a_ia_i^T$ is a <positive-definite matrix> and
$$
\lambda_{\min}(H)\operatorname{tr}X\le\operatorname{tr}(HX)=\sum_i a_i^TXa_i\le m.
$$
The 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\ge1$. These facts justify the optimum and nonzero denominator used below. Assume $m,n\ge1$.
Back to article page
