4
$\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.

$\endgroup$
6
$\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.

$\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$ Mar 12 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$ Mar 12 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$ Mar 12 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$ Mar 12 at 12:51
  • 1
    $\begingroup$ Set it to 2, as described in the links. $\endgroup$ Mar 12 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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