Поведение решателя с несглаженной проблемой

Этот пример показывает важность выбора соответствующего решателя для задач оптимизации. Это также показывает, что одна точка негладкости может вызвать проблемы для решателей Optimization Toolbox™.

В общем случае таблицы решений решателя дают представление, на котором решатель, вероятно, будет работать лучше всего на вашу проблему. Для сглаженных проблем см. Таблицу решений Оптимизации. Для несглаженных проблем см. Таблицу для Выбора Solver сначала, и для получения дополнительной информации консультируйтесь с Характеристиками Решателя Global Optimization Toolbox.

Функция с одной несглаженной точкой

Функция f(x)=||x||1/2 несглаженно в точке 0, которая является точкой минимизации. Вот 2D график с помощью матричной нормы для точки 4-D [x(1)x(2)00] .

figure
x = linspace(-5,5,51);
[xx,yy] = meshgrid(x);
zz = zeros(size(xx));
for ii = 1:length(x)
    for jj = 1:length(x)
        zz(ii,jj) = sqrt(norm([xx(ii,jj),yy(ii,jj);0,0]));
    end
end

surf(xx,yy,zz)
xlabel('x(1)')
ylabel('x(2)')
title('Norm([x(1),x(2);0,0])^{1/2}')

Этот пример использует матричную норму для матричного x 2 на 6. Матричная норма относится к сингулярному разложению, которое как не является гладким как Евклидова норма. Смотрите 2-норму Матрицы.

Минимизируйте Используя patternsearch

patternsearch рекомендуемый первый решатель должен попробовать за несглаженные проблемы. См. Таблицу для Выбора Решателя. Запустите patternsearch от ненулевого матричного x0 2 на 6, и попытайтесь определить местоположение минимума f. Для этой попытки и всех других, используют опции решателя по умолчанию.

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

fun = @(x)norm([x(1:6);x(7:12)])^(1/2);
x0 = [1:6;7:12];
rng default
x0 = x0 + rand(size(x0))
x0 = 2×6

    1.8147    2.1270    3.6324    4.2785    5.9575    6.1576
    7.9058    8.9134    9.0975   10.5469   11.9649   12.9706

[xps,fvalps,eflagps,outputps] = patternsearch(fun,x0);
Optimization terminated: mesh size less than options.MeshTolerance.
xps,fvalps,eflagps,outputps.funccount
xps = 2×6
10-4 ×

    0.1116   -0.1209    0.3503   -0.0520   -0.1270    0.2031
   -0.3082   -0.1526    0.0623    0.0652    0.4479    0.1173

fvalps = 0.0073
eflagps = 1
ans = 10780

patternsearch достигает хорошего решения, как проявлено выходным флагом 1. Однако это принимает 10 000 вычислений функции, чтобы сходиться.

Минимизируйте Используя fminsearch

Документация утверждает тот fminsearch иногда может обрабатывать разрывы, таким образом, это - разумная опция.

[xfms,fvalfms,eflagfms,outputfms] = fminsearch(fun,x0);
 
Exiting: Maximum number of function evaluations has been exceeded
         - increase MaxFunEvals option.
         Current function value: 3.197063 
xfms,fvalfms,eflagfms,outputfms.funcCount
xfms = 2×6

    2.2640    1.1747    9.0693    8.1652    1.7367   -1.2958
    3.7456    1.2694    0.2714   -3.7942    3.8714    1.9290

fvalfms = 3.1971
eflagfms = 0
ans = 2401

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

Используйте particleswarm

particleswarm рекомендуется как следующий решатель попробовать. Смотрите Выбор Между Решателями для Несглаженных проблем.

[xpsw,fvalpsw,eflagpsw,outputpsw] = particleswarm(fun,12);
Optimization ended: relative change in the objective value 
over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.
xpsw,fvalpsw,eflagpsw,outputpsw.funccount
xpsw = 1×12
10-12 ×

   -0.0386   -0.1282   -0.0560    0.0904    0.0771   -0.0541   -0.1189    0.1290   -0.0032    0.0165    0.0728   -0.0026

fvalpsw = 4.5222e-07
eflagpsw = 1
ans = 37200

particleswarm находит еще более точное решение, чем patternsearch, но принимает 35 000 вычислений функции. Выйдите флаг 1 указывает, что решение хорошо.

Используйте ga

ga популярный решатель, но не рекомендуется как первый решатель попробовать. Смотрите, как хорошо это работает над этой проблемой.

