the minimization problem is given by
\begin{array}{cl}
\min_{x,y} &\displaystyle\sum_{i=1}^{K} \frac{y_{i}}{Y}\left[\frac{x_{i}}{y_{i}} - \frac{X}{Y}\right]^2 \\
s.t& \sum_{i=1}^{K} x_{i} = X \\
&\sum_{i=1}^{K}y_{i}=Y \\
& x_{i}\leqslant y_{i}\\
&x_{i},y_{i}\in\mathbb{Z}^{+}
\end{array}
The problem is non-convex and highly rational. If we were to fix one of the variables then CVXPY can solve this easy. However, I am wondering if theres a way around to solve problem if we can reformulate the objective function and constraint in another way.
There must be some constraints/bounds you are not telling us about, since this problem can be solved analytically.
1 Like
I have edited the constraints after I forgot an additional constraint. Thank you for the notice, I think the most important detail is that the decision variables are both positive and that one is always a bound to other.
For the sake of simplification I am mainly interested in the case of K=3. This somewhat resembles the quadratic integer knapsack problem which was addressed by Bretthauer et al. (1995). However, this problem becomes highly rational and non-convex.
So X,Y are constants? Then the objective develops (up to constant stuff we can ignore) to \sum_i \frac{x_i^2}{y_i} which is a sum of quad_over_lin so it is a natural mixed-integer SOCP. You can just input it as is.
Hmm, I see. Alternatively, if we define z_{i}\triangleq\frac{1}{y_{i}} and we instead minimize \sum_{i} z_{i}Y(x_{i}z_{i} - m)^{2} subject to x_{i}z_{i}-m=0 and \sum_{i}x_{i}=X and x_{i} z_{i}\leqslant 1 would this work with some CVXPY optimizer? The constraints are bi-linear.
I don’t understand what you are trying to achieve. It looks like overcomplicating a simple matter. For example how will you include the integrality constraint on y through z.
All mixed-integer SOCP optimizers under CVX and CVXPY will be able to solve the formulation I proposed.
I agree with your assertion. Thank you very much for your suggestions I will implement the code now!
Hello once more, I tried using quad_over_lin, but based on the arguments I have ‘x’ and ‘y’, the latter is a vectir not a scalar (I am facing an error saying that the second argument must be scalar). The idea is that I want the computations of x and y to be scalar as I am eventually computing the term \sum_{i}\frac{x_{i}^{2}}{y_{i}} for each i which is a scalar. Thus, the problem is that \textsf{obj = cp.sum(cp.quad_over_lin(x,y))} does not work.
You are asking a CVXPY question on the CVX forum.
But anyway, you just have to do it index by index then, something like
obj = cp.sum(cp.quad_over_lin(x[i],y[i]) for i in range(n))
or whatever of this kind compiles.
1 Like