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

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

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

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

Функция –sech (x) является почти 0 для всего |x | > 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 искать неограниченную область, чтобы найти глобальный минимум. Снова, вам нужны много стартовых точек, чтобы иметь хороший шанс нахождения глобального минимума.

Первые пять строк кода генерируют 10 000 широко рассеянных случайных стартовых точек с помощью метода, описанного в Широко Рассеянных Точках для Неограниченных Компонентов. 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 с обычной сеткой и многообещающими стартовыми точками

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

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

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 существует только две стартовых точки, один из которых является глобальным минимумом.