QCQP tuner difficulties

Answered

Jacob Wren

November 11, 2022 20:53

• 
• 
• 

Hello,

Gurobi is unable to solve my convex quadratically-constrained quadratic program (QCQP) for certain values of a tuning parameter.

This is my explanation. 

Call the tuning parameter epsilon. When epsilon is taken to be small, the program becomes essentially non-convex.
The issue in 2 dimensions is that ||x|| <= c is a convex set, but ||x|| = c is not.
So if we know ||x|| >= c, and we constrain ||x|| <= c + epsilon for small epsilon, it starts looking like ||x|| = c.

Any thoughts?

Thanks,

Jake

0

• 

  Jaromił Najman

  • Gurobi Staff

  November 14, 2022 09:15

  Hi Jake,

  When epsilon is taken to be small, the program becomes essentially non-convex.

  How small is your epsilon in the nonconvex case? Your approach can lead to numerical difficulties if epsilon is very small, i.e., it is close or smaller than Gurobi's tolerances.

  It might be best to solve the model as a nonconvex one instead of trying to "trick" it into a convex one. If there is no hope for solving the nonconvex model, you could try relaxing the PSDTol. Please note that usually playing with tolerance is not a good idea as this may lead to all sorts of numerical trouble.

  Best regards, 
  Jaromił

  0
• 

  Jacob Wren

  November 14, 2022 17:01

  • 
  • 
  • 

  Hi Jaromił,

  It might be best to solve the model as a nonconvex one instead of trying to "trick" it into a convex one. 

  Two questions:

  1) How do I know at what value of epsilon the model goes from convex to nonconvex?

  2) How should I let Gurobi know this (I previously set Method=2)?

  Thanks,

  Jake

   

  0
• 

  Jaromił Najman

  • Gurobi Staff

  November 14, 2022 20:01

  Hi Jake,

  1) How do I know at what value of epsilon the model goes from convex to nonconvex?

  I am not sure whether this can even be calculated rigorously. If you have a tight upper bound \(U\) on \(||x||\) then you could use it to compute \(\epsilon = U - c\). But I guess that computing such an upper bound is not practical and the bound probably would be very weak.

  2) How should I let Gurobi know this (I previously set Method=2)?

  You can set the NonConvex parameter to 2 even if your model is convex. This way you will prevent running into an error when your model becomes nonconvex.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.