lbfgs (Manual de Maxima 5.47post)

60 lbfgs

Introducción a lbfgs
Funciones y variables para lbfgs

60.1 Introducción a lbfgs

La función lbfgs implementa el llamado algoritmo L-BFGS [1] para resolver problemas de minimización sin restricciones mediante una técnica cuasi-Newton con memoria limitada (BFGS). El término memoria limitada procede del hecho de que se almacena una aproximación de rango bajo de la inversa de la matriz hessiana, en lugar de la matriz completa. El programa fue originalmente escrito en Fortran [2] por Jorge Nocedal, incorporando algunas funciones escritas originalmente por Jorge J. Moré y David J. Thuente, traducidas posteriormente a Lisp automáticamente con el programa f2cl. El paquete lbfgs contiene el código traducido, junto con una función interfaz que para controlar ciertos detalles.

Referencias:

[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503–528 (1989)

[2] http://netlib.org/opt/lbfgs_um.shar

60.2 Funciones y variables para lbfgs

Función: lbfgs (FOM, X, X0, epsilon, iprint) ¶

Function: lbfgs ([FOM, grad] X, X0, epsilon, iprint) ¶

Encuentra una solución aproximada para el problema de minimización sin restricciones de la función objetivo FOM para la lista de variables X, partiendo de los estimadores iniciales X0, de tal manera que norm(grad(FOM)) < epsilon*max(1, norm(X)).

Si el argumento grad está presente, debe ser el gradiente de FOM respecto de las variables X. grad puede ser una lista o una función que devuelva una lista con igual número de elementos que X. Si el argumento no está presente, el gradiente se calcula automáticamente mediante derivación simbólica. Si FOM es una función, el gradiente grad debe ser suministrado por el usuario.

El algoritmo utilizado es una técnica cuasi-Newton con memoria limitada (BFGS) [1]. El término memoria limitada procede del hecho de que se almacena una aproximación de rango bajo de la inversa de la matriz hessiana, en lugar de la matriz completa. Cada iteración del algoritmo es una búsqueda a lo largo de una recta, cuya dirección se calcula a partir de la matriz inversa aproximada del hessiano. La función objetivo decrece siempre tras cada búsqueda exitosa a lo largo de la recta; además, casi siempre decrece también el módulo del gradiente de la función.

El argumento iprint controla los mensajes de progreso que envía la función lbfgs.

iprint[1]

iprint[1] controla la frecuencia con la que se emiten los mensajes.

iprint[1] < 0: No se envían mensajes.
iprint[1] = 0: Mensajes únicamente en la primera y última iteraciones.
iprint[1] > 0: Imprime un mensaje cada iprint[1] iteraciones.

iprint[2]

iprint[2] controla la cantidad de información contenida en los mensajes.

iprint[2] = 0: Imprime contador de iteraciones, número de evaluaciones de FOM, valor de FOM, módulo del gradiente de FOM y amplitud del paso.
iprint[2] = 1: Igual que iprint[2] = 0, incluyendo X0 y el gradiente de FOM evaluado en X0.
iprint[2] = 2: Igual que iprint[2] = 1, incluyendo los valores de X en cada iteración.
iprint[2] = 3: Igual que iprint[2] = 2, incluyendo el gradiente de FOM en cada iteración.

Las columnas devueltas por lbfgs son las siguientes:

I: Número de iteraciones. Se incremente tras cada búsqueda a lo largo de una recta.
NFN: Número de evaluaciones de la función objetivo.
FUNC: Valor de la función objetivo al final de cada iteración.
GNORM: Módulo del gradiente de la función objetivo al final de cada iteración.
STEPLENGTH: Un parámetro interno del algoritmo de búsqueda.

Para más información sobre el algoritmo se puede acudir a los comentarios en el código original en Fortran [2].

Véanse también lbfgs_nfeval_max y lbfgs_ncorrections.

Referencias:

[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503–528 (1989)

[2] http://netlib.org/opt/lbfgs_um.shar

Ejemplos:

La misma función objetivo utilizada por FGCOMPUTE en el programa sdrive.f del paquete LBFGS de Netlib. Nótese que las variables en cuestión están subindicadas. La función objetivo tiene un mínimo exacto igual a cero en u[k] = 1, para k = 1, ..., 8.

(%i1) load ("lbfgs")$
(%i2) t1[j] := 1 - u[j];
(%o2)                     t1  := 1 - u
                            j         j
(%i3) t2[j] := 10*(u[j + 1] - u[j]^2);
                                          2
(%o3)                t2  := 10 (u      - u )
                       j         j + 1    j
(%i4) n : 8;
(%o4)                           8
(%i5) FOM : sum (t1[2*j - 1]^2 + t2[2*j - 1]^2, j, 1, n/2);
                 2 2           2              2 2           2
(%o5) 100 (u  - u )  + (1 - u )  + 100 (u  - u )  + (1 - u )
            8    7           7           6    5           5
                     2 2           2              2 2           2
        + 100 (u  - u )  + (1 - u )  + 100 (u  - u )  + (1 - u )
                4    3           3           2    1           1
(%i6) lbfgs (FOM, '[u[1],u[2],u[3],u[4],u[5],u[6],u[7],u[8]],
       [-1.2, 1, -1.2, 1, -1.2, 1, -1.2, 1], 1e-3, [1, 0]);
*************************************************
  N=    8   NUMBER OF CORRECTIONS=25
       INITIAL VALUES
 F=  9.680000000000000D+01   GNORM=  4.657353755084533D+02
*************************************************

 I NFN   FUNC                    GNORM                   STEPLENGTH

 1   3   1.651479526340304D+01   4.324359291335977D+00   7.926153934390631D-04
 2   4   1.650209316638371D+01   3.575788161060007D+00   1.000000000000000D+00
 3   5   1.645461701312851D+01   6.230869903601577D+00   1.000000000000000D+00
 4   6   1.636867301275588D+01   1.177589920974980D+01   1.000000000000000D+00
 5   7   1.612153014409201D+01   2.292797147151288D+01   1.000000000000000D+00
 6   8   1.569118407390628D+01   3.687447158775571D+01   1.000000000000000D+00
 7   9   1.510361958398942D+01   4.501931728123679D+01   1.000000000000000D+00
 8  10   1.391077875774293D+01   4.526061463810630D+01   1.000000000000000D+00
 9  11   1.165625686278198D+01   2.748348965356907D+01   1.000000000000000D+00
10  12   9.859422687859144D+00   2.111494974231706D+01   1.000000000000000D+00
11  13   7.815442521732282D+00   6.110762325764183D+00   1.000000000000000D+00
12  15   7.346380905773044D+00   2.165281166715009D+01   1.285316401779678D-01
13  16   6.330460634066464D+00   1.401220851761508D+01   1.000000000000000D+00
14  17   5.238763939854303D+00   1.702473787619218D+01   1.000000000000000D+00
15  18   3.754016790406625D+00   7.981845727632704D+00   1.000000000000000D+00
16  20   3.001238402313225D+00   3.925482944745832D+00   2.333129631316462D-01
17  22   2.794390709722064D+00   8.243329982586480D+00   2.503577283802312D-01
18  23   2.563783562920545D+00   1.035413426522664D+01   1.000000000000000D+00
19  24   2.019429976373283D+00   1.065187312340952D+01   1.000000000000000D+00
20  25   1.428003167668592D+00   2.475962450735100D+00   1.000000000000000D+00
21  27   1.197874264859232D+00   8.441707983339661D+00   4.303451060697367D-01
22  28   9.023848942003913D-01   1.113189216665625D+01   1.000000000000000D+00
23  29   5.508226405855795D-01   2.380830599637816D+00   1.000000000000000D+00
24  31   3.902893258879521D-01   5.625595817143044D+00   4.834988416747262D-01
25  32   3.207542206881058D-01   1.149444645298493D+01   1.000000000000000D+00
26  33   1.874468266118200D-01   3.632482152347445D+00   1.000000000000000D+00
27  34   9.575763380282112D-02   4.816497449000391D+00   1.000000000000000D+00
28  35   4.085145106760390D-02   2.087009347116811D+00   1.000000000000000D+00
29  36   1.931106005512628D-02   3.886818624052740D+00   1.000000000000000D+00
30  37   6.894000636920714D-03   3.198505769992936D+00   1.000000000000000D+00
31  38   1.443296008850287D-03   1.590265460381961D+00   1.000000000000000D+00
32  39   1.571766574930155D-04   3.098257002223532D-01   1.000000000000000D+00
33  40   1.288011779655132D-05   1.207784334505595D-02   1.000000000000000D+00
34  41   1.806140190993455D-06   4.587890258846915D-02   1.000000000000000D+00
35  42   1.769004612050548D-07   1.790537363138099D-02   1.000000000000000D+00
36  43   3.312164244118216D-10   6.782068546986653D-04   1.000000000000000D+00


 THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
 IFLAG = 0
(%o6) [u  = 1.000005339816132, u  = 1.000009942840108, 
        1                       2
u  = 1.000005339816132, u  = 1.000009942840108, 
 3                       4
u  = 1.000005339816132, u  = 1.000009942840108, 
 5                       6
u  = 1.000005339816132, u  = 1.000009942840108]
 7                       8

Un problema de regresión. La función objetivo es el cuadrado medio de la diferencia entre la predicción F(X[i]) y el valor observado Y[i]. La función F es monótona y acotada (llamada en ocasiones "sigmoidal"). En este ejemplo, lbfgs calcula valores aproximados para los parámetros de F y plot2d hace una representación gráfica comparativa de F junto con los datos observados.

(%i1) load ("lbfgs")$
(%i2) FOM : '((1/length(X))*sum((F(X[i]) - Y[i])^2, i, 1,
                                                length(X)));
                               2
               sum((F(X ) - Y ) , i, 1, length(X))
                       i     i
