Настройте задачу для поиска по шаблону

Задача минимизации является квадратичной функцией из шести переменных, удовлетворяющих линейным ограничениям равенствам и неравенствам. Целевая функция, lincontest7, входит в комплект поставки Global Optimization Toolbox.

type lincontest7

function y = lincontest7(x);
%LINCONTEST7 objective function.
%   y = LINCONTEST7(X) evaluates y for the input X. Make sure that x is a column 
%   vector, whereas objective function gets a row vector.


%   Copyright 2003-2004 The MathWorks, Inc.

x = x';
%Define a quadratic problem in terms of H and f (From web unknown source)
H = [36 17 19 12 8 15; 17 33 18 11 7 14; 19 18 43 13 8 16;
12 11 13 18 6 11; 8 7 8 6 9 8; 15 14 16 11 8 29];
 f = [ 20 15 21 18 29 24 ]';
 
 y = 0.5*x'*H*x + f'*x;

Задайте указатель на функцию @lincontest7 как целевая функция.

objectiveFcn = @lincontest7;

Целевая функция принимает вектор-строку длины шесть. Задайте начальную точку для оптимизации.

x0 = [2 1 0 9 1 0];

Создайте линейные матрицы ограничений, представляющие ограничения Aineq*x <= Bineq и Aeq*x = Beq. Для получения дополнительной информации см. раздел «Линейные ограничения».

Aineq = [-8 7 3 -4 9 0 ];
Bineq = [7];
Aeq = [7 1 8 3 3 3; 5 0 5 1 5 8; 2 6 7 1 1 8; 1 0 0 0 0 0];
Beq = [84 62 65 1];

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

[X1,Fval,Exitflag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq,Aeq,Beq);

Optimization terminated: mesh size less than options.MeshTolerance.

fprintf('The number of iterations is: %d\n', Output.iterations);

The number of iterations is: 132

fprintf('The number of function evaluations is: %d\n', Output.funccount);

The number of function evaluations is: 1531

fprintf('The best function value found is: %g\n', Fval);

The best function value found is: 2189.03

Добавьте визуализацию

Отслеживайте процесс оптимизации, задавая опции, которые выбирают две функции построения графика. Область функции построения графика psplotbestf строит графики наилучшего значения целевой функции на каждой итерации и функции построения графика psplotfuncount строит графики, количество раз, когда целевая функция оценивается при каждой итерации. Установите эти две функции построения графика в массив ячеек.

opts = optimoptions(@patternsearch,'PlotFcn',{@psplotbestf,@psplotfuncount});

Запуск patternsearch решатель, включая opts аргумент. Поскольку задача не имеет верхних или нижних границ ограничений и нелинейных ограничений, передайте пустые массивы ([]) для седьмого, восьмого и девятого аргументов.

[X1,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq, ...
    Aeq,Beq,[],[],[],opts);

Optimization terminated: mesh size less than options.MeshTolerance.

Опции сетки

Поиск шаблона включает в себя оценку целевой функции в точках в mesh. Размер mesh может повлиять на скорость решения. Управлять размером сетки можно с помощью опций.

Начальный размер сетки

Mesh в каждой итерации является диапазоном набора направлений поиска, которые добавляются к текущей точке, масштабируемой текущим размером сетки. Решатель начинает с начального размера сетки 1 по умолчанию. Чтобы начать начальный размер сетки с 10, установите InitialMeshSize опция.

options = optimoptions(opts,'InitialMeshSize',10);

Масштабирование сетки

Можно масштабировать mesh, чтобы улучшить минимизацию плохо масштабируемой задачи оптимизации. Масштабирование поворачивает шаблон на некоторую степень и масштабируется по направлениям поиска. The ScaleMesh опция включена (true) по умолчанию, но можно выключить, если задача хорошо масштабирована. В целом, если задача плохо масштабирована, установка этой опции равной true может уменьшить количество вычислений функции. Для этой задачи установите ScaleMesh на false, потому что lincontest7 является хорошо масштабированной целевой функцией.

