2
$\begingroup$

I have a QP problem as

$\min \hspace{2mm} x^TQx-c^Tx$

here $x$ in binary

I want to transform it into a MILP by writing the objective function as

$\min \hspace{2mm} z-c^Tx$

and then adding a constraint

$x^TQx-z\le 0$

I can further linearize the above constraint with first order Taylor approximation as below

$-x_0^TQx_0+2x_0^TQx-z\le 0$

here $x_0$ is initial/feasible point.

Am I doing it right?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Is your matrix Q positive semidefinite? $\endgroup$
    – Kevin Dalmeijer
    Commented Apr 19 at 15:45
  • $\begingroup$ Is there a reason you want to settle for an approximation as opposed to exactly linearizing the quadratic term (at the cost of additional variables and constraints)? $\endgroup$
    – prubin ♦
    Commented Apr 19 at 15:57
  • $\begingroup$ @prubin I really don't know which one is a better option. If we go for MILP (by linearizing the multiplicative terms of binary variables), we add a lot of constraints. For this particular problem I already have 1000+ constraints (all linear though!) $\endgroup$
    – KGM
    Commented Apr 19 at 16:27
  • $\begingroup$ @KevinDalmeijer no, Q is not a PSD matrix $\endgroup$
    – KGM
    Commented Apr 19 at 16:41
  • 2
    $\begingroup$ @KevinDalmeijer and prubin, $Q$ is symmetric and positive definite without loss of generality, the latter because $x$ is binary and you can thus add $|\lambda_\min| \sum_i (x_i^2−x_i)$ to the objective function to make the Hessian diagonally dominant. $\endgroup$
    – RobPratt
    Commented Apr 19 at 20:00

1 Answer 1

Reset to default
2
$\begingroup$

Let's assume that, per Rob Pratt's comment, your $Q$ is symmetric and positive definite. Your approximation is correctly derived, and you can certainly try it. Due to convexity, the linear approximation will be conservative, so you may get values of $z$ that are smaller than they should be, leading to incorrect (suboptimal) solutions.

Linearizing the product exactly would involve a bit over a half million new continuous variables and two to three times that many new constraints. The added constraints would mercifully be sparse. Depending on the dimensions of the rest of your problem (and your computational horsepower and patience), it's quite possible that a good quality MIP solver could handle the linearized version.

Most current commercial solvers (and at least some open source solvers) can handle convex quadratic objectives and second order cone constraints, so you could solve the problem with no modifications or with the constraint $x' Q x - z \le 0,$ without the tangential approximation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ From the annals of nitpicking: Technically, that constraint is a convex quadratic constraint, which can be reformulated (after factorization) into a Second Order Cone constraint. Second Order Cone constraints are more general than convex quadratic constraints. That doesn't affect your advice however. $\endgroup$
    – Mark L. Stone
    Commented Apr 24 at 19:15
  • $\begingroup$ @MarkL.Stone You are of course correct. $\endgroup$
    – prubin ♦
    Commented Apr 24 at 20:01

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