Linearize quadratic continuous constraints
AnsweredHello,
I am formulating a problem to be solved with Gurobi. One of my constraints is quadratic. I know I can linearize the constraints if at least one of the involved variables is binary. I read at some point that, if both of variables are continuous, it can not be linearized. And this is my problem, I want to multiply x and y and both are continuous (>=0) I added it to the model and it is solved without problems. My questions are:
 is this solution totally correct? I supposse so, because Gurobi works with quadratic constraints
 linearization is for reducing complexity of solving time or does it have any other purpose?
 I am using gurobi to solve a theoretical problem which will be explained in a paper. Mathematically, is it ok to ensure that Gurobi can solve this kind of problems?
 With this quadratic constraint, is my problem nonconvex? or convexity does not depend on the type of constraints?
Thanks

Hi Ana,
Since version 9.0 Gurobi has the capability of solving nonconvex quadratic optimization problem. This means that your model is allowed to have terms \(x\cdot y\) where both variables are continuous, binary, integer or a combination of these.
 is this solution totally correct? I supposse so, because Gurobi works with quadratic constraints
The solution is totally correct up to computational tolerances specified by the FeasibilityTol and IntFeasTol parameters which allow for small violations. This tolerances are necessary, since Gurobi's algorithms work with floating point number, i.e., are limited by the floating point precision.
 linearization is for reducing complexity of solving time or does it have any other purpose?
It is most often better to reformulate a bilinear product \(b \cdot x\), where \(b\) is binary and \(x\) continuous in a linear fashion. This is performed automatically by Gurobi. However, there are rare cases where keeping the original bilinear form may be profitable. This can be controlled by the parameter PreQLinearize. Please note that providing tight finite variable bounds for all continuous variables occurring in nonlinear terms is key for an efficient solution of quadratic programs. This is especially important for nonconvex problems.
 I am using gurobi to solve a theoretical problem which will be explained in a paper. Mathematically, is it ok to ensure that Gurobi can solve this kind of problems?
As long as your problem falls into the MIQCQP category, Gurobi can tackle this problem. In case, that your problem is nonconvex, you just have to set the NonConvex parameter to 2.
 With this quadratic constraint, is my problem nonconvex? or convexity does not depend on the type of constraints?
Just adding a quadratic constraint does not make your problem nonconvex. For example, the function \(x^2 + 2xy + y^2\) is convex while \(x^2 + 5xy + y^2\) is not. Both functions have square and bilinear terms but the hessian properties of the two functions differ. The convexity of a quadratic program depends on the properties of the quadratic coefficient matrix.
I recommend having a look at our Webinar on NonConvex Quadratic Optimization. It holds all essential information on Gurobi's nonconvex feature.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment