Solving problems with a quadratic objective (QP)

Describes solving quadratic programming problems (QPs) with CPLEX.

CPLEX solves quadratic programs; that is, a model in which the constraints are linear, but the objective function can contain one or more quadratic terms. These problems are also known as QP. When such problems are convex, CPLEX normally solves them efficiently in polynomial time. Nonconvex QPs, however, are known to be quite hard. In theoretical terms, they are characterized as NP-hard. CPLEX applies various approaches to those problems, such approaches as barrier algorithms or branch and bound algorithms. Notably, in the branch and bound approach, there is no theoretical guarantee about the complexity of such a problem. Consequently, solution of such a problem (that is, a nonconvex QP) can take many orders of magnitude longer than the solution of a convex QP of comparable dimensions. The following topics address the question of how to distinguish such problems and describe the facilities that CPLEX offers to solve them.