  Montanari and Richard (2015) asked whether a natural semidefinite programming
(SDP) relaxation can effectively optimize $\mathbf{x}^{\top}\mathbf{W}
\mathbf{x}$ over $\|\mathbf{x}\| = 1$ with $x_i \geq 0$ for all coordinates
$i$, where $\mathbf{W} \in \mathbb{R}^{n \times n}$ is drawn from the Gaussian
orthogonal ensemble (GOE) or a spiked matrix model. In small numerical
experiments, this SDP appears to be tight for the GOE, producing a rank-one
optimal matrix solution aligned with the optimal vector $\mathbf{x}$. We prove,
however, that as $n \to \infty$ the SDP is not tight, and certifies an upper
bound asymptotically no better than the simple spectral bound
$\lambda_{\max}(\mathbf{W})$ on this objective function. We also provide
evidence, using tools from recent literature on hypothesis testing with
low-degree polynomials, that no subexponential-time certification algorithm can
improve on this behavior. Finally, we present further numerical experiments
estimating how large $n$ would need to be before this limiting behavior becomes
evident, providing a cautionary example against extrapolating asymptotics of
SDPs in high dimension from their efficacy in small "laptop scale"
computations.
