Функция с одной нескончаемой точкой

Функция $$f(x)=||x|{|}^{1/2}$$ nonsmooth в точке 0, которая является точкой минимизации. Вот 2-D график с использованием матричной нормы для точки 4-D $\left[\begin{array}{cc}x(1)& x(2)\\ 0& 0\end{array}\right]$ .

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}')

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

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

patternsearch - это рекомендуемый первый решатель, чтобы попытаться решить нескромные задачи. Смотрите таблицу для выбора решателя. Начните patternsearch из ненулевой матрицы 2 на 6 x0, и попытаться найти минимум $$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 = 429

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

Использование fmincon из Optimization Toolbox

fmincon Иногда можно минимизировать функции nonsmooth. Посмотрите, как это работает на этом.

[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.1407    0.8738    0.9526    0.5668    0.8921    0.6830
    0.4008   -0.1290    0.0410   -0.6440    0.0190   -0.2374

fvalfmc = 1.3212e-05

eflagfmc = 2

ans = 863

fmincon с опциями по умолчанию создает точное решение после менее чем 1000 вычислений функции. Выходной флаг 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       429 
    {'fmincon'      }       {'Good'}        1.3212e-05       863 

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

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