Linearize quadratic continuous constraints



1 comment

  • Jaromił Najman

    Hi Ana,

    Since version 9.0 Gurobi has the capability of solving non-convex 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 non-convex 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 non-convex, you just have to set the NonConvex parameter to 2.

    - With this quadratic constraint, is my problem non-convex? or convexity does not depend on the type of constraints?

    Just adding a quadratic constraint does not make your problem non-convex. 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 Non-Convex Quadratic Optimization. It holds all essential information on Gurobi's non-convex feature.

    Best regards,

    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk