Можете ли вы сертифицировать, что решение является глобальным?

Никаких гарантий

Как вы можете сказать, если вы нашли глобальный минимум вашей целевой функции? Короткий ответ, что вы не можете; у вас нет гарантии, что результат решателя Global Optimization Toolbox является глобальным оптимумом. В то время как все решатели Global Optimization Toolbox неоднократно пытаются найти глобальное решение, ни один решатель не использует алгоритм, который может сертифицировать решение как глобальное.

Однако можно использовать стратегии в этом разделе для исследования решений.

Проверьте, является ли решение локальным решением с patternsearch

Прежде чем вы сможете определить, является ли предполагаемое решение глобальным минимумом, сначала проверьте, что это локальный минимум. Для этого запустите patternsearch о задаче.

Для преобразования problem использовать patternsearch вместо fmincon или fminunc, введите

problem.solver = 'patternsearch';

Также смените стартовую точку на только что найденное решение, и очистите опции:

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

Для примера, Проверка ближайших точек показывает следующее:

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

Однако проверка этого предполагаемого решения с patternsearch показывает, что существует лучшее решение. Начать patternsearch из отчетного решения 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

Идентифицируйте ограниченную область, содержащую глобальное решение

Предположим, что у вас есть сглаженная целевая функция в ограниченной области. Учитывая достаточно времени и стартовых точек, MultiStart в конечном счете определяет местоположение глобального решения.

Поэтому, если можно связать область, в которой может существовать глобальное решение, можно получить некоторую степень уверенности в том, что MultiStart определяет местоположение глобального решения.

Для примера рассмотрим функцию

f=x6+y6+sin(x+y)(x2+y2)cos(x21+y2)(2+x4+x2y2+y4).

Начальные сводки x6 + y6 заставить функцию стать большой и положительной для больших значений |<reservedrangesplaceholder1>| или |<reservedrangesplaceholder0>|. Компоненты глобального минимума функции должны находиться в границах

– 10  ≤ <reservedrangesplaceholder1>  , <reservedrangesplaceholder0> ≤ 10,

начиная с 106 намного больше, чем все кратные 104 которые происходят в других сводках функции.

Можно идентифицировать меньшие границы для этой задачи; например, глобальный минимум находится в диапазоне от -2 до 2. Более важно определить разумные границы, чем определить наилучшие границы.

Используйте MultiStart с дополнительными начальными точками

Чтобы проверить, есть ли лучшее решение вашей задачи, запустите MultiStart с дополнительными стартовыми точками. Использование MultiStart вместо GlobalSearch для этой задачи, потому что GlobalSearch не запускает локальный решатель из всех начальных точек.

Например, см. Пример: Поиск лучшего решения.

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте