В этом примере показано значение разреженной арифметики при возникновении разреженной проблемы. Матрица имеет n строки, где вы выбираете n быть большим значением и несколькими ненулевыми диагональными полосами. Полная матрица размера nоколо-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около-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около-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)')
