Документация

Трудный для нахождения глобальный минимум

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

Этот пример показывает эти методы и некоторые варианты.

Функция -sech (x) - почти 0 для всех |<reservedrangesplaceholder1>|    > 5, и -sech (0) = -1. Пример является двумерной версией функции sech с одним минимумом в [1,1], другой в [1e5,-1e5]:

f имеет глобальный минимум -21 при (1e5, -1e5) и локальный минимум -11 при (1,1).

 Код для генерации фигуры

x1 = [1,1]; x2 = [1e5,-1e5];
% f is a vectorized version of the objective function
% Each row of an input matrix x is one point to evaluate
f = @(x)-10*sech(sqrt((x(:,1)-x1(1)).^2+(x(:,2)-x1(2)).^2)) ...
    -20*sech(3e-4*sqrt((x(:,1)-x2(1)).^2+(x(:,2)-x2(2)).^2))-1;
hndl = ezsurf(@(x,y)f([x,y]),[-1e6 1e6],1000);
set(hndl,'LineStyle','none')
view(-45,10)
hold on
annotation('textarrow',...
    [0.71 0.56],[0.48 0.21],'TextEdgeColor','none',...
    'String',{'Global Minimum'});
hold off

Минимум в (1e5, -1e5) показывает как узкий всплеск. Минимум в (1,1) не отображается, так как он слишком узок.

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

Настройки по умолчанию не могут найти глобальный минимум - добавить границы

GlobalSearch и MultiStart не может найти глобальный минимальный дефолт использования глобальными опциями, так как компоненты стартовой точки по умолчанию находятся в области значений (-9999,10001) для GlobalSearch и (-1000,1000) для MultiStart.

С дополнительными границами -1e6 и 1e6 в problem, GlobalSearch обычно не находит глобальный минимум:

x1 = [1;1];x2 = [1e5;-1e5];
f = @(x)-10*sech(norm(x(:)-x1)) -20*sech((norm(x(:)-x2))*3e-4) -1;
opts = optimoptions(@fmincon,'Algorithm','active-set');
problem = createOptimProblem('fmincon','x0',[0,0],'objective',f,...
    'lb',[-1e6;-1e6],'ub',[1e6;1e6],'options',opts);
gs = GlobalSearch;
rng(14,'twister') % for reproducibility
[xfinal,fval] = run(gs,problem)

GlobalSearch stopped because it analyzed all the trial points.

All 32 local solver runs converged with a positive 
local solver exit flag.

xfinal =
    1.0000    1.0000

fval =
  -11.0000

GlobalSearch с границами и другими стартовыми точками

Чтобы найти глобальный минимум, можно искать больше точек. Этот пример использует 1e5 стартовых точек и MaxTime 300 с:

gs.NumTrialPoints = 1e5;
gs.MaxTime = 300;
[xg,fvalg] = run(gs,problem)

GlobalSearch stopped because maximum time is exceeded.

GlobalSearch called the local solver 2186 times before exceeding 
the clock time limit (MaxTime = 300 seconds).
1943 local solver runs converged with a positive 
local solver exit flag.

xg =
   1.0e+04 *
   10.0000  -10.0000

fvalg =
  -21.0000

В этом случае GlobalSearch нашел глобальный минимум.

MultiStart с границами и многими стартовыми точками

Также можно искать, используя MultiStart со многими стартовыми точками. Этот пример использует 1e5 стартовых точек и MaxTime 300 с:

ms = MultiStart(gs);
[xm,fvalm] = run(ms,problem,1e5)

MultiStart stopped because maximum time was exceeded.

MultiStart called the local solver 17266 times before exceeding
the clock time limit (MaxTime = 300 seconds).
17266 local solver runs converged with a positive 
local solver exit flag.

xm =
    1.0000    1.0000

fvalm =
  -11.0000

В этом случае MultiStart не удалось найти глобальный минимум.

MultiStart без границ, широко рассредоточенные стартовые точки

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

Первые пять строк кода генерируют 10000 широко рассредоточенных случайных начальных точек, используя метод, описанный в Широко рассеянных точках для незакрепленных компонентов. newprob - структура задачи, использующая fminunc локальный решатель и без границ:

rng(0,'twister') % for reproducibility
u = rand(1e4,1);
u = 1./u;
u = exp(u) - exp(1);
s = rand(1e4,1)*2*pi;
stpts = [u.*cos(s),u.*sin(s)];
startpts = CustomStartPointSet(stpts);

opts = optimoptions(@fminunc,'Algorithm','quasi-newton');
newprob = createOptimProblem('fminunc','x0',[0;0],'objective',f,...
    'options',opts);
[xcust,fcust] = run(ms,newprob,startpts)

MultiStart completed the runs from all start points.

All 10000 local solver runs converged with a positive
local solver exit flag.

xcust =
   1.0e+05 *

    1.0000
   -1.0000

fcust =
  -21.0000

В этом случае MultiStart нашел глобальный минимум.

MultiStart с регулярной сеткой начальных точек

Можно также использовать сетку начальных точек вместо случайных начальных точек. Чтобы узнать, как создать регулярную сетку для больших размерностей или такую, которая имеет небольшие возмущения, смотрите Единообразную сетку или Возмущенную сетку.

xx = -1e6:1e4:1e6;
[xxx,yyy] = meshgrid(xx,xx);
z = [xxx(:),yyy(:)];
bigstart = CustomStartPointSet(z);
[xgrid,fgrid] = run(ms,newprob,bigstart)

MultiStart completed the runs from all start points.

All 10000 local solver runs converged with a positive 
local solver exit flag.

xgrid =
  1.0e+004 *

   10.0000
  -10.0000

fgrid =
  -21.0000

В этом случае MultiStart нашел глобальный минимум.

MultiStart с регулярной сеткой и перспективными стартовыми точками

Составление регулярной сетки начальных точек, особенно в высоких размерностях, может использовать неподходящее количество памяти или времени. Можно фильтровать начальные точки, чтобы запустить только те, которые имеют маленькое значение целевой функции.

Чтобы выполнить эту фильтрацию наиболее эффективно, напишите свою целевую функцию векторизованным образом. Для получения дополнительной информации смотрите Запись векторизованной функции или Векторизация функций Objective и Constraint. Следующий указатель на функцию вычисляет вектор целей на основе матрицы входа, строки которой представляют начальные точки:

x1 = [1;1];x2 = [1e5;-1e5];
g = @(x) -10*sech(sqrt((x(:,1)-x1(1)).^2 + (x(:,2)-x1(2)).^2)) ...
     -20*sech(sqrt((x(:,1)-x2(1)).^2 + (x(:,2)-x2(2)).^2))-1;

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

xx = -1e6:1e3:1e6;
[xxx,yyy] = meshgrid(xx,xx);
z = [xxx(:),yyy(:)];
idx = g(z) < -2; % index of promising start points
zz = z(idx,:);
smallstartset = CustomStartPointSet(zz);
opts = optimoptions(@fminunc,'Algorithm','quasi-newton','Display','off');
newprobg = createOptimProblem('fminunc','x0',[0,0],...
    'objective',g,'options',opts); 
    % row vector x0 since g expects rows
[xfew,ffew] = run(ms,newprobg,smallstartset)

MultiStart completed the runs from all start points.

All 2 local solver runs converged with a positive 
local solver exit flag.

xfew =
      100000     -100000

ffew =
   -21

В этом случае MultiStart нашел глобальный минимум. Начальных точек всего две smallstartset, одним из которых является глобальный минимум.