Global Extremal Conditions for Multi-Integer Quadratic Programming(Abstract)

摘要

We consider a quadratic programming problem: min {P(x) = 1/2 -^s | x ∈ X_a}, where x and f are real g-dimensional vectors, Q ∈ R~(q x q) is a symmetric matrix of order q and X_a = {X ∈ R~q | x_i ∈E {c1, ··· , c_p}} with c_j being an integer for j =1, ···, p (p ≥ 3). We first transform this problem into a {—1,1} integer quadratic programming problem and then derive a "canonical dual". Regardless convexity, no duality gap exists between the primal problem and its canonical dual. We provide some global extremal conditions for this problem. Some computational examples are also provided to illustrate this approach.