(%o2)          -----------------------------------
                            length(X)
(%i3) X : [1, 2, 3, 4, 5];
(%o3)                    [1, 2, 3, 4, 5]
(%i4) Y : [0, 0.5, 1, 1.25, 1.5];
(%o4)                [0, 0.5, 1, 1.25, 1.5]
(%i5) F(x) := A/(1 + exp(-B*(x - C)));
                                   A
(%o5)            F(x) := ----------------------
                         1 + exp((- B) (x - C))
(%i6) ''FOM;
                A               2            A                2
(%o6) ((----------------- - 1.5)  + (----------------- - 1.25)
          - B (5 - C)                  - B (4 - C)
        %e            + 1            %e            + 1
            A             2            A               2
 + (----------------- - 1)  + (----------------- - 0.5)
      - B (3 - C)                - B (2 - C)
    %e            + 1          %e            + 1
             2
            A
 + --------------------)/5
      - B (1 - C)     2
   (%e            + 1)
(%i7) estimates : lbfgs (FOM, '[A, B, C], [1, 1, 1], 1e-4, [1, 0]);
*************************************************
  N=    3   NUMBER OF CORRECTIONS=25
       INITIAL VALUES
 F=  1.348738534246918D-01   GNORM=  2.000215531936760D-01
*************************************************

I  NFN  FUNC                    GNORM                   STEPLENGTH
1    3  1.177820636622582D-01   9.893138394953992D-02   8.554435968992371D-01  
2    6  2.302653892214013D-02   1.180098521565904D-01   2.100000000000000D+01  
3    8  1.496348495303004D-02   9.611201567691624D-02   5.257340567840710D-01  
4    9  7.900460841091138D-03   1.325041647391314D-02   1.000000000000000D+00  
5   10  7.314495451266914D-03   1.510670810312226D-02   1.000000000000000D+00  
6   11  6.750147275936668D-03   1.914964958023037D-02   1.000000000000000D+00  
7   12  5.850716021108202D-03   1.028089194579382D-02   1.000000000000000D+00  
8   13  5.778664230657800D-03   3.676866074532179D-04   1.000000000000000D+00  
9   14  5.777818823650780D-03   3.010740179797108D-04   1.000000000000000D+00


 THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
 IFLAG = 0
(%o7) [A = 1.461933911464101, B = 1.601593973254801, 
                                           C = 2.528933072164855]
(%i8) plot2d ([F(x), [discrete, X, Y]], [x, -1, 6]), ''estimates;
(%o8)

Especificando el gradiente de la función objetivo en lugar de calcularlo simbólicamente.

(%i1) load ("lbfgs")$
(%i2) F(a, b, c) := (a - 5)^2 + (b - 3)^4 + (c - 2)^6$
(%i3) define(F_grad(a, b, c),
             map (lambda ([x], diff (F(a, b, c), x)), [a, b, c]))$
(%i4) estimates : lbfgs ([F, F_grad],
                   [a, b, c], [0, 0, 0], 1e-4, [1, 0]);
*************************************************
  N=    3   NUMBER OF CORRECTIONS=25
       INITIAL VALUES
 F=  1.700000000000000D+02   GNORM=  2.205175729958953D+02
*************************************************

   I  NFN     FUNC                    GNORM                   STEPLENGTH

   1    2     6.632967565917637D+01   6.498411132518770D+01   4.534785987412505D-03  
   2    3     4.368890936228036D+01   3.784147651974131D+01   1.000000000000000D+00  
   3    4     2.685298972775191D+01   1.640262125898520D+01   1.000000000000000D+00  
   4    5     1.909064767659852D+01   9.733664001790506D+00   1.000000000000000D+00  
   5    6     1.006493272061515D+01   6.344808151880209D+00   1.000000000000000D+00  
   6    7     1.215263596054292D+00   2.204727876126877D+00   1.000000000000000D+00  
   7    8     1.080252896385329D-02   1.431637116951845D-01   1.000000000000000D+00  
   8    9     8.407195124830860D-03   1.126344579730008D-01   1.000000000000000D+00  
   9   10     5.022091686198525D-03   7.750731829225275D-02   1.000000000000000D+00  
  10   11     2.277152808939775D-03   5.032810859286796D-02   1.000000000000000D+00  
  11   12     6.489384688303218D-04   1.932007150271009D-02   1.000000000000000D+00  
  12   13     2.075791943844547D-04   6.964319310814365D-03   1.000000000000000D+00  
  13   14     7.349472666162258D-05   4.017449067849554D-03   1.000000000000000D+00  
  14   15     2.293617477985238D-05   1.334590390856715D-03   1.000000000000000D+00  
  15   16     7.683645404048675D-06   6.011057038099202D-04   1.000000000000000D+00


 THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
 IFLAG = 0
(%o4) [a = 5.000086823042934, b = 3.052395429705181, 
                                           c = 1.927980629919583]

Variable: lbfgs_nfeval_max ¶

Valor por defecto: 100

La variable lbfgs_nfeval_max almacena el número máximo de evaluaciones de la función objetivo en lbfgs. Cuando se alcanza el valor lbfgs_nfeval_max, lbfgs devuelve el resultado logrado en la última iteración exitosa.

Variable: lbfgs_ncorrections ¶

Valor por defecto: 25

La variable lbfgs_ncorrections almacena el número de correcciones aplicadas a la matriz inversa aproximada del hessiano, la cual es gestionada por lbfgs.