Minimización cuadrática con el hessian denso, estructurado

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.

Aprovecha la estructura de hessian
Paso 1: decidir qué parte de H pasar a quadprog como primer argumento.
Paso 2: escribir una función para computar productos de matriz hessian para H.
Paso 3: llama a una rutina de minimización cuadrática con un punto de partida.
Preacondicionamiento

Aprovecha la estructura de hessian

La confianza-región-reflexivo método puede resolver grandes problemas donde el hessian es denso pero estructurado.quadprog Para estos problemas, no se calcula con el hessian directamente, como lo hace para problemas de confianza-región-reflexivo con disperso, porque la formación sería la memoria intensiva.quadprogH*YHHH En su lugar, debe proporcionar una función que, dada una matriz e información sobre, calcula =.quadprogYHWH*Y

En este ejemplo, la matriz Hessiana tiene la estructura donde es una matriz simétrica dispersa 512-by-512, y es una matriz dispersa de 512 por 10 compuesta de un número de columnas densas.HH = B + A*A'BA Para evitar el uso excesivo de memoria que podría suceder al trabajar directamente porque es denso, el ejemplo proporciona una función de multiplicación de hessian,.HHqpbox4mult Esta función, cuando se pasa una matriz, utiliza matrices dispersas y para calcular el producto de matriz de hessian.YABW = H*Y = (B + A*A')*Y

En la primera parte de este ejemplo, las matrices y necesitan ser proporcionadas a la función de multiplicar de hessian.ABqpbox4mult Puede pasar una matriz como el primer argumento, que se pasa a la función de multiplicar de hessian.quadprog Puede utilizar una función anidada para proporcionar el valor de la segunda matriz.

La segunda parte del ejemplo muestra cómo apretar la tolerancia para compensar un preacondicionador aproximado en lugar de una matriz exacta.TolPCGH

Paso 1: decidir qué parte de H pasar a quadprog como primer argumento.

O bien se puede pasar como el primer argumento.ABquadprog El ejemplo elige pasar como el primer argumento porque esto da como resultado un mejor preacondicionador (ver).BPreacondicionamiento

quadprog(B,f,[],[],[],[],l,u,xstart,options)

Paso 2: escribir una función para computar productos de matriz hessian para H.

Ahora, defina una función querunqpbox4

