QCQP tuner difficulties

回答済み

Jacob Wren

2022年11月11日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:25

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  2022年11月14日 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

  2022年11月14日 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

  2022年11月14日 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.

  Best regards, 
  Jaromił

  0

投稿コメントは受け付けていません。