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

Funciones y variables para lbfgs
================================

 -- Función: lbfgs (FOM, 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).

     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);
          (%o1)   /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac
          (%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.657353755084532D+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.501931728123680D+01   1.000000000000000D+00
           8  10   1.391077875774294D+01   4.526061463810632D+01   1.000000000000000D+00
           9  11   1.165625686278198D+01   2.748348965356917D+01   1.000000000000000D+00
          10  12   9.859422687859137D+00   2.111494974231644D+01   1.000000000000000D+00
          11  13   7.815442521732281D+00   6.110762325766556D+00   1.000000000000000D+00
          12  15   7.346380905773160D+00   2.165281166714631D+01   1.285316401779533D-01
          13  16   6.330460634066370D+00   1.401220851762050D+01   1.000000000000000D+00
          14  17   5.238763939851439D+00   1.702473787613255D+01   1.000000000000000D+00
          15  18   3.754016790406701D+00   7.981845727704576D+00   1.000000000000000D+00
          16  20   3.001238402309352D+00   3.925482944716691D+00   2.333129631296807D-01
          17  22   2.794390709718290D+00   8.243329982546473D+00   2.503577283782332D-01
          18  23   2.563783562918759D+00   1.035413426521790D+01   1.000000000000000D+00
          19  24   2.019429976377856D+00   1.065187312346769D+01   1.000000000000000D+00
          20  25   1.428003167670903D+00   2.475962450826961D+00   1.000000000000000D+00
          21  27   1.197874264861340D+00   8.441707983493810D+00   4.303451060808756D-01
          22  28   9.023848941942773D-01   1.113189216635162D+01   1.000000000000000D+00
          23  29   5.508226405863770D-01   2.380830600326308D+00   1.000000000000000D+00
          24  31   3.902893258815567D-01   5.625595816584421D+00   4.834988416524465D-01
          25  32   3.207542206990315D-01   1.149444645416472D+01   1.000000000000000D+00
          26  33   1.874468266362791D-01   3.632482152880997D+00   1.000000000000000D+00
          27  34   9.575763380706598D-02   4.816497446154354D+00   1.000000000000000D+00
          28  35   4.085145107543406D-02   2.087009350166495D+00   1.000000000000000D+00
          29  36   1.931106001379290D-02   3.886818608498966D+00   1.000000000000000D+00
          30  37   6.894000721499670D-03   3.198505796342214D+00   1.000000000000000D+00
          31  38   1.443296033051864D-03   1.590265471025043D+00   1.000000000000000D+00
          32  39   1.571766603154336D-04   3.098257063980634D-01   1.000000000000000D+00
          33  40   1.288011776581970D-05   1.207784183577257D-02   1.000000000000000D+00
          34  41   1.806140173752971D-06   4.587890233385193D-02   1.000000000000000D+00
          35  42   1.769004645459358D-07   1.790537375052208D-02   1.000000000000000D+00
          36  43   3.312164100763217D-10   6.782068426119681D-04   1.000000000000000D+00

           THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
           IFLAG = 0
          (%o6) [u  = 1.000005339815974, u  = 1.000009942839805,
                  1                       2
          u  = 1.000005339815974, u  = 1.000009942839805,
           3                       4
          u  = 1.000005339815974, u  = 1.000009942839805,
           5                       6
          u  = 1.000005339815974, u  = 1.000009942839805]
           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);
          (%o1)   /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac
          (%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.496348495303005D-02   9.611201567691633D-02   5.257340567840707D-01
          4    9  7.900460841091139D-03   1.325041647391314D-02   1.000000000000000D+00
          5   10  7.314495451266917D-03   1.510670810312237D-02   1.000000000000000D+00
          6   11  6.750147275936680D-03   1.914964958023047D-02   1.000000000000000D+00
          7   12  5.850716021108205D-03   1.028089194579363D-02   1.000000000000000D+00
          8   13  5.778664230657791D-03   3.676866074530332D-04   1.000000000000000D+00
          9   14  5.777818823650782D-03   3.010740179797255D-04   1.000000000000000D+00

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

 -- 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.