How to solve this mixed integer quadratic program using cvxpy or other method?

Question

My problem is described in this picture: $$ \begin{array}{l} \left\{\begin{array}{l} \text { objective function: } \\ f = \min \sum_\limits{l=1}^2 \sum_\limits{i=0}^{2^l-1} \sum_\limits{j=0}^{2^l-2}\left(A_{i j}^l / A_{j +l}^l-D_{i j}^l / D_{ijH}^l\right)^2 \\ \text { constraints: } \\ A_{i j}^l-A_{2i \ 2j}^{l+1}-A_{2iH \ 2 j}^{l+1}-A_{2i \ 2jH}^{l+1}-A_{2iH \ 2jH }^{l+1}=0 \\ A_{i j}^l \leqslant V_{i j}^l \\ \end{array}\right. \end{array} $$

In this problem, D and V is known, A is the object that I want to get. It is a layered structure, each block in the upper layer is divided into four sub-blocks in the figure below.

What I want to do is simulate the distribution of D with A, so in the objective function is the ratio of two adjacent squares in each row in A compared to the value in D. I do this comparison on each layer and sum them. Then it is all of my objective function.

Also I have two constraints. The first is in A the value in the upper cell is equal to the sum of the four child nodes in the lower layer, just like the D and V. The second is the value in A is no more than the value in V in the same position.

I have tried the CVXPY library in python. But it seems my objective function is not a convex function so it can't solve it. My code is like:

first_layer = cp.Variable((2,2), integer=True)
second_layer = cp.Variable((4,4), integer=True)

for i in range(0,2):
    for j in range(0,1):
        cost += (first_layer[i][j] / first_layer[i][j+1] - D[1][i][j] / D[1][i][j+1])**2

for i in range(0,4):
    for j in range(0,3):
        cost += (second_layer[i][j] / second_layer[i][j+1] - D[2][i][j] / D[2][i][j+1])**2

constraints = []
for i in range(0,2):
    for j in range(0,2):
        constraints += [A[i][j] - A[2*i][2*j] - A[2*i+1][2*j] - A[2*i][2*j+1] - A[2*i+1][2*j+1] == 0]

for i in range(0,2):
    for j in range(0,2):
        constraints += [A[i][j] - V[i][j] <= 0]

objective = cp.Minimize(cost)
prob = cp.Problem(objective,constraints)
prob.solve(solver='ECOS_BB')

And the result is:

cvxpy.error.DCPError: Problem does not follow DCP rules. Specifically:
The objective is not DCP. Its following subexpressions are not:

It seems I violation the DCP rules [https://www.cvxpy.org/tutorial/dcp/index.html], because it saysexpr1*expr2, expr1/expr2, and expr1@expr2 can only be DCP when one of the expressions is constant.My objective function has the term x1/x2 so it can't works. But is DGP rules [https://www.cvxpy.org/tutorial/dgp/index.html] or DQP rules[https://www.cvxpy.org/tutorial/dqcp/index.html] works? I'm not sure.

So, I really don't know how to solve this type of problem? I'm even not sure it is what type of question. What type of objective function is this and how can I solve it?

Answer 1

Maybe work with a slightly different objective. Basically, you want:

$$ A_{i j}^l / A_{j +l}^l \approx D_{i j}^l / D_{ijH}^l $$

You could do:

$$ \min \sum |A_{i j}^l - A_{j +l}^l \cdot D_{i j}^l / D_{ijH}^l | $$

This is now linear (CVXPY can linearize the absolute value for you).

A detail: maybe exclude: $A_{j +l}^l=0$. That may need an extra binary variable if $A$ can be negative. (I am not sure how you want to interpret $A_{j +l}^l=0$).

Note that this approach will give somewhat different solutions than your model. But it will do a similar thing. If you want to stick to your objective, I think you may need to look at a different tool, such as a (global) MINLP solver.

Answer 2

Try with constraint:
$x_{i}*y_{i}=1$.
Then replace $x_i$ with $y_i$ in the objective.