Is paretosearch from the Global Optimization Toolbox deterministic?

Dear MATLAB Community,

I wonder if the paretosearch solver provided by the Global Optimization Toolbox is stochastic or deterministic. In simple words, can the results found with this method differ between different executions?

As far as I know, I would say that the method is deterministic, i.e., the same problem and method configuration return the same result every execution. I think that paretosearch relies on pattern search, which I belieive that is deterministic (please, correct me if I am wrong). Hence, I would say that it is. However, the first example in https://www.mathworks.com/help/gads/paretosearch.html#d126e62423 sets RNG (and says 'for reproducibility').

I have done the following test based on the first example in the referred link:

fun = @(x)[norm(x-[1,2])^2;norm(x+[2,1])^2];
rng default % For reproducibility
x1 = paretosearch(fun,2);

Pareto set found that satisfies the constraints. 

Optimization completed because the relative change in the volume of the Pareto set 
is less than 'options.ParetoSetChangeTolerance' and constraints are satisfied to within 
'options.ConstraintTolerance'.

rng(1234);
x2 = paretosearch(fun,2);

Pareto set found that satisfies the constraints. 

Optimization completed because the relative change in the volume of the Pareto set 
is less than 'options.ParetoSetChangeTolerance' and constraints are satisfied to within 
'options.ConstraintTolerance'.

rng(5678);
x3 = paretosearch(fun,2);

Pareto set found that satisfies the constraints. 

Optimization completed because the relative change in the volume of the Pareto set 
is less than 'options.ParetoSetChangeTolerance' and constraints are satisfied to within 
'options.ConstraintTolerance'.

isequal(x1, x2)

ans = logical
   1

isequal(x1, x3)

ans = logical
   1

isequal(x2, x3)

ans = logical
   1

So, it seems deterministc. Nonetheless, I could have been extremely lucky (or the problem might be too easy for the solver and it is converging perfectly). This is the reason I would like to know if paretosearch is formally deterministic or not.

Thank you very much in advance for your time!

Answer 1

[Avadhoot]

Hi Nicolas,

I understand that you are confused regarding the nature of the Pareto search algorithm. As you have correctly stated, the algorithm is derived from the pattern search method, which is a deterministic search method. While the pareto search method itself is deterministic, there are a lot of external factors which can influence the results. These factors include the following:

1. Problem formulation: The search is heavily influenced by how the search problem is formulated.
2. Objective function: If there are stochastic elements involved in the objective function then the results vary accordingly.
3. Polling method: The polling method chosen for Pareto search also introduces randomness in the search as it is necessary to explore the search space.

When you include the “rng default” line in the code, it sets the random number generator seed to a predefined default value. This results in reproducible results as the algorithm will produce the same set of random numbers every time the code is executed.

In conclusion, the “paretosearch” function is deterministic but it still can be influenced by external factors.

For more information about the “paretosearch” function and the algorithm behind it, refer to the below documentation:

1. https://www.mathworks.com/help/gads/paretosearch.html
2. https://www.mathworks.com/help/gads/paretosearch-algorithm.html

To understand how to reproduce results using the output of the previous experiment refer the below link:

https://www.mathworks.com/help/gads/reproducing-your-results-1.html

I hope this helps.

[Nicolás C.C.]

Thank you very much! My main concern was to certify the deterministic nature of ParetoSearh itself for a fixed (and non-stochastic) problem (and compared to NSGA-II, for instance, which is stochastic by definition). I have already accepted your answer. Kind regards!