5

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.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Handballer73
  • 301
  • 1
  • 7

1 Answers1

8

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.

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • 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? – Handballer73 Mar 12 '21 at 09:28
  • 1
    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. – Erwin Kalvelagen Mar 12 '21 at 12:15
  • @ 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. – Mark L. Stone Mar 12 '21 at 12:49
  • 1
    @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. – Mark L. Stone Mar 12 '21 at 12:51
  • @MarkL.Stone can be that I have not yet understood correctly with the non convex...so if I understand correctly I must enter there no extra command...because in the error it was also said that I should set it equal to 2...but I do not know with which command or where I can do that. I have nowhere written anything like that in my code – Handballer73 Mar 12 '21 at 16:32
  • @Handballer73 Set NonConvex https://www.gurobi.com/documentation/9.1/refman/nonconvex.html in Java per examples at https://www.gurobi.com/documentation/9.1/refman/java_parameter_examples.html#JavaParameterExamples – Mark L. Stone Mar 12 '21 at 16:45
  • @MarkL.Stone Thank you, I have already read that too. The question for me is actually what is meant by this parameter...do I need to define it or which one is it in my problem described above? I am still absolutely not familiar with it I must honestly confess. – Handballer73 Mar 12 '21 at 16:56
  • I know these are very primitive questions and I am sorry for that, I would still appreciate any help – Handballer73 Mar 12 '21 at 17:06
  • 1
    Set it to 2, as described in the links. – Mark L. Stone Mar 12 '21 at 19:55