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

Проблемой минимизировать является квадратичная функция шести переменных, удовлетворяющих линейному равенству и ограничениям неравенства. Целевая функция, 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-2017 The MathWorks, Inc.
x = x';

%Define a quadratic problem in terms of H and f 
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;

Создайте переменную x оптимизации с шестью элементами как вектор-строка.

x = optimvar("x",1,6);

Создайте задачу оптимизации с целевой функцией lincontest7(x).

prob = optimproblem("Objective",lincontest7(x));

Задайте начальную точку для оптимизации.

x0.x = [2 1 0 9 1 0];

Создайте линейные ограничительные матрицы для ограничений Aineq*x' <= Bineq и Aeq*x' = Beq. Необходимо использовать x' в этих ограничениях, потому что x вектор-строка.

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]';
prob.Constraints.Aineq = Aineq*x' <= Bineq;
prob.Constraints.Aeq = Aeq*x' == Beq;

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

[sol,Fval,eflag,output] = solve(prob,x0,"Solver","patternsearch");

Solving problem using patternsearch.
Optimization terminated: mesh size less than options.MeshTolerance.

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

The number of iterations is: 242

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

The number of function evaluations is: 1927

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 аргумент.

[sol2,Fval2,eflag2,output2] = solve(prob,x0,"Solver","patternsearch",...
    "Options",opts);

Solving problem using patternsearch.
Optimization terminated: mesh size less than options.MeshTolerance.

Настройки сетки

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

Начальный размер Mesh

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

opts = optimoptions(opts,'InitialMeshSize',1/2);

Поймайте в сети масштабирование

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

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

Поймайте в сети акселератор

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

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

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

[sol3,Fval3,eflag3,output3] = solve(prob,x0,"Solver","patternsearch",...
    "Options",opts);

Solving problem using patternsearch.
Optimization terminated: mesh size less than options.MeshTolerance.

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

The number of iterations is: 197

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

The number of function evaluations is: 1302

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

The best function value found is: 2189.03

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

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

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

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

opts.MeshTolerance = 1e-7;

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

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

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

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

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

opts.SearchFcn = @positivebasisnp1;

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

[sol4,Fval4,eflag4,output4] = solve(prob,x0,"Solver","patternsearch",...
    "Options",opts);

Solving problem using patternsearch.
Optimization terminated: mesh size less than options.MeshTolerance.

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

The number of iterations is: 67

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

The number of function evaluations is: 838

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

The best function value found is: 2189.03

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