[xga,fvalga,eflagga,outputga] = ga(fun,12);
Optimization terminated: average change in the fitness value less than options.FunctionTolerance.
xga,fvalga,eflagga,outputga.funccount
xga = 1×12

   -0.0061   -0.0904    0.0816   -0.0484    0.0799   -0.1925    0.0048    0.3581    0.0848    0.0232    0.0237   -0.1294

fvalga = 0.6257
eflagga = 1
ans = 65190

ga не находит столь же хорошее решение как patternsearch или particleswarm, и берет о вдвое большем количестве вычислений функции в качестве particleswarm. Выйдите флаг 1 вводит в заблуждение в этом случае.

Используйте fminunc от Optimization Toolbox

fminunc не рекомендуется для несглаженных функций. Смотрите, как это выполняет на этом.

[xfmu,fvalfmu,eflagfmu,outputfmu] = fminunc(fun,x0);
Local minimum possible.

fminunc stopped because the size of the current step is less than
the value of the step size tolerance.
xfmu,fvalfmu,eflagfmu,outputfmu.funcCount
xfmu = 2×6

   -0.5844   -0.9726   -0.4356    0.1467    0.3263   -0.1002
   -0.0769   -0.1092   -0.3429   -0.6856   -0.7609   -0.6524

fvalfmu = 1.1269
eflagfmu = 2
ans = 442

fminunc решение не так хорошо как ga решение. Однако fminunc достигает довольно плохого решения в относительно немногих вычислениях функции. Выйдите из флага 2 средних значения, необходимо заботиться, условия оптимальности первого порядка не соблюдают в решении, о котором сообщают.

Используйте fmincon от Optimization Toolbox

fmincon может иногда минимизировать несглаженные функции. Смотрите, как это выполняет на этом.

[xfmc,fvalfmc,eflagfmc,outputfmc] = fmincon(fun,x0);
Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.
xfmc,fvalfmc,eflagfmc,outputfmc.funcCount
xfmc = 2×6
10-10 ×

    0.1530    0.0951   -0.2098    0.1464   -0.2330    0.1503
    0.3891   -0.2477   -0.2373   -0.0222    0.4761   -0.2413

fvalfmc = 8.2669e-06
eflagfmc = 2
ans = 1052

fmincon с опциями по умолчанию производит точное решение меньше чем после 1 000 вычислений функции. Выйдите флаг 2 не означает, что решение неточно, но что условия оптимальности первого порядка не соблюдают. Это вызвано тем, что градиент целевой функции не является нулем в решении.

Сводные данные результатов

Выбор соответствующего решателя приводит к лучше, более быстрые результаты. Эти сводные данные показывают, насколько разрозненный результаты могут быть. Качеством решения является 'Poor' если значение целевой функции больше 0.1, 'Good' если значение меньше, чем 0,01, и 'Mediocre' в противном случае.

Solver = {'patternsearch';'fminsearch';'particleswarm';'ga';'fminunc';'fmincon'};
SolutionQuality = {'Good';'Poor';'Good';'Poor';'Poor';'Good'};
FVal = [fvalps,fvalfms,fvalpsw,fvalga,fvalfmu,fvalfmc]';
NumEval = [outputps.funccount,outputfms.funcCount,outputpsw.funccount,...
    outputga.funccount,outputfmu.funcCount,outputfmc.funcCount]';
results = table(Solver,SolutionQuality,FVal,NumEval)
results=6×4 table
         Solver          SolutionQuality       FVal       NumEval
    _________________    _______________    __________    _______

    {'patternsearch'}       {'Good'}         0.0072656     10780 
    {'fminsearch'   }       {'Poor'}            3.1971      2401 
    {'particleswarm'}       {'Good'}        4.5222e-07     37200 
    {'ga'           }       {'Poor'}           0.62572     65190 
    {'fminunc'      }       {'Poor'}            1.1269       442 
    {'fmincon'      }       {'Good'}        8.2669e-06      1052 

Другое представление результатов.

figure
hold on
for ii = 1:length(FVal)
    clr = rand(1,3);
    plot(NumEval(ii),FVal(ii),'o','MarkerSize',10,'MarkerEdgeColor',clr,'MarkerFaceColor',clr)
    text(NumEval(ii),FVal(ii)+0.2,Solver{ii},'Color',clr);
end
ylabel('FVal')
xlabel('NumEval')
title('Reported Minimum and Evaluations By Solver')
hold off

В то время как particleswarm достигает самого низкого значения целевой функции, оно делает так путем принятия в три раза больше вычислений функции, чем patternsearch, и более чем в 30 раз больше, чем fmincon.

fmincon обычно не рекомендуется для несглаженных проблем. Это эффективно в этом случае, но этот случай имеет всего одну несглаженную точку.

Похожие темы

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