Conventionally, a quadratic program (QP) is formulated this way:

Minimize 1/2 xTQx + cTx

subject to Ax ~ b

with these bounds l x u

where the relation ~ may be any combination of equal to, less than or equal to, greater than or equal to, or range constraints. As in other problem formulations, l indicates lower and u upper bounds. Q is a matrix of objective function coefficients. That is, the elements Qjj are the coefficients of the quadratic terms xj2, and the elements Qij and Qji are summed together to be the coefficient of the term xixj.

ILOG CPLEX distinguishes two kinds of Q matrices:

• In a separable problem, only the diagonal terms of the matrix are defined.

• In a nonseparable problem, at least one off-diagonal term of the matrix is nonzero.

ILOG CPLEX optimizes only convex quadratic minimization problems or equivalently, only concave quadratic maximization problems, as illustrated in Figure 7.1. For convex QPs, Q must be positive semi-definite; that is, the term x'Qx 0 for all x, whether or not x is feasible. For concave maximization problems, the requirement is that Q must be negative semi-definite; that is, x'Qx 0 for all x. In a minimization problem, if Q is separable and positive semi-definite, then Q 0.

Figure 7.1 Maximize a Concave Objective Function, Minimize a Convex Objective Function

In this chapter, we assume you have some familiarity with quadratic programming. For a more complete explanation of quadratic programming generally, we recommend you consult a text such as one of those listed in Further Reading.