Типичная проблема оптимизации

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

Примечание:

Если целевая функция или нелинейные ограничения не состоят из элементарных функций, необходимо преобразовать нелинейные функции в выражения оптимизации с помощью fcn2optimexpr. См. последнюю часть этого примера, «Альтернативная формулировка с использованием fcn2optimexpr» или «Преобразование нелинейной функции в выражение оптимизации».

Подход к решению этой задачи на основе решателя см. в разделе Решение ограниченной нелинейной проблемы на основе решателя.

Постановка проблемы: функция Розенброка

Рассмотрим проблему минимизации функции Розенброка

над единичным диском, что означает диск радиуса 1, центрированный в начале координат. Другими словами, найти $$x$$, который минимизирует функцию $$f(x$$) над $${}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}\mathrm{}$$x12+x22≤1 набора. Эта проблема заключается в минимизации нелинейной функции, подверженной нелинейному ограничению.

Функция Розенброка является стандартной тестовой функцией в оптимизации. Он имеет уникальное минимальное значение 0, достигнутое в точке [1,1]. Поиск минимума является проблемой для некоторых алгоритмов, потому что функция имеет небольшой минимум внутри глубоко изогнутой долины. Решение этой проблемы не в данный момент [1,1] потому что эта точка не удовлетворяет ограничению.

На этом рисунке показаны два вида функции Розенброка на диске блока. Вертикальная ось имеет логарифмический масштаб; другими словами, график показывает $$\log \mathrm{(}1+f$$(x)). Контурные линии лежат под графиком поверхности.

rosenbrock = @(x)100*(x(:,2) - x(:,1).^2).^2 + (1 - x(:,1)).^2; % Vectorized function

figure1 = figure('Position',[1 200 600 300]);
colormap('gray');
axis square;
R = 0:.002:1;
TH = 2*pi*(0:.002:1); 
X = R'*cos(TH);
Y = R'*sin(TH); 
Z = log(1 + rosenbrock([X(:),Y(:)]));
Z = reshape(Z,size(X));

% Create subplot
subplot1 = subplot(1,2,1,'Parent',figure1);
view([124 34]);
grid('on');
hold on;

% Create surface
surf(X,Y,Z,'Parent',subplot1,'LineStyle','none');

% Create contour
contour(X,Y,Z,'Parent',subplot1);

% Create subplot
subplot2 = subplot(1,2,2,'Parent',figure1);
view([234 34]);
grid('on');
hold on

% Create surface
surf(X,Y,Z,'Parent',subplot2,'LineStyle','none');

% Create contour
contour(X,Y,Z,'Parent',subplot2);

% Create textarrow
annotation(figure1,'textarrow',[0.4 0.31],...
    [0.055 0.16],...
    'String',{'Minimum at (0.7864,0.6177)'});

% Create arrow
annotation(figure1,'arrow',[0.59 0.62],...
    [0.065 0.34]);

title("Rosenbrock's Function: Two Views")

hold off

rosenbrock дескриптор функции вычисляет функцию Розенброка сразу в любом числе точек 2-D. Эта векторизация ускоряет печать функции и может быть полезна в других контекстах для оценки скорости функции в нескольких точках.

Функция $$f(x$$) называется целевой функцией. Целевой функцией является функция, которую необходимо свернуть. $${}_{\mathrm{}}^{\mathrm{}}{}_{\mathrm{}}^{\mathrm{}}\mathrm{}$$x12+x22≤1 неравенства называется ограничением. Ограничения ограничивают набор $$$$x, по которому решатель ищет минимум. Можно иметь любое количество ограничений, которые являются неравенствами или уравнениями.

Определение проблемы с помощью переменных оптимизации

Проблемный подход к оптимизации использует переменные оптимизации для определения цели и ограничений. Существует два подхода к созданию выражений с использованием этих переменных:

Для этой задачи и целевая функция, и нелинейное ограничение являются многочленами, поэтому выражения можно записать непосредственно в терминах переменных оптимизации. Создание переменной оптимизации 2-D с именем 'x'.

x = optimvar('x',1,2);

Создайте целевую функцию как многочлен в переменной оптимизации.

