How does global search handle negative exitflags of the local solver?

Hi everybody,

I have a problem with the global search algorithm in combination with the local fmincon solver. As I use the output function of the local solver as stopping criteria, fmincon always delivers -1 as output flag. Although a negative exit flag means a "bad" result to MATLAB the result is correct for my prupose. Now I am not sure if my global search algorithm is working correctly, receiving negative exitflags of the local solver, as the current best point ist not updated during the process. At the moment I am using the output function of the global search function to write the local solutions to a backup variable, so that I can read and compare the results but I think the algorithm has some problems with the negative exitflags?!

Do you have any suggestions? Is it possible to manipulate the exitflag of the local solver?

Thanks in advance!

Alex

[Paul Kerr-Delworth]

Hi Alex,

GlobalSearch dynamically updates a solution that it will return if all calls to the local solver return with a negative exit flag. Specifically, it keeps the "best" solution amongst all the solutions with negative exit flag and discards the rest.

So, what do we mean by "best"? The solution returned in the case where all the local solver exit flags is either

If at least one call to the local solver stops at a feasible point:

• Return the solution with lowest function value among all feasible solutions

If no call to the local solver stops at a feasible point:

• Return the solution with lowest constraint violation

If you want to continue to use your output function, you can let the local solver decide when to stop. That is, don't set stop = true in your output function (as you're aware, this is what is causing the local solver to stop with a negative exitflag). GlobalSearch will then keep unique solutions that return with a postive exitflag from the local solver.

Hope this helps.

Best regards,

Paul

[Alex]

Hi Paul,

thanks for your fast reply.

If I understand you correctly, global search can deal with negative exit flag of the local solver, right?! So the global search algorithm is still searching in the right direction, updating the basins of attraction and so on?! My "controlling" of the local solver and also of the global search functions by using the output function works quite good, I was just worrying if the global search function works correctly while getting "bad" solutions all the time. So with your statement I would say it should work but I do not really understand your last paragraph. How is it possible to stop the local solver by the output function without using the stop flag?

Best regards, Alex

[Paul Kerr-Delworth]

Hi Alex,

Your understanding is correct, GlobalSearch can deal with a negative exit flag of the local solver. Now, the basins of attraction are defined around a local solution. That is, a basin of attraction is defined around a solution returned from the local solver with a positive exit flag. So, in your case, if you prematurely stop all calls to the local solver, GlobalSearch will think all solutions are "bad" and no basins of attraction will be found.

May I ask why you need to stop the calls to the local solver? Are these calls taking a long time? If so, you may need to tune the local solver. Perhaps increasing TolX or TolFun for the local solver may help here.

Regarding your last question, what I mean is that I think you shouldn't be stopping the calls to the local solver. For GlobalSearch to work correctly, it is strongly advised to let the calls to the local solver terminate by themselves and not force them to stop by using an output function.

Best regards,

Paul

[Alex]

Hi Paul,

thank you very much for this answer. That helped me a lot. I am using the output function to stop the local solver because it is more suitable to the stopping criteria I need. My problem was that my function value was still changing even when other criteria were fulfilled and thus the iteration stopped. That is why I wrote an output function to check the convergence behaviour of the function value. Now as I now that my Global Search will not work correctly, I will try to play around a bit with the other tolerances and stopping criteria to achieve satisfying results. I now that I could use the criteria First order optimality which refers to the behaviour of the function value but I do not find a suitable value for this tolerance, may be because I am dealing with a lot of constraints.

Thanks again!

Best regards, Alex

[Sean de Wolski]

@Alex, you could have your output function trigger the objective function to throw out a larger value than the previous iteration to trick the solver into thinking it found a local minimum.

This could be done using nested functions or object oriented programming.

[Alex]

Hi,

thanks for your reply.

Your approach is very close to what I meant with manipulating the exitflag in my first question but how can I extract values from the output function as the only output parameter is the stop flag. Sure I can add another output parameter to the function but how should I name it to communicate with the global search function? If I am right I can only read out values from optimValues and cannot change them actively, can I?

Best regards, Alex

Answer 1

[Sean de Wolski]

In reply to comments:

Yes, but GlobalSearch is evaluating your objective function on each iteration. All you can do is read these values out as you said in the plot function. But, from within the plot function you can change a flag, that when checked by the objective function, will cause your objective function to return a larger value than the previous iteration rather than doing the calculation.

If we had a small example, it would be easier to show how to do this. I think using a nested function as the plot function would likely be easiest. The nested function shares the workspace with the objective function so they can see and modify each other's variables. I thought there was an example on how to do this, but I can't find it now. Maybe Alan will chime in.

If you can provide a minimal working example, it would help.

Answer 2

[Alex]

Hi,

meanwhile I adapted my stopping criteria in an acceptable way so that I receive positive exit flags from the local solver (not a flag=1 but flag=2 which should be OK). At the moment I am trying to adjust the other parameters of the global search function to ensure that the global minimum is found. If this will work out the next days, I would be fine and the problem is solved. Otherwise I would like to come back to your idea with more details about my code.

Nevertheless, thanks for your help!

Best regards, Alex