# Distinguishing between convex and nonconvex QPs

Explains how to determine the convexity of a quadratic program.

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

Minimize 1/2 x^{T}Qx + c^{T}x

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
Q_{jj} are the coefficients of the
quadratic terms x_{j}^{2},
and the elements Q_{ij} and Q_{ji} are
summed together to be the coefficient of the term x_{i}x_{j}.

IBM ILOG CPLEX distinguishes between two kinds of Q matrices:

In a

*separable*problem, only the diagonal terms of the matrix are defined; all off-diagonal terms of the matrix are zero.In a

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

CPLEX can solve minimization problems having a convex quadratic objective function. Equivalently, it can solve maximization problems having a concave quadratic objective function. All linear objective functions satisfy this property for both minimization and maximization. However, you cannot always assume this property in the case of a quadratic objective function.

CPLEX can also compute points that are **local optima**; that is, those
points satisfy *first-order optimality conditions* of
models with arbitrary quadratic objective functions. These models
include minimization problems with a concave objective function, maximization
problems with a convex objective function, and either minimization
or maximization problems with objective functions that are neither
convex nor concave. Such points may not be the globally optimal solution
to the model.

Intuitively, recall that any point on the line between two arbitrary points of a convex function will be above that function. In more formal terms, a continuous segment (that is, a straight line) connecting two arbitrary points on the graph of the objective function will not go below the objective of a minimization problem, and equivalently, the straight line will not go above the objective of a maximization problem. The image Figure 1 illustrates this intuitive idea for an objective function in one variable. It is possible for a quadratic function in more than one variable to be neither convex nor concave.

In formal terms, the question of whether a quadratic
objective function is convex or concave is equivalent to whether the
matrix Q is positive semi-definite or negative semi-definite. For
convex QPs, Q must be positive semi-definite; that is, x^{T}Qx `≥`

0
for every vector x, whether or not x is feasible. For concave maximization
problems, the requirement is that Q must be negative semi-definite;
that is, x^{T}Qx `≤`

0
for every vector x. It is conventional to use the same term, positive
semi-definite, abbreviated PSD, for both cases, on the assumption
that a maximization problem with a negative semi-definite Q can be
transformed into an equivalent PSD.

For a **separable** function, to determine the convexity of a problem,
it is sufficient to check whether
the individual diagonal elements of the matrix Q are of the correct
sign to make sure of positive or negative semi-definiteness.
For the **nonseparable** case, it may be less easy to decide in advance
the convexity of Q. However, CPLEX detects this property during the
early stages of optimization.

By default, CPLEX terminates if the quadratic objective
term in a QP is found to be non PSD. In such a case, in order to instruct
CPLEX not to terminate, you must set the
optimality target parameter.
The value that you set for that parameter depends on the type of results that you expect.
If you would like CPLEX to compute a point that satisfies **first-order
optimality conditions** (that is, a local optimum), then you set the parameter to
the value CPX_SOLUTIONTARGET_FIRSTORDER.
If you would like CPLEX to find a **global optimum**, then you set the parameter to
the value CPX_SOLUTIONTARGET_OPTIMALGLOBAL.

For a more complete explanation of quadratic programming generally, a textbook, such as one of those listed in Further reading of the preface of this manual, may be helpful.