  We present a technique for producing valid dual bounds for nonconvex
quadratic optimization problems. The approach leverages an elegant piecewise
linear approximation for univariate quadratic functions due to Yarotsky,
formulating this (simple) approximation using mixed-integer programming (MIP).
Notably, the number of constraints, binary variables, and auxiliary continuous
variables used in this formulation grows logarithmically in the approximation
error. Combining this with a diagonal perturbation technique to convert a
nonseparable quadratic function into a separable one, we present a
mixed-integer convex quadratic relaxation for nonconvex quadratic optimization
problems. We study the strength (or sharpness) of our formulation and the
tightness of its approximation. Further, we show that our formulation
represents feasible points via a Gray code. We close with computational results
on problems with quadratic objectives and/or constraints, showing that our
proposed method i) across the board outperforms existing MIP relaxations from
the literature, and ii) on hard instances produces better bounds than exact
solvers within a fixed time budget.
