Main Content

## 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.

### Use MultiStart with More Start Points

To check whether there is a better solution to your problem, run `MultiStart` with additional start points. Use `MultiStart` instead of `GlobalSearch` for this task because `GlobalSearch` does not run the local solver from all start points.

For example, see Example: Searching for a Better Solution.

## Support Get trial now