## Can You Certify That a Solution Is Global?

### No Guarantees

How can you tell if you have located the global minimum of your objective function? The short answer is that you cannot; you have no guarantee that the result of a Global Optimization Toolbox solver is a global optimum. While all Global Optimization Toolbox solvers repeatedly attempt to locate a global solution, no solver employs an algorithm that can certify a solution as global.

However, you can use the strategies in this section for investigating solutions.

### Check if a Solution Is a Local Solution with patternsearch

Before you can determine if a purported solution is a global minimum, first check that it is a local minimum. To do so, run patternsearch on the problem.

To convert the problem to use patternsearch instead of fmincon or fminunc, enter

problem.solver = 'patternsearch';

Also, change the start point to the solution you just found, and clear the options:

problem.x0 = x;
problem.options = [];

For example, Check Nearby Points shows the following:

options = optimoptions(@fmincon,'Algorithm','active-set');
ffun = @(x)(x(1)-(x(1)-x(2))^2);
problem = createOptimProblem('fmincon', ...
'objective',ffun,'x0',[1/2 1/3], ...
'lb',[0 -1],'ub',[1 1],'options',options);
[x,fval,exitflag] = fmincon(problem)
x =
1.0e-007 *
0    0.1614

fval =
-2.6059e-016

exitflag =
1

However, checking this purported solution with patternsearch shows that there is a better solution. Start patternsearch from the reported solution x:

% set the candidate solution x as the start point
problem.x0 = x;
problem.solver = 'patternsearch';
problem.options = [];
[xp,fvalp,exitflagp] = patternsearch(problem)
Optimization terminated: mesh size less than options.MeshTolerance.

xp =

1.0000   -1.0000

fvalp =

-3.0000

exitflagp =

1

### Identify a Bounded Region That Contains a Global Solution

Suppose you have a smooth objective function in a bounded region. Given enough time and start points, MultiStart eventually locates a global solution.

Therefore, if you can bound the region where a global solution can exist, you can obtain some degree of assurance that MultiStart locates the global solution.

For example, consider the function

$f={x}^{6}+{y}^{6}+\mathrm{sin}\left(x+y\right)\left({x}^{2}+{y}^{2}\right)-\mathrm{cos}\left(\frac{{x}^{2}}{1+{y}^{2}}\right)\left(2+{x}^{4}+{x}^{2}{y}^{2}+{y}^{4}\right).$

The initial summands x6 + y6 force the function to become large and positive for large values of |x| or |y|. The components of the global minimum of the function must be within the bounds

–10 ≤ x,y ≤ 10,

since 106 is much larger than all the multiples of 104 that occur in the other summands of the function.

You can identify smaller bounds for this problem; for example, the global minimum is between –2 and 2. It is more important to identify reasonable bounds than it is to identify the best bounds.