opts = optimoptions(opts,'ScaleMesh',false);

Сетчатый ускоритель

Методы прямого поиска требуют многих вычислений функции по сравнению с производными методами оптимизации. Алгоритм поиска шаблона может быстро найти окрестность оптимальной точки, но может быть медленным в обнаружении самого минимума. The patternsearch решатель может уменьшить количество вычислений функции при помощи Accelerator. Когда ускоритель включен (opts.AccelerateMesh = true), решатель быстро сжимает размер сетки после достижения минимального размера сетки. Эта опция рекомендуется только для плавных задач; в других типах задач можно потерять некоторую точность. The AccelerateMesh опция отключена (false) по умолчанию. Для этой задачи установите AccelerateMesh на true потому что целевая функция плавна.

opts = optimoptions(opts,'AccelerateMesh',true);

Запуск patternsearch решатель.

[X2,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq, ...
    Aeq,Beq,[],[],[],opts);

Optimization terminated: mesh size less than options.MeshTolerance.

fprintf('The number of iterations is: %d\n', Output.iterations);

The number of iterations is: 86

fprintf('The number of function evaluations is: %d\n', Output.funccount);

The number of function evaluations is: 893

fprintf('The best function value found is: %g\n', Fval);

The best function value found is: 2189.03

Настройки опции mesh уменьшают количество итераций и количество вычислений функции и без видимой потери точности.

Критерий остановки и допуски

MeshTolerance - допуск размера сетки. Если размер сетки меньше MeshToleranceрешатель останавливается. StepTolerance - минимальный допуск изменения текущей точки до следующей точки. FunctionTolerance - минимальный допуск на изменение значения функции от текущей точки до следующей точки.

Установите MeshTolerance 1e-7, что в десять раз меньше значения по умолчанию. Эта настройка может увеличить количество вычислений функции и итераций, и может привести к более точному решению.

opts.MeshTolerance = 1e-7;

Методы поиска в поиске по шаблону

Алгоритм поиска шаблона может использовать дополнительный метод поиска при каждой итерации, основанный на значении SearchFcn опция. Когда вы задаете метод поиска используя SearchFcn, patternsearch выполняет указанный поиск сначала, перед поиском сетки. Если метод поиска успешен, patternsearch пропускает поиск сетки, обычно называемый функцией опроса, для этой итерации. Если метод поиска неудачен в улучшении текущей точки, patternsearch выполняет поиск сетки.

Можно задать различные методы поиска для SearchFcn, включая searchga и searchneldermead, которые являются алгоритмами оптимизации. Используйте эти два метода поиска только для первой итерации, которая является настройкой по умолчанию. Использование любого из этих методов при каждой итерации может не улучшить результаты и может быть вычислительно дорогим. Однако можно использовать searchlhs метод, который генерирует латинские точки гиперкуба, в каждой итерации или, возможно, каждые 10 итераций.

Другие варианты поиска включают методы опроса, такие как положительный базис N + 1 или положительный базис 2N. Рекомендуемая стратегия состоит в том, чтобы использовать положительный базис N + 1 (который требует не более N + 1 точек для создания шаблона) в качестве метода поиска и положительный базис 2N (который требует 2N точек для создания шаблона) в качестве метода опроса.

Обновите структуру опций, чтобы использовать positivebasisnp1 как метод поиска. Потому что положительный базис 2N является значением по умолчанию для PollFcn опция, не устанавливать эту опцию.

opts.SearchFcn = @positivebasisnp1;

Запуск patternsearch решатель.

[X5,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq,Aeq,Beq, ...
    [],[],[],opts);

Optimization terminated: mesh size less than options.MeshTolerance.

fprintf('The number of iterations is: %d\n', Output.iterations);

The number of iterations is: 66

fprintf('The number of function evaluations is: %d\n', Output.funccount);

The number of function evaluations is: 838

fprintf('The best function value found is: %g\n', Fval);

The best function value found is: 2189.03

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