Find all non-global minima on a surface

[Nathanael Kazmierczak]

Hello all,

I have an optimization problem in which the response surface contains multiple minima; however, the "basin of convergence" of the global minimum is very large and dominates much of the surface. I want to find all of the local minima on the surface, which means avoiding getting sucked into the global minimum on every optimization run.

Conceptually, is there a way to accomplish this or a name by which this problem is known? Are there particular solvers in OPTI that might prove useful?

Best,

Nathanael Kazmierczak

[Jonathan Currie]

Hi Nathanael,

Other than brute force, for a general nonlinear problem I am not aware of a way to find all minima. However solvers such as BARON and SCIP do offer the ability to return multiple solutions, which may be of some assistance? I can't remember the exact options but have a look at their documentation and see if you can work it out. Otherwise write back and I can revisit it.

Jonathan

--
You received this message because you are subscribed to the Google Groups "OPTI Toolbox Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opti-toolbox-fo...@googlegroups.com.
To post to this group, send email to opti-tool...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Mark L. Stone]

This suggestion won;t guarantee you find all local minima, but may help find some of them.

If you have already found  the global minimum, solve additional problems in which you add a constraint on the objective function to be greater than a little greater (more than solver tolerance) than global minimum objective value. Of course, if the objective function is non-convex, then so will be the added constraint, so it might be tricky even finding a feasible solution.  If the new minimum is on this bound, then it may not be a true local minimum of the original problem.

Another thing you can do is place bounds excluding globally optimal or other locally optimal argmins, but that might require introducing binary variables to incorporate such non-convex constraints. 

[Nathanael Kazmierczak]

Thanks for the suggestions, all! That gives me a few helpful places to start looking.

Best,

Nathanael Kazmierczak

[Mark L. Stone]

Following up on Jonathan's suggestion: As far as I know ,BARON does not have the ability to find all local minima. However, as described in section 6,2 of the BARON manual https://minlp.com/downloads/docs/baron%20manual.pdf

the NumSol option can be used to

"find the best few, or even all feasible, solutions to a model. This facility is applicable to combinatorial as well as continuous problems."

"Once a model is solved by BARON with the NumSol option, the solutions found can be read from BARON results file."

"The BARON option isoltol (default value of 10−4) allows the user to specify the isolation tolerance used for discriminating among different solutions. In order for two feasible solution vectors to be considered different, at least one of their coordinates must differ by isoltol."

So I don't think that gets you all the local minima when applied to the original optimization problem. However, I suppose if first order KKT conditions are necessary for local minima for your problem, you could specify the first order KKT conditions to BARON as a feasibility problem, then use the NumSol and IsoTol options to find all sufficiently separated first order KKT solutions, then apply a second order test to choose the local minima from among those solutions.