Квадратичное программирование со связанными ограничениями: основанный на проблеме

Этот пример показывает, как сформулировать и решить масштабируемую связано ограниченную проблему с квадратичной целевой функцией. Пример показывает поведение решения с помощью нескольких алгоритмов. Проблема может иметь любое количество переменных; количество переменных является шкалой. Для основанной на решателе версии этого примера смотрите Квадратичную Минимизацию со Связанными Ограничениями.

Целевая функция, как функция количества проблемных переменных n,

$2 \sum_{i = 1}^{n} x_{i}^{2} - 2 \sum_{i = 1}^{n - 1} x_{i} x_{i + 1} - 2 x_{1} - 2 x_{n} .$

Создайте проблему

Создайте проблемную переменную под названием x, который имеет 400 компонентов. Кроме того, создайте выражение под названием objec для целевой функции. Связанный каждая переменная ниже 0 и выше 0,9, кроме позволяют $x_{n}$ быть неограниченным.

n = 400;
x = optimvar('x',n,'LowerBound',0,'UpperBound',0.9);
x(n).LowerBound = -Inf;
x(n).UpperBound = Inf;
prevtime = 1:n-1;
nexttime = 2:n;
objec = 2*sum(x.^2) - 2*sum(x(nexttime).*x(prevtime)) - 2*x(1) - 2*x(end);

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

qprob = optimproblem('Objective',objec);

Создайте опции, которые задают алгоритм 'trust-region-reflective' quadprog и никакое отображение. Создайте начальную точку, приблизительно сосредоточенную между границами.

opts = optimoptions('quadprog','Algorithm','trust-region-reflective','Display','off');
x0 = 0.5*ones(n,1);
x00 = struct('x',x0);

Решите проблему и исследуйте решение

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

[sol,qfval,qexitflag,qoutput] = solve(qprob,x00,'options',opts);

Постройте решение.

plot(sol.x,'b-')
xlabel('Index')
ylabel('x(index)')

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

fprintf('Exit flag = %d, iterations = %d, cg iterations = %d\n',...
    double(qexitflag),qoutput.iterations,qoutput.cgiterations)

Exit flag = 3, iterations = 19, cg iterations = 1668

Было много итераций метода сопряженных градиентов.

Настройте опции для увеличенной эффективности

Сократите количество итераций метода сопряженных градиентов путем установки опции SubproblemAlgorithm на 'factorization'. Эта опция заставляет решатель использовать более дорогой внутренний метод решения, который устраняет шаги метода сопряженных градиентов для сети полные сбережения времени в этом случае.

opts.SubproblemAlgorithm = 'factorization';
[sol2,qfval2,qexitflag2,qoutput2] = solve(qprob,x00,'options',opts);
fprintf('Exit flag = %d, iterations = %d, cg iterations = %d\n',...
    double(qexitflag2),qoutput2.iterations,qoutput2.cgiterations)

Exit flag = 3, iterations = 10, cg iterations = 0

Количество итераций и уменьшенных итераций метода сопряженных градиентов.

Сравните решения с решением `'interior-point'`

Сравните эти решения с тем полученным использованием алгоритма 'interior-point' по умолчанию. Алгоритм 'interior-point' не использует начальную точку, не передавайте x00 solve.

opts = optimoptions('quadprog','Algorithm','interior-point-convex','Display','off');
[sol3,qfval3,qexitflag3,qoutput3] = solve(qprob,'options',opts);
fprintf('Exit flag = %d, iterations = %d, cg iterations = %d\n',...
    double(qexitflag3),qoutput3.iterations,0)

Exit flag = 1, iterations = 8, cg iterations = 0

middle = floor(n/2);
fprintf('The three solutions are slightly different.\nThe middle component is %f, %f, or %f.\n',...
    sol.x(middle),sol2.x(middle),sol3.x(middle))

The three solutions are slightly different.
The middle component is 0.896446, 0.897823, or 0.857389.

fprintf('The relative norm of sol - sol2 is %f.\n',norm(sol.x-sol2.x)/norm(sol.x))

The relative norm of sol - sol2 is 0.001369.

fprintf('The relative norm of sol2 - sol3 is %f.\n',norm(sol2.x-sol3.x)/norm(sol2.x))

The relative norm of sol2 - sol3 is 0.035100.

fprintf(['The three objective function values are %f, %f, and %f.\n' ...
    'The ''interior-point'' algorithm is slightly less accurate.'],qfval,qfval2,qfval3)

The three objective function values are -1.985000, -1.985000, and -1.984963.
The 'interior-point' algorithm is slightly less accurate.

Документация