TransWikia.com

MINLP Solution same as Global Optimum?

Operations Research Asked by Clement on August 19, 2021

Is the solution to an MINLP problem the global optimum to this problem?

2 Answers

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.

Answered by Nikos Kazazakis on August 19, 2021

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 by Mark L. Stone on August 19, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP