This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Can You Certify 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.

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 (Optimization Toolbox) 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 =

exitflag =

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 =


exitflagp =


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


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.

Updating Unconstrained Problem from GlobalSearch

If you use GlobalSearch on an unconstrained problem, change your problem structure before using MultiStart. You have two choices in updating a problem structure for an unconstrained problem using MultiStart:

  • Change the solver field to 'fminunc':

    problem.solver = 'fminunc';

    To avoid a warning if your objective function does not compute a gradient, change the local options to have Algorithm set to 'quasi-newton':

    problem.options.Algorithm = 'quasi-newton';
  • Add an artificial constraint, retaining fmincon as the local solver: = -Inf(size(x0));

To search a larger region than the default, see Refine Start Points.

Related Topics

Was this topic helpful?