Identifying a Quadratically Constrained Program (QCP)

INDEX PREVIOUS NEXT

The inequality x² + y² 1 is convex. To give you an intuitive idea about convexity, Figure 12.1 graphs that inequality and shades the area that it defines as a constraint. If you consider a and b as arbitrary values in the domain of the constraint, you see that any continuous line segment between them is contained entirely in the domain.

Figure 12.1 x² + y² 1 is convex

The inequality x² + y² 1 is not convex; it is concave. Figure 12.2 graphs that inequality and shades the area that it defines as a constraint. If you consider c and d as arbitrary values in the domain of this constraint, then you see that there may be continuous line segments that join the two values in the domain but pass outside the domain of the constraint to do so.

Figure 12.2 x² + y² 1 is not convex

It might be less obvious at first glance that the equality x² + y² = 1 is not convex either. As you see in Figure 12.3, there may be a continuous line segment that joins two arbitrary points, such as e and f, in the domain but the line segment may pass outside the domain. Another way to see this idea is to note that an equality constraint is algebraically equivalent to the intersection of two inequality constraints of opposite sense, and you have already seen that at least one of those quadratic inequalities will not be convex. Thus, the equality is not convex either.

Identifying a Quadratically Constrained Program (QCP) explained that the quadratic matrix in each constraint must be positive semi-definite (PSD), thus providing convexity. A matrix Q_i is PSD if x^TQ_ix 0 for every vector x, whether or not x is feasible. Other issues pertaining to positive semi-definiteness are discussed in the context of a quadratic objective function in Identifying Convex QPs.

There is one exception to the PSD requirement; that is, there is an additional form of quadratic constraint which is accepted but is not covered by the general formulation in Identifying a Quadratically Constrained Program (QCP). Technically, the quadratically constrained problem class that the barrier optimizer solves is a Second-Order Cone Program (SOCP). ILOG CPLEX, through its preprocessing feature, makes the translation to SOCP for you, transparently, returning the solution in terms of your original formulation. A constraint will be accepted for solution by the barrier optimizer if it can be transformed to the following convex cone constraint: