1
$\begingroup$

My problem is described in this picture: enter image description here $$ \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?

$\endgroup$
5
  • 2
    $\begingroup$ Welcome to OR.SE. It would be good if you can format your objective function and constraints using MathJax: or.meta.stackexchange.com/questions/5/… $\endgroup$
    – TheSimpliFire
    Commented Nov 28, 2022 at 17:39
  • 1
    $\begingroup$ I have attempted to convert part of your text to MathJax to help you get started. Please check it for correctness and convert the remaining image to an array. Thanks. --- PS: Next time (don't!) upload a higher resolution image; convert images containing MathJax, tables and text to MathJax. $\endgroup$
    – Rob
    Commented Nov 28, 2022 at 18:08
  • $\begingroup$ Thank you! I will consider next time. $\endgroup$
    – happy
    Commented Nov 29, 2022 at 7:58
  • $\begingroup$ What is the motivation for this question? Where does this optimization problem come from? $\endgroup$ Commented Nov 29, 2022 at 17:41
  • $\begingroup$ It comes from a scatter plot sampling problem. $\endgroup$
    – happy
    Commented Nov 30, 2022 at 2:29

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you. It helps me a lot!! $\endgroup$
    – happy
    Commented Nov 30, 2022 at 2:28
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.