An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions

We present an algorithm for the global minimization of a quadratic function ψ(x, y) = −½x^TQx + h^Tx + d^Ty, over a polytope Ω = {(x, y) ∈ ℝ^n+k: Ax + By ≤ b, x ≥ 0, y ≥ 0}, where x, h ∈ ℝⁿ, 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 z_j with nonincreasing function values ψ_j and a nondecreasing sequence Γ_j, of lower bounds to ψ*. Moreover if ϵ > 0, there exist j₀ such that (ψ_j − Γ_j) ≤ ϵ for all j ≥ j₀, 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.