Contiene una función anidada que utiliza y para calcular el producto de matriz de hessian, donde.qpbox4multABWW = H*Y = (B + A*A')*Y La función anidada debe tener el formulario
```
W = qpbox4mult(Hinfo,Y,...)
```
Los dos primeros argumentos y son obligatorios.HinfoY
Carga los parámetros del problema desde.qpbox4.mat
Se usa para establecer la opción en un identificador de función que apunta a.optimoptionsHessianMultiplyFcnqpbox4mult
Llamadas con el primer argumento.quadprogB

El primer argumento de la función anidada debe ser el mismo que el primer argumento pasado, que en este caso es la matriz B.qpbox4multquadprog

El segundo argumento es la matriz (de).qpbox4multYW = H*Y Porque espera ser utilizado para formar el producto matriz hessian, es siempre una matriz con filas, donde es el número de dimensiones en el problema.quadprogYYnn El número de columnas en puede variar.Y La función está anidada de modo que el valor de la matriz proviene de la función externa. software incluye el archivo.qpbox4multAOptimization Toolbox™runqpbox4.m

function [fval, exitflag, output, x] = runqpbox4 %RUNQPBOX4 demonstrates 'HessianMultiplyFcn' option for QUADPROG with bounds.  problem = load('qpbox4'); % Get xstart, u, l, B, A, f xstart = problem.xstart; u = problem.u; l = problem.l; B = problem.B; A = problem.A; f = problem.f; mtxmpy = @qpbox4mult; % function handle to qpbox4mult nested function  % Choose algorithm and the HessianMultiplyFcn option options = optimoptions(@quadprog,'Algorithm','trust-region-reflective','HessianMultiplyFcn',mtxmpy);  % Pass B to qpbox4mult via the H argument. Also, B will be used in % computing a preconditioner for PCG. [x, fval, exitflag, output] = quadprog(B,f,[],[],[],[],l,u,xstart,options);      function W = qpbox4mult(B,Y)         %QPBOX4MULT Hessian matrix product with dense structured Hessian.         %   W = qpbox4mult(B,Y) computes W = (B + A*A')*Y where         %   INPUT:         %       B - sparse square matrix (512 by 512)         %       Y - vector (or matrix) to be multiplied by B + A'*A.         %   VARIABLES from outer function runqpbox4:         %       A - sparse matrix with 512 rows and 10 columns.         %         %   OUTPUT:         %       W - The product (B + A*A')*Y.         %          % Order multiplies to avoid forming A*A',         %   which is large and dense         W = B*Y + A*(A'*Y);     end  end

Paso 3: llama a una rutina de minimización cuadrática con un punto de partida.

Para llamar a la rutina de minimización cuadrática contenida en, ingreserunqpbox4

[fval,exitflag,output] = runqpbox4;

para ejecutar el código anterior. A continuación, muestre los valores para,, y.fvalexitflagoutput.iterationsoutput.cgiterations

fval,exitflag,output.iterations, output.cgiterations
fval =    -1.0538e+03   exitflag =       3   ans =      18   ans =      30

Después de 18 iteraciones con un total de 30 iteraciones PCG, el valor de la función se reduce a

fval
fval =  -1.0538e+003

y la optimalidad de primer orden es

output.firstorderopt
ans =     0.0043

Preacondicionamiento

A veces no se puede usar para calcular un preacondicionador porque solo existe implícitamente.quadprogHH En su lugar, usa, el argumento pasado en lugar de, para calcular un preacondicionador. es una buena opción porque es del mismo tamaño que y se aproxima a algún grado.quadprogBHBHH Si no fueran del mismo tamaño que, calcularían un preacondicionador basado en algunas matrices de escalado diagonal determinadas a partir del algoritmo.BHquadprog Típicamente, esto no llevaría a cabo también.

Dado que el preacondicionador es más aproximado que cuando está disponible explícitamente, puede ser necesario ajustar el parámetro a un valor algo más pequeño.HTolPCG Este ejemplo es el mismo que el anterior, pero se reduce del valor predeterminado 0,1 a 0,01.TolPCG

function [fval, exitflag, output, x] = runqpbox4prec %RUNQPBOX4PREC demonstrates 'HessianMultiplyFcn' option for QUADPROG with bounds.  problem = load('qpbox4'); % Get xstart, u, l, B, A, f xstart = problem.xstart; u = problem.u; l = problem.l; B = problem.B; A = problem.A; f = problem.f; mtxmpy = @qpbox4mult; % function handle to qpbox4mult nested function  % Choose algorithm, the HessianMultiplyFcn option, and override the TolPCG option options = optimoptions(@quadprog,'Algorithm','trust-region-reflective',...     'HessianMultiplyFcn',mtxmpy,'TolPCG',0.01);  % Pass B to qpbox4mult via the H argument. Also, B will be used in % computing a preconditioner for PCG. % A is passed as an additional argument after 'options' [x, fval, exitflag, output] = quadprog(B,f,[],[],[],[],l,u,xstart,options);      function W = qpbox4mult(B,Y)         %QPBOX4MULT Hessian matrix product with dense structured Hessian.         %   W = qpbox4mult(B,Y) computes W = (B + A*A')*Y where         %   INPUT:         %       B - sparse square matrix (512 by 512)         %       Y - vector (or matrix) to be multiplied by B + A'*A.         %   VARIABLES from outer function runqpbox4prec:         %       A - sparse matrix with 512 rows and 10 columns.         %         %   OUTPUT:         %       W - The product (B + A*A')*Y.         %          % Order multiplies to avoid forming A*A',         %   which is large and dense         W = B*Y + A*(A'*Y);     end  end

Ahora, introduzca

[fval,exitflag,output] = runqpbox4prec;

para ejecutar el código anterior. Después de 18 iteraciones y 50 iteraciones PCG, el valor de la función tiene el mismo valor que cinco dígitos significativos