quadratic quotient programming

回答済み

Xiaoyu Shan

2022年04月12日 20:42

• 
• 
• 

Can Gurobi solve integer programming whose objective function is in the form of quadratic quotient? e.g. min x'Qx/x'Px, where x's are binary, P and Q are positive semidefinite. 

0

• 

  Maliheh Aramon

  • Gurobi Staff

  2022年04月13日 02:47

  Hi Xiaoyu, 

  No, Gurobi does not directly support solving an optimization problem with an objective function in the form \(\frac{x^\prime Q x}{x^\prime P x}\). Please check the article on What types of model can Gurobi solve? for the list of models that Gurobi solves.

  You can consider defining an auxiliary variable \(y\) and solve the following optimization problem (assuming minimization):

  \[\begin{align} \min~~ y & \notag \\ \mathrm{st:}~~  & x^\prime Q x - y (x^\prime P x) \leq 0 \notag \end{align}\]

  This is a nonconvex problem and the term \(y (x^\prime P x)\) includes multilinear terms that you need to model using a series of bilinear constraints. You can check the article on How do I model multilinear terms in Gurobi?

  Best regards,

  Maliheh

  0

サインインしてコメントを残してください。