| blob | 085d1a93b4d465f4234fa3cdcb2caaaa7de64f10 |
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ção a lbfgs::
5 * Funções e Variáveis Definidas para lbfgs::
6 @end menu
8 @node Introdução a lbfgs, Funções e Variáveis Definidas para lbfgs, Top, Top
9 @section Introdução a lbfgs
11 @code{lbfgs} é uma implementação do algorítmo[1] L-BFGS (Broyden-Fletcher-Goldfarb-Shanno)
12 para resolver problemas de minimização não limitada através de um algorítmo de memória limitada quasi-Newton (BFGS).
13 Esse algorítmo é chamado de método de memória limitada porque uma aproximação de baixo ranque da
14 inverso da matriz Hessiana é armazenado em lugar da inversa da matriz Hessiana completa.
15 O programa foi escrito origináriamente em Fortran [2] por Jorge Nocedal,
16 incorporando algumas funções originalmente escritas por Jorge J. Moré e David J. Thuente,
17 e traduzidas para Lisp automaticamente através do programa @code{f2cl}.
18 O pacote do Maxima @code{lbfgs} compreende o código traduzido e adicionalmente
19 uma interface de função que gerencia alguns detallhes.
21 Referências:
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)
26 [2] http://netlib.org/opt/lbfgs_um.shar
28 @node Funções e Variáveis Definidas para lbfgs, , Introdução a lbfgs, Top
29 @section Funções e Variáveis Definidas para lbfgs
31 @deffn {Função} lbfgs (@var{FOM}, @var{X}, @var{X0}, @var{epsilon}, @var{iprint})
33 Encontra uma solução aproximada da minimização não limitada de número de mérito @var{FOM}
34 sobre a lista de variá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)}.
38 O algorítmo aplicado é um algorítmo de memória limitada[1] quasi-Newton (BFGS).
39 Esse algorítmo é chamado de método de memória limitada porque uma aproximação de baixo ranque da
40 inverso da matriz Hessiana é armazenado em lugar da inversa da matriz Hessiana completa.
41 Cada iteração do algorítmo é uma busca de linha, isto é,
42 uma busca ao longo de um raio em torno da variáveis @var{X},
43 com a direção de busca calculada a partir da Hessian inversa aproximada.
44 O FOM é sempre decrementado por meio de uma busca de linha realizada com sucesso.
45 Usualmente (mas não sempre) a norma do gradiente de FOM também é decrementada.
47 @var{iprint} controla as messaens de progresso mostradas através de @code{lbfgs}.
49 @table @code
50 @item iprint[1]
51 @code{@var{iprint}[1]} controla a freq@"{u}ê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ção e na última iteração.
57 @item iprint[1] > 0
58 Mostra uma mensagem a cada @code{@var{iprint}[1]} iterações.
59 @end table
60 @item iprint[2]
61 @code{@var{iprint}[2]} controla a quantidade de informações fornecidas pelas mensagens de progresso (verbosidade).
62 @table @code
63 @item iprint[2] = 0
64 Mostra na tela o contador de iterações, o número de avaliaçõ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ção.
70 @item iprint[2] = 3
71 O mesmo que @code{@var{iprint}[2] = 2}, adicionando o gradiente de @var{FOM} a cada iteração.
72 @end table
73 @end table
75 As colunas mostradas por @code{lbfgs} são as seguintes.
77 @table @code
78 @item I
79 número de iterações. Esse número é incrementado a cada busca de linha.
80 @item NFN
81 Número de avaliações do número de mérito.
82 @item FUNC
83 Valor do nero de mérito ao final da busca de linha mais recente.
84 @item GNORM
85 Norma do gradiente do número de mérito ao final da mais recente busca de linha.
86 @item STEPLENGTH
87 Um parâmetro interno do algorítmo de busca.
88 @end table
90 Informação adicional com relação a detalhes do algorítmo podem ser encontradas nos
91 comentários do código Fortran original em [2].
93 Veja também @code{lbfgs_nfeval_max} e @code{lbfgs_ncorrections}.
95 Referências:
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)
100 [2] http://netlib.org/opt/lbfgs_um.shar
102 Exemplo:
104 O mesmo FOM como calculada por FGCOMPUTE no programa sdrive.f no pacote LBFGS de Netlib.
105 Note que as variáveis em questão são variáveis com subscritos.
106 O FOM tem um mí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===
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 *************************************************
144 I NFN FUNC GNORM STEPLENGTH
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
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
196 @defvr {Variãvel} lbfgs_nfeval_max
197 Valor padrão: 100
199 @code{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 @code{lbfgs}.
200 Quando @code{lbfgs_nfeval_max} for encontrada,
201 @code{lbfgs} retorna o resultado da última busca de linha realizada co sucesso.
203 @end defvr
205 @defvr {Variãvel} lbfgs_ncorrections
206 Valor padrão: 25
208 @code{lbfgs_ncorrections} é o número de correções aplicadas
209 à matriz Hessiana inversa aproximada que é mantida por @code{lbfgs}.
211 @end defvr