Большая разреженная квадратичная программа с алгоритмом внутренней точки
Этот пример показывает значение использования разреженной арифметики, когда у вас есть разреженная задача. Матрица имеет n строки, где вы выбираете n быть большим значением и несколькими ненулевыми диагональными полосами. Полная матрица размеров n-by- n может использовать всю доступную память, но разреженная матрица не представляет никакой проблемы.
Задача состоит в том, чтобы минимизировать x'*H*x/2 + f'*x при условии, что
x(1) + x(2) + ... + x(n) <= 0,
где f = [-1;-2;-3;...;-n]. H является разреженной симметричной полосной матрицей.
Создайте разреженную квадратичную матрицу
Создайте симметричную циркулянтную матрицу на основе сдвигов вектора [3,6,2,14,2,6,3], с 14 на основной диагонали. Пусть матрица n-by- n, где n = 30,000.
n = 3e4;
H2 = speye(n);
H = 3*circshift(H2,-3,2) + 6*circshift(H2,-2,2) + 2*circshift(H2,-1,2)...
+ 14*H2 + 2*circshift(H2,1,2) + 6*circshift(H2,2,2) + 3*circshift(H2,3,2);Просмотрите матричную структуру.
spy(H)
Создайте линейные ограничения и цель
Линейное ограничение состоит в том, что сумма элементов решения является непозитивной. Целевая функция содержит линейный член, выраженный в векторе f.
A = ones(1,n); b = 0; f = 1:n; f = -f;
Решите задачу
Решите квадратичную задачу программирования, используя 'interior-point-convex' алгоритм. Чтобы предотвратить преждевременную остановку решателя, установите StepTolerance опция для 0.
options = optimoptions(@quadprog,'Algorithm','interior-point-convex','StepTolerance',0); [x,fval,exitflag,output,lambda] = ... quadprog(H,f,A,b,[],[],[],[],[],options);
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. <stopping criteria details>
На многих компьютерах невозможно создать полную n-by- n матрица, когда n = 30,000. Таким образом, вы можете запустить эту задачу только при помощи разреженных матриц.
Исследуйте решение
Просмотрите значение целевой функции, количество итераций и множитель Лагранжа, сопоставленный с линейным неравенством.
fprintf('The objective function value is %d.\nThe number of iterations is %d.\nThe Lagrange multiplier is %d.\n',... fval,output.iterations,lambda.ineqlin)
The objective function value is -3.133073e+10. The number of iterations is 7. The Lagrange multiplier is 1.500050e+04.
Поскольку нет нижних границ, верхних границ или линейных ограничений равенства, единственный значимый множитель Лагранжа lambda.ineqlin. Потому что lambda.ineqlin является ненулевым, можно сказать, что ограничение неравенства активно. Оцените ограничение, чтобы увидеть, что решение находится на контуре.
fprintf('The linear inequality constraint A*x has value %d.\n',A*x)The linear inequality constraint A*x has value 9.150244e-08.
Сумма компонентов решения равна нулю в пределах допусков.
Решение x имеет три области: начальный фрагмент, конечный фрагмент и приблизительно линейный фрагмент по большей части решения. Постройте график трех областей.
subplot(3,1,1) plot(x(1:60)) title('x(1) Through x(60)') subplot(3,1,2) plot(x(61:n-60)) title('x(61) Through x(n-60)') subplot(3,1,3) plot(x(n-59:n)) title('x(n-59) Through x(n)')
