Introducedilhaão a lbfgs
========================

lbfgs é uma implementacedilhaão do algorítmo[1] L-BFGS (Broyden-Fletcher-Goldfarb-Shanno) para resolver problemas de minimizacedilhaão não limitada através de um algorítmo de memória limitada quasi-Newton (BFGS). Esse algorítmo é chamado de método de memória limitada porque uma aproximacedilhaão de baixo ranque da inverso da matriz Hessiana é armazenado em lugar da inversa da matriz Hessiana completa. O programa foi escrito origináriamente em Fortran [2] por Jorge Nocedal, incorporando algumas funcedilhaões originalmente escritas por Jorge J. Moré e David J. Thuente, e traduzidas para Lisp automaticamente através do programa f2cl. O pacote do Maxima lbfgs compreende o código traduzido e adicionalmente uma interface de funcedilhaão que gerencia alguns detallhes.

Referências:

[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

Funcedilhaões e Variáveis Definidas para lbfgs
==============================================

 -- Funcedilhaão: lbfgs (FOM, X, X0, EPSILON, IPRINT)

     Encontra uma solucedilhaão aproximada da minimizacedilhaão não limitada de número de mérito FOM sobre a lista de variáveis X, comecedilhaando a partir da estimativa inicial X0, tal que norm grad FOM < epsilon max(1, norm X).

     O algorítmo aplicado é um algorítmo de memória limitada[1] quasi-Newton (BFGS). Esse algorítmo é chamado de método de memória limitada porque uma aproximacedilhaão de baixo ranque da inverso da matriz Hessiana é armazenado em lugar da inversa da matriz Hessiana completa. Cada iteracedilhaão do algorítmo é uma busca de linha, isto é, uma busca ao longo de um raio em torno da variáveis X, com a direcedilhaão de busca calculada a partir da Hessian inversa aproximada. O FOM é sempre decrementado por meio de uma busca de linha realizada com sucesso. Usualmente (mas não sempre) a norma do gradiente de FOM também é decrementada.

     IPRINT controla as messaens de progresso mostradas através de lbfgs.

     iprint[1]
          IPRINT[1] controla a freqüência das mensagens de progresso.

          iprint[1] < 0
               Nenhuma mensagem de progresso.

          iprint[1] = 0
               Messagens na primeira iteracedilhaão e na última iteracedilhaão.

          iprint[1] > 0
               Mostra uma mensagem a cada IPRINT[1] iteracedilhaões.

     iprint[2]
          IPRINT[2] controla a quantidade de informacedilhaões fornecidas pelas mensagens de progresso (verbosidade).

          iprint[2] = 0
               Mostra na tela o contador de iteracedilhaões, o número de avaliacedilhaões de FOM, o valor de FOM, a norma do gradiente de FOM, e o comprimento do salto.

          iprint[2] = 1
               O mesmo que IPRINT[2] = 0, adicionando X0 e o gradiente de FOM avaliado em X0.

          iprint[2] = 2
               O mesmo que IPRINT[2] = 1, adicionando valores de X a cada iteracedilhaão.

          iprint[2] = 3
               O mesmo que IPRINT[2] = 2, adicionando o gradiente de FOM a cada iteracedilhaão.

     As colunas mostradas por lbfgs são as seguintes.

     I
          número de iteracedilhaões. Esse número é incrementado a cada busca de linha.

     NFN
          Número de avaliacedilhaões do número de mérito.

     FUNC
          Valor do nero de mérito ao final da busca de linha mais recente.

     GNORM
          Norma do gradiente do número de mérito ao final da mais recente busca de linha.

     STEPLENGTH
          Um parâmetro interno do algorítmo de busca.

     Informacedilhaão adicional com relacedilhaão a detalhes do algorítmo podem ser encontradas nos comentários do código Fortran original em [2].

     Veja também lbfgs_nfeval_max e lbfgs_ncorrections.

     Referências:

     [1] D. Liu e 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

     Exemplo:

     O mesmo FOM como calculada por FGCOMPUTE no programa sdrive.f no pacote LBFGS de Netlib. Note que as variáveis em questão são variáveis com subscritos. O FOM tem um mínimo exato igual a zero em u[k] = 1 for 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

 -- Variãvel: lbfgs_nfeval_max
     Valor padrão: 100

     lbfgs_nfeval_max é o número máximo de avaliacedilhaões do número de mérito (FOM - "figure of merit" em inglês) em lbfgs. Quando lbfgs_nfeval_max for encontrada, lbfgs retorna o resultado da última busca de linha realizada co sucesso.

 -- Variãvel: lbfgs_ncorrections
     Valor padrão: 25

     lbfgs_ncorrections é o número de correcedilhaões aplicadas à matriz Hessiana inversa aproximada que é mantida por lbfgs.