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

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

Целевая функция, как функция количества переменных задачи 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);

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

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.

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