Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Gran programa cuadrático disperso, basado en problemas

En este ejemplo se muestra el valor de usar aritmética dispersa cuando se tiene un problema disperso. La matriz tiene filas, donde elige ser un valor grande y algunas bandas diagonales que no son de cero.nn Una matriz completa de tamaño por puede utilizar toda la memoria disponible, pero una matriz dispersa no presenta ningún problema.nn

El problema es minimizar el sujeto ax'*H*x/2 + f'*x

,x(1) + x(2) + ... + x(n) <= 0

Dónde. es una matriz de bandas simétrica dispersa.f = [-1;-2;-3;...;-n]H

Crear matriz cuadrática dispersa

Crear una matriz circulante simétrica basada en los turnos del vector, con 14 estando en la Diagonal principal.H[3,6,2,14,2,6,3] Que la matriz esté por donde.nnn = 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);

Ver la estructura de matriz dispersa.

spy(H)

Crear variables de optimización y problema

Cree una variable de optimización y un problema.xqprob

x = optimvar('x',n); qprob = optimproblem;

Cree la función objetiva y las restricciones. Coloque el objetivo y las restricciones en.qprob

f = 1:n; obj = 1/2*x'*H*x - f*x; qprob.Objective = obj; cons = sum(x) <= 0; qprob.Constraints = cons;

Resuelve el problema

Resuelve el problema de programación cuadrática usando el algoritmo predeterminado y el álgebra lineal dispersa.interior-point-convex' Para evitar que el solucionador se detenga prematuramente, establezca la opción en.StepTolerance0

options = optimoptions('quadprog','Algorithm','interior-point-convex',...     'LinearSolver','sparse','StepTolerance',0); [sol,fval,exitflag,output,lambda] = solve(qprob,'Options',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> 

Examine la solución

Vea el valor de la función objetiva, el número de iteraciones y el multiplicador de Lagrange asociado a la restricción de desigualdad lineal.

fprintf('The objective function value is %d.\nThe number of iterations is %d.\nThe Lagrange multiplier is %d.\n',...     fval,output.iterations,lambda.Constraints)
The objective function value is -3.133073e+10. The number of iterations is 7. The Lagrange multiplier is 1.500050e+04. 

Evalúe la restricción para ver que la solución está en el límite.

fprintf('The linear inequality constraint sum(x) has value %d.\n',sum(sol.x))
The linear inequality constraint sum(x) has value 7.599738e-09. 

La suma de los componentes de la solución es cero dentro de las tolerancias.

La solución tiene tres regiones: una porción inicial, una porción final y una porción aproximadamente lineal sobre la mayor parte de la solución.x Trace las tres regiones.

subplot(3,1,1) plot(sol.x(1:60)) title('x(1) Through x(60)') subplot(3,1,2) plot(sol.x(61:n-60)) title('x(61) Through x(n-60)') subplot(3,1,3) plot(sol.x(n-59:n)) title('x(n-59) Through x(n)')

Temas relacionados