We present an algorithm for the global minimization of a quadratic function ψ(x, y) = −½xTQx + hTx + dTy, over a polytope Ω = {(x, y) ∈ ℝn+k: Ax + By ≤ b, x ≥ 0, y ≥ 0}, where x, h ∈ ℝn, y, d ∈ ℛk, b ∈ ℛm, and where A and B are m × n and m × k matrices, respectively, and Q is an n × n symmetric positive definite matrix. We first consider the case where k = 0 and construct a “tight” parallelpiped R, containing Ω by using an arbitrary set of Q-conjugate directions and by solving 2n linear programs. We show that the convex envelope of ψ with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each subproblem we obtain the linear convex envelope of ψ over a smaller parallelepiped, R′, with facets parallel to those of R. Then, we obtain a lower bound by minimizing this convex envelope over R′ ∩ Ω. If ψ* is the optimal objective value, for each ϵ ≥ 0, the algorithm generates a sequence of feasible points zj with nonincreasing function values ψj and a nondecreasing sequence Γj, of lower bounds to ψ*. Moreover if ϵ > 0, there exist j0 such that (ψj − Γj) ≤ ϵ for all j ≥ j0, and if ϵ = 0, (ψj − Γj) converges to 0. The results are then generalized to the case where k is nonzero and possibly much larger than n. Preliminary computational results are also presented.