[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

57. lbfgs


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

57.1 Introdução a lbfgs

lbfgs é uma implementação do algorítmo[1] L-BFGS (Broyden-Fletcher-Goldfarb-Shanno) para resolver problemas de minimizaçã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 aproximaçã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 funçõ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 funçã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


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Índice] [ ? ]

57.2 Funções e Variáveis Definidas para lbfgs

Função: lbfgs (FOM, X, X0, epsilon, iprint)

Encontra uma solução aproximada da minimização não limitada de número de mérito FOM sobre a lista de variáveis X, começando 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 aproximação de baixo ranque da inverso da matriz Hessiana é armazenado em lugar da inversa da matriz Hessiana completa. Cada iteração do algorítmo é uma busca de linha, isto é, uma busca ao longo de um raio em torno da variáveis X, com a direçã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 iteração e na última iteração.

iprint[1] > 0

Mostra uma mensagem a cada iprint[1] iterações.

iprint[2]

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

iprint[2] = 0

Mostra na tela o contador de iterações, o número de avaliaçõ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 iteração.

iprint[2] = 3

O mesmo que iprint[2] = 2, adicionando o gradiente de FOM a cada iteração.

As colunas mostradas por lbfgs são as seguintes.

I

número de iterações. Esse número é incrementado a cada busca de linha.

NFN

Número de avaliaçõ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.

Informação adicional com relaçã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 avaliaçõ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 correções aplicadas à matriz Hessiana inversa aproximada que é mantida por lbfgs.


[ << ] [ >> ]           [Top] [Contents] [Índice] [ ? ]

This document was generated by Robert Dodier on Dezembro, 22 2007 using texi2html 1.76.