doc/info/pt_BR/lbfgs.texi

   1 @c Language: Brazilian Portuguese, Encoding: iso-8859-1
   2 @c /lbfgs.texi/1.3/Sat Jun  2 00:13:23 2007//
   3 @menu
   4 * Introduç@~{a}o a lbfgs::
   5 * Funç@~{o}es e Vari@'{a}veis Definidas para lbfgs::
   6 @end menu
   7
   8 @node Introduç@~{a}o a lbfgs, Funç@~{o}es e Vari@'{a}veis Definidas para lbfgs, Top, Top
   9 @section Introduç@~{a}o a lbfgs
  10
  11 @code{lbfgs} @'{e} uma implementaç@~{a}o do algor@'{i}tmo[1] L-BFGS (Broyden-Fletcher-Goldfarb-Shanno)
  12 para resolver problemas de minimizaç@~{a}o n@~{a}o limitada atrav@'{e}s de um algor@'{i}tmo de mem@'{o}ria limitada quasi-Newton (BFGS).
  13 Esse algor@'{i}tmo @'{e} chamado de m@'{e}todo de mem@'{o}ria limitada porque uma aproximaç@~{a}o de baixo ranque da
  14 inverso da matriz Hessiana @'{e} armazenado em lugar da inversa da matriz Hessiana completa.
  15 O programa foi escrito origin@'{a}riamente em Fortran [2] por Jorge Nocedal,
  16 incorporando algumas funç@~{o}es originalmente escritas por Jorge J. Mor@'{e} e David J. Thuente,
  17 e traduzidas para Lisp automaticamente atrav@'{e}s do programa @code{f2cl}.
  18 O pacote do Maxima @code{lbfgs} compreende o c@'{o}digo traduzido e adicionalmente
  19 uma interface de funç@~{a}o que gerencia alguns detallhes.
  20
  21 Refer@^{e}ncias:
  22
  23 [1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large
  24 scale optimization". @i{Mathematical Programming B} 45:503--528 (1989)
  25
  26 [2] http://netlib.org/opt/lbfgs_um.shar
  27
  28 @node Funç@~{o}es e Vari@'{a}veis Definidas para lbfgs, , Introduç@~{a}o a lbfgs, Top
  29 @section Funç@~{o}es e Vari@'{a}veis Definidas para lbfgs
  30
  31 @deffn {Funç@~{a}o} lbfgs (@var{FOM}, @var{X}, @var{X0}, @var{epsilon}, @var{iprint})
  32
  33 Encontra uma soluç@~{a}o aproximada da minimizaç@~{a}o n@~{a}o limitada de n@'{u}mero de m@'{e}rito @var{FOM}
  34 sobre a lista de vari@'{a}veis @var{X},
  35 começando a partir da estimativa inicial @var{X0},
  36 tal que @math{norm grad FOM < epsilon max(1, norm X)}.
  37
  38 O algor@'{i}tmo aplicado @'{e} um algor@'{i}tmo de mem@'{o}ria limitada[1] quasi-Newton (BFGS).
  39 Esse algor@'{i}tmo @'{e} chamado de m@'{e}todo de mem@'{o}ria limitada porque uma aproximaç@~{a}o de baixo ranque da
  40 inverso da matriz Hessiana @'{e} armazenado em lugar da inversa da matriz Hessiana completa.
  41 Cada iteraç@~{a}o do algor@'{i}tmo @'{e} uma busca de linha, isto @'{e},
  42 uma busca ao longo de um raio em torno da vari@'{a}veis @var{X},
  43 com a direç@~{a}o de busca calculada a partir da Hessian inversa aproximada.
  44 O FOM @'{e} sempre decrementado por meio de uma busca de linha realizada com sucesso.
  45 Usualmente (mas n@~{a}o sempre) a norma do gradiente de FOM tamb@'{e}m @'{e} decrementada.
  46
  47 @var{iprint} controla as messaens de progresso mostradas atrav@'{e}s de @code{lbfgs}.
  48
  49 @table @code
  50 @item iprint[1]
  51 @code{@var{iprint}[1]} controla a freq@"{u}@^{e}ncia das mensagens de progresso.
  52 @table @code
  53 @item iprint[1] < 0
  54 Nenhuma mensagem de progresso.
  55 @item iprint[1] = 0
  56 Messagens na primeira iteraç@~{a}o e na @'{u}ltima iteraç@~{a}o.
  57 @item iprint[1] > 0
  58 Mostra uma mensagem a cada @code{@var{iprint}[1]} iteraç@~{o}es.
  59 @end table
  60 @item iprint[2]
  61 @code{@var{iprint}[2]} controla a quantidade de informaç@~{o}es fornecidas pelas mensagens de progresso (verbosidade).
  62 @table @code
  63 @item iprint[2] = 0
  64 Mostra na tela o contador de iteraç@~{o}es, o n@'{u}mero de avaliaç@~{o}es de @var{FOM}, o valor de @var{FOM},
  65 a norma do gradiente de @var{FOM}, e o comprimento do salto.
  66 @item iprint[2] = 1
  67 O mesmo que @code{@var{iprint}[2] = 0}, adicionando @var{X0} e o gradiente de @var{FOM} avaliado em @var{X0}.
  68 @item iprint[2] = 2
  69 O mesmo que @code{@var{iprint}[2] = 1}, adicionando valores de @var{X} a cada iteraç@~{a}o.
  70 @item iprint[2] = 3
  71 O mesmo que @code{@var{iprint}[2] = 2}, adicionando o gradiente de @var{FOM} a cada iteraç@~{a}o.
  72 @end table
  73 @end table
  74
  75 As colunas mostradas por @code{lbfgs} s@~{a}o as seguintes.
  76
  77 @table @code
  78 @item I
  79 n@'{u}mero de iteraç@~{o}es. Esse n@'{u}mero @'{e} incrementado a cada busca de linha.
  80 @item NFN
  81 N@'{u}mero de avaliaç@~{o}es do n@'{u}mero de m@'{e}rito.
  82 @item FUNC
  83 Valor do nero de m@'{e}rito ao final da busca de linha mais recente.
  84 @item GNORM
  85 Norma do gradiente do n@'{u}mero de m@'{e}rito ao final da mais recente busca de linha.
  86 @item STEPLENGTH
  87 Um par@^{a}metro interno do algor@'{i}tmo de busca.
  88 @end table
  89
  90 Informaç@~{a}o adicional com relaç@~{a}o a detalhes do algor@'{i}tmo podem ser encontradas nos
  91 coment@'{a}rios do c@'{o}digo Fortran original em [2].
  92
  93 Veja tamb@'{e}m @code{lbfgs_nfeval_max} e @code{lbfgs_ncorrections}.
  94
  95 Refer@^{e}ncias:
  96
  97 [1] D. Liu e J. Nocedal. "On the limited memory BFGS method for large
  98 scale optimization". @i{Mathematical Programming B} 45:503--528 (1989)
  99
 100 [2] http://netlib.org/opt/lbfgs_um.shar
 101
 102 Exemplo:
 103
 104 O mesmo FOM como calculada por FGCOMPUTE no programa sdrive.f no pacote LBFGS de Netlib.
 105 Note que as vari@'{a}veis em quest@~{a}o s@~{a}o vari@'{a}veis com subscritos.
 106 O FOM tem um m@'{i}nimo exato igual a zero em @math{u[k] = 1} for @math{k = 1, ..., 8}.
 107 @c ===beg===
 108 @c load (lbfgs);
 109 @c t1[j] := 1 - u[j];
 110 @c t2[j] := 10*(u[j + 1] - u[j]^2);
 111 @c n : 8;
 112 @c FOM : sum (t1[2*j - 1]^2 + t2[2*j - 1]^2, j, 1, n/2);
 113 @c lbfgs (FOM, '[u[1], u[2], u[3], u[4], u[5], u[6], u[7], u[8]],
 114 @c        [-1.2, 1, -1.2, 1, -1.2, 1, -1.2, 1], 1e-3, [1, 0]);
 115 @c ===end===
 116
 117 @example
 118 (%i1) load (lbfgs);
 119 (%o1)   /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac
 120 (%i2) t1[j] := 1 - u[j];
 121 (%o2)                     t1  := 1 - u
 122                             j         j
 123 (%i3) t2[j] := 10*(u[j + 1] - u[j]^2);
 124                                           2
 125 (%o3)                t2  := 10 (u      - u )
 126                        j         j + 1    j
 127 (%i4) n : 8;
 128 (%o4)                           8
 129 (%i5) FOM : sum (t1[2*j - 1]^2 + t2[2*j - 1]^2, j, 1, n/2);
 130                  2 2           2              2 2           2
 131 (%o5) 100 (u  - u )  + (1 - u )  + 100 (u  - u )  + (1 - u )
 132             8    7           7           6    5           5
 133                      2 2           2              2 2           2
 134         + 100 (u  - u )  + (1 - u )  + 100 (u  - u )  + (1 - u )
 135                 4    3           3           2    1           1
 136 (%i6) lbfgs (FOM, '[u[1], u[2], u[3], u[4], u[5], u[6], u[7], u[8]],
 137        [-1.2, 1, -1.2, 1, -1.2, 1, -1.2, 1], 1e-3, [1, 0]);
 138 *************************************************
 139   N=    8   NUMBER OF CORRECTIONS=25
 140        INITIAL VALUES
 141  F=  9.680000000000000D+01   GNORM=  4.657353755084532D+02
 142 *************************************************
 143
 144    I  NFN     FUNC                    GNORM                   STEPLENGTH
 145
 146    1    3     1.651479526340304D+01   4.324359291335977D+00   7.926153934390631D-04
 147    2    4     1.650209316638371D+01   3.575788161060007D+00   1.000000000000000D+00
 148    3    5     1.645461701312851D+01   6.230869903601577D+00   1.000000000000000D+00
 149    4    6     1.636867301275588D+01   1.177589920974980D+01   1.000000000000000D+00
 150    5    7     1.612153014409201D+01   2.292797147151288D+01   1.000000000000000D+00
 151    6    8     1.569118407390628D+01   3.687447158775571D+01   1.000000000000000D+00
 152    7    9     1.510361958398942D+01   4.501931728123680D+01   1.000000000000000D+00
 153    8   10     1.391077875774294D+01   4.526061463810632D+01   1.000000000000000D+00
 154    9   11     1.165625686278198D+01   2.748348965356917D+01   1.000000000000000D+00
 155   10   12     9.859422687859137D+00   2.111494974231644D+01   1.000000000000000D+00
 156   11   13     7.815442521732281D+00   6.110762325766556D+00   1.000000000000000D+00
 157   12   15     7.346380905773160D+00   2.165281166714631D+01   1.285316401779533D-01
 158   13   16     6.330460634066370D+00   1.401220851762050D+01   1.000000000000000D+00
 159   14   17     5.238763939851439D+00   1.702473787613255D+01   1.000000000000000D+00
 160   15   18     3.754016790406701D+00   7.981845727704576D+00   1.000000000000000D+00
 161   16   20     3.001238402309352D+00   3.925482944716691D+00   2.333129631296807D-01
 162   17   22     2.794390709718290D+00   8.243329982546473D+00   2.503577283782332D-01
 163   18   23     2.563783562918759D+00   1.035413426521790D+01   1.000000000000000D+00
 164   19   24     2.019429976377856D+00   1.065187312346769D+01   1.000000000000000D+00
 165   20   25     1.428003167670903D+00   2.475962450826961D+00   1.000000000000000D+00
 166   21   27     1.197874264861340D+00   8.441707983493810D+00   4.303451060808756D-01
 167   22   28     9.023848941942773D-01   1.113189216635162D+01   1.000000000000000D+00
 168   23   29     5.508226405863770D-01   2.380830600326308D+00   1.000000000000000D+00
 169   24   31     3.902893258815567D-01   5.625595816584421D+00   4.834988416524465D-01
 170   25   32     3.207542206990315D-01   1.149444645416472D+01   1.000000000000000D+00
 171   26   33     1.874468266362791D-01   3.632482152880997D+00   1.000000000000000D+00
 172   27   34     9.575763380706598D-02   4.816497446154354D+00   1.000000000000000D+00
 173   28   35     4.085145107543406D-02   2.087009350166495D+00   1.000000000000000D+00
 174   29   36     1.931106001379290D-02   3.886818608498966D+00   1.000000000000000D+00
 175   30   37     6.894000721499670D-03   3.198505796342214D+00   1.000000000000000D+00
 176   31   38     1.443296033051864D-03   1.590265471025043D+00   1.000000000000000D+00
 177   32   39     1.571766603154336D-04   3.098257063980634D-01   1.000000000000000D+00
 178   33   40     1.288011776581970D-05   1.207784183577257D-02   1.000000000000000D+00
 179   34   41     1.806140173752971D-06   4.587890233385193D-02   1.000000000000000D+00
 180   35   42     1.769004645459358D-07   1.790537375052208D-02   1.000000000000000D+00
 181   36   43     3.312164100763217D-10   6.782068426119681D-04   1.000000000000000D+00
 182
 183  THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS.
 184  IFLAG = 0
 185 (%o6) [u  = 1.000005339815974, u  = 1.000009942839805,
 186         1                       2
 187 u  = 1.000005339815974, u  = 1.000009942839805,
 188  3                       4
 189 u  = 1.000005339815974, u  = 1.000009942839805,
 190  5                       6
 191 u  = 1.000005339815974, u  = 1.000009942839805]
 192  7                       8
 193 @end example
 194 @end deffn
 195
 196 @defvr {Vari@~{a}vel} lbfgs_nfeval_max
 197 Valor padr@~{a}o: 100
 198
 199 @code{lbfgs_nfeval_max} @'{e} o n@'{u}mero m@'{a}ximo de avaliaç@~{o}es do n@'{u}mero de m@'{e}rito (FOM - "figure of merit" em ingl@^{e}s) em @code{lbfgs}.
 200 Quando @code{lbfgs_nfeval_max} for encontrada,
 201 @code{lbfgs} retorna o resultado da @'{u}ltima busca de linha realizada co sucesso.
 202
 203 @end defvr
 204
 205 @defvr {Vari@~{a}vel} lbfgs_ncorrections
 206 Valor padr@~{a}o: 25
 207
 208 @code{lbfgs_ncorrections} @'{e} o n@'{u}mero de correç@~{o}es aplicadas
 209 @`{a} matriz Hessiana inversa aproximada que @'{e} mantida por @code{lbfgs}.
 210
 211 @end defvr
 212