5
$\begingroup$

I have the following problem:

I have an objective function with the optimization variable $x$, which looks simplified like this:

$ZF = (a+b)*(x+1)$

Here $a$ is simply a constant value. However, behind $b$ is a 4th degree polynomial which is dependent on my optimization variable $x$.

Now my idea was to create a constraint with GRBModel.addGenConstrPoly(), where $b$ is then also an optimization variable.

When I do that, I get the following error code back:

"Error code: 10020. Objective Q not PSD (diagonal adjustment of 6.5e+06 would be required). Set NonConvex parameter to 2 to solve model."

Maybe I am thinking completely wrong and someone can help me how I can enter my polynomial differently.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

This can be handled by transforming this to a bilinear problem, i.e., a problem only involving products of no more than 2 variables at a time.

This is accomplished by lifting the problem into a higher dimension, i.e., by introducing new variables and corresponding constraints.

For instance, the term $x^3$ can be made bilinear (quadratic), by introducing a new variable $y$, adding the constraint $y=x^2$, and rewriting $x^3$ as $xy$.

Let's say you have a term $x^2w$. Introduce a new variable $z$, add the constraint $z=xw$, and rewrite $x^2w$ as $xz$.

This can be extended to an arbitrary polynomial in any degree and number of variables, resulting in a bilinear formulation, which can be solved to global optimality (run time and memory permitting) by Gurobi 9.x. You will need to set the NonConvex parameter appropriately to handle a non-convex bilinear model.

Gurtobi 9.1 does not automate this for polynomials "above" bilinear (quadratic). Perhaps some future version might. Some optimization modeling systems actually do automate this; for instance, YALMIP automatically reformulates polynomial matrix inequalities as Bilinear Matrix Inequalities (BMI) by lifting (adding new variables and constraints).

This lifting approach is discussed at greater length in the context of linear matrix inequalities in Optimization on linear matrix inequalities for polynomial systems control. The general idea is the same for polynomial optimization.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you for the detailed answer! So if I understand you correctly, my way only works for 2nd degree polynomials? How and where can I set the NonConvex parameter appropriately to handle a non-convex bilinear model? $\endgroup$
    – Handballer73
    Commented Mar 12, 2021 at 9:28
  • 1
    $\begingroup$ I am not sure if chaining these 5 multiplications is better than a (clever) piecewise linear approximation for the 4th degree polynomial + a single non-convex multiplication. That would be worth of some quick experiments. Often these questions can only be answered by trying it out. $\endgroup$
    – Erwin Kalvelagen
    Commented Mar 12, 2021 at 12:15
  • $\begingroup$ @ Handballer73 The NonConvex parameter is just what you would set for a non-convex quadratic, because that's what the model you will enter is. $\endgroup$
    – Mark L. Stone
    Commented Mar 12, 2021 at 12:49
  • 1
    $\begingroup$ @Erwin Kalvelagen i don't claim this is the best way of solving the problem, but it is a way of entering exactly a problem corresponding to the original problem, with no approximations introduced. $\endgroup$
    – Mark L. Stone
    Commented Mar 12, 2021 at 12:51
  • 1
    $\begingroup$ Set it to 2, as described in the links. $\endgroup$
    – Mark L. Stone
    Commented Mar 12, 2021 at 19:55

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.