Minimization Problem of a quadratic MIP with a rational term

1

Consider the following quadratic MIP:

\begin{array}{cl} \displaystyle\min_{x,y}&\displaystyle\sum_{i=1}^{K}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2} \\[0.2cm] \mathrm{s.t.}&\sum_{i}x_{i}=X \\[0.2cm] &\sum_{i}y_{i}=Y \\[0.2cm] &x_{i}\leqslant y_{i} \\[0.2cm] &x_{i},y_{i}\in\mathbb{Z}^{+} \end{array}

CVXPY does not have a framework for this type of problem. To fix things a bit, I defined an auxiliary variable f_{i}\triangleq\frac{x_{i}}{y_{i}}. Thus, define the new minimization problem:

\begin{array}{cl} \displaystyle\min_{x,y}&\displaystyle\sum_{i=1}^{K}\left(f_{i}-\frac{X}{Y}\right)^{2} \\[0.2cm] \mathrm{s.t.}&y_{i}f_{i}-x_{i}=0 \\[0.2cm] & f_{i}\leqslant 1 \\[0.2cm] &\sum_{i}x_{i}=X \\[0.2cm] &\sum_{i}y_{i}=Y \\[0.2cm] &x_{i},y_{i}\in\mathbb{Z}^{+} \end{array}

This time, CVXPY highlights that the constraints (the first constraint) do not follow the required form for the optimizer to solve this (I am using \textsf{gurobi}) I thought if the constraints were bi linear then CVXPY would handle this.

I would be thankful for assistance in trying to simulate this minimization problem.

\text{Remark}: In a previous post of mine, the objective function was basically sum of product that expanded to a quad_over_lin term which is resolved easily by cvxpy. However, I couldn’t find anything of this sort for dealing with square of rational of positive integers.

1 Like
2

Even though the question is for CVXPY, I’ll allow it here due to relevance also to CVX. However, the syntax to implement a formulation might be different for CVX and CVXPY.

That said, x^2/y^2 is neither convex nor concave, even for i = 1. It’s Hessian at x = y = 1 has one positive and one negative eigenvalue. Therefore, it is not suitable for CVX.

Nor CVXPY, unless you possibly make use of some extended capability to address non-convex problems (nor complying with DCP rules); The details of any such extended capability are off-topic in the CVX forum, and should be addressed in a CVXPY. venue

3

Maybe you should post the problem in a general page like

It seems like an interesting modeling question. And not only that, since the problem looks very combinatorial there may be better ways to solve it than using an optimizer.

For example it seems (??) like each x_i should be \lfloor X/K\rfloor or \lceil X/K\rceil and similarly for y_i to best approximate the (obvious) continuous solution.

1 Like