obj = 100*(x(2) - x(1)^2)^2 + (1 - x(1))^2;

Создание задачи оптимизации с именем prob наличие obj в качестве целевой функции.

prob = optimproblem('Objective',obj);

Создайте нелинейное ограничение как полином в переменной оптимизации.

nlcons = x(1)^2 + x(2)^2 <= 1;

Включите нелинейное ограничение в задачу.

prob.Constraints.circlecons = nlcons;

Просмотрите проблему.

show(prob)

  OptimizationProblem : 

	Solve for:
       x

	minimize :
       ((100 .* (x(2) - x(1).^2).^2) + (1 - x(1)).^2)


	subject to circlecons:
       (x(1).^2 + x(2).^2) <= 1
     

Решить проблему

Для решения проблемы оптимизации звоните solve. Задача требует начальной точки, которая представляет собой структуру, дающую начальное значение переменной оптимизации. Создание начальной структуры точек x0 с x-значением, $$$$равным [0 0].

x0.x = [0 0];
[sol,fval,exitflag,output] = solve(prob,x0)

Solving problem using fmincon.

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

sol = struct with fields:
    x: [0.7864 0.6177]

fval = 0.0457

exitflag = 
    OptimalSolution

output = struct with fields:
              iterations: 24
               funcCount: 34
         constrviolation: 0
                stepsize: 6.9161e-06
               algorithm: 'interior-point'
           firstorderopt: 2.1625e-08
            cgiterations: 4
                 message: '...'
            bestfeasible: [1x1 struct]
     objectivederivative: "reverse-AD"
    constraintderivative: "closed-form"
                  solver: 'fmincon'

Анализ решения

Решение показывает exitflag = OptimalSolution. Этот флаг выхода указывает, что решение является локальным оптимумом. Сведения о попытке найти лучшее решение см. в разделе Когда решатель добьется успеха.

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

infeas = output.constrviolation

infeas = 0

Несходимость 0 указывает на то, что решение осуществимо.

infeas = infeasibility(nlcons,sol)

infeas = 0

Опять же, несходимость 0 указывает на то, что решение осуществимо.

nx = norm(sol.x)

nx = 1.0000

output структура дает больше информации о процессе решения, например, количество итераций (24), решатель (fmincon) и количество оценок функций (84). Дополнительные сведения об этих статистических данных см. в разделе Допуски и критерии остановки.

Альтернативная формулировка с использованием fcn2optimexpr

Для более сложных выражений запишите файлы функций для целевой функции или функции ограничения и преобразуйте их в выражения оптимизации с помощью fcn2optimexpr. Например, базис нелинейной функции ограничения находится в disk.m файл:

type disk

function radsqr = disk(x) 

radsqr = x(1)^2 + x(2)^2;

Преобразовать этот файл функции в выражение оптимизации.

radsqexpr = fcn2optimexpr(@disk,x);

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

rosenexpr = fcn2optimexpr(rosenbrock,x);

Создайте задачу оптимизации с помощью этих преобразованных выражений оптимизации.

convprob = optimproblem('Objective',rosenexpr,'Constraints',radsqexpr <= 1);

Просмотрите новую проблему.

show(convprob)

  OptimizationProblem : 

	Solve for:
       x

	minimize :
       anonymousFunction2(x)

       where:

         anonymousFunction2 = @(x)100*(x(:,2)-x(:,1).^2).^2+(1-x(:,1)).^2;


	subject to :
       disk(x) <= 1
     

Решите новую проблему. Раствор по существу такой же, как и ранее.

[sol,fval,exitflag,output] = solve(convprob,x0)

Solving problem using fmincon.

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

sol = struct with fields:
    x: [0.7864 0.6177]

fval = 0.0457

exitflag = 
    OptimalSolution

output = struct with fields:
              iterations: 24
               funcCount: 84
         constrviolation: 0
                stepsize: 6.9162e-06
               algorithm: 'interior-point'
           firstorderopt: 2.4373e-08
            cgiterations: 4
                 message: '...'
            bestfeasible: [1x1 struct]
     objectivederivative: "finite-differences"
    constraintderivative: "finite-differences"
                  solver: 'fmincon'

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