Quadratic Constraints
A quadratic constraint allows you to restrict the value of a quadratic
expression. For example, you may require that any feasible solution
satisfy the constraint
. Note that the
matrix-oriented Gurobi APIs (C, MATLAB, and R) require the right-hand
side of a quadratic constraint to be a constant, while the
object-oriented APIs (C++, Java, .NET, and Python) allow arbitrary
quadratic expressions on both sides of the comparator.
The computed solution should satisfy the stated constraint to within FeasibilityTol. Quadratic constraints are often much more challenging to satisfy than linear constraints, so tightening the parameter may increase runtimes dramatically.
Gurobi can handle both convex and non-convex quadratic constraints. However, there are some subtle and important differences in how the different constraint types are handled. In general, it is much easier to solve a model whose constraints all have convex feasible regions. It is actually quite difficult to recognize all such cases, but the following forms are always recognized:
-
, where 
is Positive Semi-Definite (PSD)
-
, where is Positive Semi-Definite (PSD),
is a vector of variables, and
is a non-negative variable (a Second-Order Cone constraint,
if 
, identity matrix)
, where is Positive Semi-Definite (PSD),
is a vector of variables,
and and 
are non-negative variables
(a rotated Second-Order Cone constraint, if , identity matrix)
Why distinguish between convex and non-convex quadratic constraints? In some situations you may know that your problem should be convex, and thus it may be a sign of a modeling error if your model isn't recognized as such. To avoid accidentally solving a much harder problem than you may have intended, you can set the NonConvex parameter to either 0 or 1. In the default setting of -1 or if the NonConvex parameter is set to 2, Gurobi will accept arbitrary quadratic constraints and attempt to solve the resulting model using the appropriate algorithm.
Note that other non-convex quadratic solvers often only find locally optimal solutions. The algorithms in Gurobi explore the entire search space, so they provide a globally valid lower bound on the optimal objective value, and given enough time they will find a globally optimal solution (subject to tolerances).
We would like to note a subtle point here regarding terminology. A quadratic constraint that involves only products of disjoint pairs of variables is often called a bilinear constraint, and a model that contains bilinear constraints is often called a bilinear program. Bilinear constraints are a special case of non-convex quadratic constraints, and the algorithms Gurobi uses to handle the latter are also well suited to solving bilinear programming problems.
