4
$\begingroup$

I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). The other constraints are all linear. In addition, I have equality and inequality constraints. What methods are there to optimize this?

I see two options:

  • Convex optimization methods (but they might be inefficient, given that my loss is linear.
  • Use methods for quadratic objectives and just use them with linear objective functions.

Google mostly lists proprietary software instead of papers to read.

Any better suggestions that are explicitly made for QCMILP (quadratically constrained mixed integer linear programs?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Having a linear objective won't particularly help. Actually, you can always reformulate a QCQP to have a linear objective by minimizing $z$ subject to $z = \mathrm{obj}$. However, having a single quadratic constraint should favor methods based on linear approximations, which are the ones usually implemented by exact MIQCQP solvers (Gurobi, Cplex...) $\endgroup$
    – fontanf
    Commented Mar 1, 2023 at 8:33
  • 3
    $\begingroup$ Maybe not useful, but $x^Ty\le z$ can be linearized (with some effort) using the fact that $x$ is integer-valued. (Hint: Expand using binary variables and then linearize the terms). $\endgroup$
    – Erwin Kalvelagen
    Commented Mar 1, 2023 at 15:46
  • $\begingroup$ I don't think solvers like Cplex and Gurobi will automatically linearize quadratic terms with general integer variables, but only with binary variables. $\endgroup$
    – Erwin Kalvelagen
    Commented Mar 1, 2023 at 16:03
  • 2
    $\begingroup$ The quadratic constraint, $x^T y \leq z$, is not convex in general as the Hessian is indefinite. Please update your question to reflect this. $\endgroup$
    – Henrik Alsing Friberg
    Commented Mar 2, 2023 at 12:50

1 Answer 1

Reset to default
2
$\begingroup$

Gurobi can solve mixed integer quadratically constrained problems provided that your known values in the quadratic constraint form positive semidefinite matrix. You'd need to use Quadratic Constraint to model the constraints. Gurobi will linearly relax using either interior points or outer approximation.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Gurobi can also solve non-convex MIQCQPs after setting the NonConvex Parameter accordingly. So the matrix doesn't need to be positive semidefinite. $\endgroup$
    – joni
    Commented Mar 3, 2023 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.