Is the solution to an MINLP problem the global optimum to this problem?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ some solvers like BARON can find the MINLP optimum solution and guarantees global optimality. $\endgroup$– Oguz ToragayJul 13, 2020 at 21:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
This question is a matter of semantics.
If by "solution", you mean the global optimum, then yes, "the" (a) solution to an MINLP is a global optimum (note that some problems have more than one globally optimum solution).
If, however, by "solution", you mean a local, but not necessarily, global, optimum, then the solution to an MINLP is not necessarily a global optimum.
As pointed out in a comment by @Oguz Toragay, branch and bound global optimizers, such as BARON, among others, attempt to find a global optimum. However, under computing time constraint (and to a lesser extent, memory constraint), they do not always succeed in reducing the gap (upper bound minus lower bound) to a satisfactory level. They can also run into numerical trouble and fail or produce an incorrect solution, no matter how much time or memory they are given. The only guaranteed protection against producing incorrect solutions due to bad numerics (scaling) is to use an interval-analysis-based solver with outward rounding. But interval-analysis-based global solvers are even less likely to reach a satisfactory conclusion.
Some MINLP solvers, such as KNITRO, employ algorithms which will find the global optimum (if given enough computing time and memory) for problems for which the continuous relaxation is convex; But these algorithms are only heuristic, and not even guaranteed to find a local optimum, for problems for which the continuous relaxation is non-convex - the reported gap can even be negative (better than globally optimal, ha ha) because the algorithm may assume subproblems have been solved to global optimality, when in the absence of convexity, that may not be the case.
answered Jul 14, 2020 at 5:32
-
$\begingroup$ The last paragraph of your comment is exactly what caused my confusion. They (researchers, developers,...) distinguish between convex and non-convex MINLP relaxations. $\endgroup$– ClementJul 14, 2020 at 7:01
-
$\begingroup$ @Clement If we are minimizing, we have convex relaxations. If we are maximizing, we have concave relaxations. There's also certain niche methods like edge concave relaxations that we can use when minimising, but that's not the norm. In the context of a relaxation that is algorithmically useful, non-convex is misleading - it's simply concave. $\endgroup$ Jul 14, 2020 at 9:11
-
$\begingroup$ To further clarify, by "continuous relaxation is convex", I mean exactly that if integarlity constraints are iingnored , the problem is convex, which means minimizing a convex function subject to convex constraints, or maximizing a concave function subject to convex constraints. In this context, non-convex does not ,mean concave. Do not be confused iwith other meanings of relaxation, which occur in the context of (branch and bound) global optimizers - in the course of solving the problem, the global optimizer may spawn convex relaxations of the original problem, for instance by ,,, (continued) $\endgroup$ Jul 14, 2020 at 13:06
-
$\begingroup$ (continuation) ... replacing one or more constraints with convex constraints which expand the feasible region., and whose solution would therefore provide a lower bound if minimizing (upper bound if maximizing) to the original problem. $\endgroup$ Jul 14, 2020 at 13:07
$\begingroup$
$\endgroup$
Technically, your statement is correct, but nowadays it depends on who you're talking to.
Historically, to $\min f(x) s.t. ...$ means exactly what we see: to find the minimal value. Not some value that's smaller in some arbitrary neighborhood, the minimal value.
Ergo, the semantically correct way is to use "solution" for all global solutions, and "local solution" for, well, all other solutions.
However, because of people's inability to find global solutions for decades, abuse of terminology came along, and people started referring to "solution" as any solution, which is technically incorrect.
Nowadays, unless you're talking to a global optimisation person, this is the terminology people will understand.
If you are talking to a global optimisation person they will still understand what you mean, politely nod, and silently condemn you for all time.
