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 con algoritmo de punto interior

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.[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 la matriz.

spy(H)

Crear restricción lineal y objetivo

La restricción lineal es que la suma de los elementos de la solución no es positiva. La función objetiva contiene un término lineal expresado en el vector.f

A = ones(1,n); b = 0; f = 1:n; f = -f;

Resuelve el problema

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

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> 

En muchos equipos no se puede crear una matriz completa cuando = 30.000.nnn Por lo tanto, puede ejecutar este problema solo con matrices dispersas.

Examine la solución

Vea el valor de la función objetiva, el número de iteraciones y el multiplicador de Lagrange asociado con la 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.ineqlin)
The objective function value is -3.133073e+10. The number of iterations is 7. The Lagrange multiplier is 1.500050e+04. 

Debido a que no hay límites inferiores, límites superiores o restricciones de igualdad lineales, el único multiplicador significativo de Lagrange es.lambda.ineqlin Dado que es distinto de cero, puede decir que la restricción de desigualdad está activa.lambda.ineqlin Evalúe la restricción para ver que la solución está en el límite.

fprintf('The linear inequality constraint A*x has value %d.\n',A*x)
The linear inequality constraint A*x has value 9.150244e-08. 

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(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)')

Consulte también

|

Temas relacionados