Characteristics of a quadratically constrained program

Describes the characteristics of a quadratically constrained program.

The distinguishing characteristic of QCP is that quadratic terms may appear in one or more constraints of the problem. The objective function of such a problem may or may not contain quadratic terms as well. Thus, the most general formulation of a QCP is:

Minimize    ¹ / ₂x^TQx + c^Tx

subject to   Ax ~ b

and            a _i ^T x + x^TQ _i x ≤ r _i for i=1,...,q

with these bounds l ≤ x ≤ u

As in a quadratic objective function, convexity plays an important role in quadratic constraints. The constraints must each define a convex region. To make sure of convexity, IBM ILOG CPLEX requires that each Q _i matrix be positive semi-definite (PSD) or that the constraint can be transformed into a second order cone. The following sections offer more information about these concepts.