Why Does Gurobi Report "Non-Convex MINLP" for a Convex Logarithmic Objective?
AnsweredI am solving a convex optimization problem using Gurobi 12. My objective function is to minimize -\sum \log(p). The logarithmic function is concave, so the negative sum of logarithms should define a convex problem.
However, when I run my optimization, the Gurobi output console states:
`Solving non-convex MINLP`.
I understand that Gurobi treats nonlinear functions (e.g., `log`) by modeling them as MIP formulations, but I am confused as to why it identifies the problem as non-convex when the objective is convex.
Could someone explain why this happens? Is there something about the formulation or the way Gurobi handles such problems that could cause it to misinterpret the convexity?
Thank you!
-
-
Gurobi Staff
Hi Beyzanur,
Gurobi treats nonlinear functions (e.g., `log`) by modeling them as MIP formulations
I'm not sure what you mean by this. Are you referring to static piecewise linear approximations? If so then please note we provide alternative approaches as of version 11 (outer approximation and spatial branch-and-bound).
Could someone explain why this happens?
Log functions are indeed concave, and so are their weighted combination (with positive weights). For a problem to be convex, you can either maximize a concave objective function, or minimize a convex objective function. This may be easier to understand if you consider transforming the problem using the epigraph or hypograph. Eg
min log(x)
s.t. x >= 0is equivalent to
min y
y >= log(x)
x >= 0and y >= log(x) is not a convex constraint.
- Riley
- Riley
0 -
-
Hi Riley,
Thank you for the explanation. However I am already using this convex formulation:
min y
y >= -sum(log(x))
x >= 1e-6Despite this, when I run my program in Gurobi, the console states:
Solving non-convex MINLP and proceeds with root relaxation.
I am using Gurobi 12 with Julia.0 -
-
-
Hi Beyzanur,
My objective function is to maximize -\sum \log(p)
min y
y >= -sum(log(x))These are contradictory, can you clarify?
- Riley
0 -
-
Sorry for the confusion, maximizing is incorrect, should be minimizing- I updated my post now. I am minimizing negative sum of logarithms.
0 -
-
-
No problem, are you able to share a MPS file using a service such as dropbox, onedrive, Google Drive, github etc?
- Riley
0 -
-
Sure, here is the MPS file: https://github.com/beyzanuraydiin/grb_mps_file
Thank you.0 -
-
-
Hi Beyzanur,
It turns out that adding any of the new non-linear constraints introduced in v12 will designate the model as non-convex, even simple models:
m = gp.Model()
x = m.addVar(lb=1, ub=10)
y = m.addVar(obj=-1, lb=float("-inf"))
m.addConstr(y == nl.log(x))
m.optimize()This is similar to how quadratic equality constraints also designate the model as non-convex (which technically it is unless y is substituted out).
m = gp.Model()
y = m.addVar(obj=1, ub=1)
x = m.addVar()
m.addConstr(y == x*x)
m.optimize()If the theoretical model (without auxiliary variables and equality constraints introduced) is convex then we can expect it to be solved without too much trouble (compared to non-convex models).
At some time in the future we may introduce convexity recognition for some non-linear constraints.
- Riley
0 -
Please sign in to leave a comment.
Comments
7 comments