Настройки по умолчанию не могут найти глобальный минимум - добавить границы
MultiStart без границ, широко рассредоточенные стартовые точки
MultiStart с регулярной сеткой и перспективными стартовыми точками
Нахождение начальной точки в области притяжения глобального минимума может оказаться трудным, когда умывальная раковина мала или когда вы не уверены в местоположении минимума. Чтобы решить этот тип задачи, вы можете:
Добавьте разумные границы
Возьмите огромное количество случайных стартовых точек
Составьте методическую сетку начальных точек
Для задачи без ограничений примите широко рассредоточенные случайные стартовые точки
Этот пример показывает эти методы и некоторые варианты.
Функция -sech (x) - почти 0 для всех |<reservedrangesplaceholder1>| > 5, и -sech (0) = -1. Пример является двумерной версией функции sech с одним минимумом в [1,1], другой в [1e5,-1e5]:
f (x, y) = -10sech (|<reservedrangesplaceholder0> - (1,1) |) - 20sech (.0003 (|x - (1e5, -1e5) |) - 1.
f имеет глобальный минимум -21 при (1e5, -1e5) и локальный минимум -11 при (1,1).
Минимум в (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Чтобы найти глобальный минимум, можно искать больше точек. Этот пример использует 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 со многими стартовыми точками. Этот пример использует 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 поиск неограниченной области для нахождения глобального минимума. Снова, вам нужно много стартовых точек, чтобы иметь хорошие шансы найти глобальный минимум.
Первые пять строк кода генерируют 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 нашел глобальный минимум.
Можно также использовать сетку начальных точек вместо случайных начальных точек. Чтобы узнать, как создать регулярную сетку для больших размерностей или такую, которая имеет небольшие возмущения, смотрите Единообразную сетку или Возмущенную сетку.
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 нашел глобальный минимум.
Составление регулярной сетки начальных точек, особенно в высоких размерностях, может использовать неподходящее количество памяти или времени. Можно фильтровать начальные точки, чтобы запустить только те, которые имеют маленькое значение целевой функции.
Чтобы выполнить эту фильтрацию наиболее эффективно, напишите свою целевую функцию векторизованным образом. Для получения дополнительной информации смотрите Запись векторизованной функции или Векторизация функций 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, одним из которых является глобальный минимум.