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^TQx + c^Tx

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², and the elements Q_ij and Q_ji are summed together to be the coefficient of the term x_ix_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.

Figure 1. Minimize a convex objective function, maximize a concave objective function

Minimize a convex objective function, maximize a concave objective function graphic

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^TQx ≥ 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^TQx ≤ 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.